Применение красно-черных деревьев

Ответ 1

Красно-черное дерево - это особая реализация самобалансирующегося бинарного дерева поиска, и сегодня оно, похоже, является наиболее популярным вариантом реализации.

Двоичные деревья поиска используются для реализации конечных карт, где вы храните набор ключей со связанными значениями. Вы также можете реализовать наборы, используя только ключи и не сохраняя никаких значений.

Балансировка дерева необходима для обеспечения хорошей производительности, так как в противном случае дерево может выродиться в список, например, если вы вставите ключи, которые уже отсортированы.

Преимущество деревьев поиска перед хеш-таблицами состоит в том, что вы можете эффективно обходить дерево в порядке сортировки.

AVL-деревья - это еще один вариант сбалансированных бинарных деревьев поиска. Они были популярны до того, как стали известны красно-черные деревья. Они более тщательно сбалансированы, с максимальной разницей в один между высотами левого и правого поддерева (деревья RB гарантируют максимум два раза). Их главный недостаток в том, что для восстановления баланса требуется больше усилий.

Так что красно-черные деревья, безусловно, хороший, но не единственный выбор для этого приложения.

Ответ 2

Красные Черные Деревья взяты из класса самобалансирующих BST, и, как утверждают другие, любое такое дерево балансировки может быть использовано. Я хотел бы добавить, что красно-черные деревья широко используются в качестве таблиц системных символов. Например, они используются при реализации следующего:

• Java: java.util.TreeMap, java.util.TreeSet.
• С++ STL: map, multimap, multiset.
• Ядро Linux: полностью справедливый планировщик, linux/rbtree.h

Ответ 3

Если у вас нет особых требований к производительности, дерево R-B может быть заменено каким-то другим самобалансирующимся двоичным деревом, например деревом AVL. Выбор между ними - это в основном оптимизация производительности - они предлагают одни и те же основные операции.

Не то, чтобы любой из них был окончательно "быстрее", чем другой, просто потому, что они различны, что их использование будет иметь слегка отличающуюся производительность, при прочих равных условиях. Поэтому, если вы тщательно нарисуете свои требования или просто случайно, вы можете оказаться в одном из них "достаточно быстро" для вашего использования, а другой нет. R-B предлагает немного более быструю установку, чем AVL, за счет немного более медленного поиска.

Ответ 4

Нет такого правила, как красный черный, может использоваться только в конкретном случае это зависит от приложения в таких случаях, как когда вы должны строить дерево только один раз, и вам приходится много раз запрашивать его, тогда вы можете пойти на дерево AVL, потому что в поиске дерева AVL довольно быстро. Но он строго сбалансирован, поэтому вставка и удаление может занять некоторое время Дерево AVl может использоваться для языковой диктопии, где вам нужно построить структуру данных только один раз и красное черное дерево используется в полностью справедливом планировщике, используемом в текущих ядрах Linux, в течение нескольких дней.

ограничения, применяемые к красному черному дереву, также обеспечивают то, что путь от корня до самого удаленного листа не более чем в два раза длиннее пути от корня до ближайшего листа.

Кстати, вы можете найти различное видение и вставить и т.д. время, необходимое для красного черного дерева здесь.

        Average     Worst case

Space   O(n)        O(n) 

Search  O(log n)    O(log n)

Insert  O(log n)    O(log n)

Delete  O(log n)    O(log n)

Ответ 5

Планировщик процессов в Linux использует Red Black Trees. Красные черные деревья заменяют очереди очередей, которые имеют приоритеты для процессов в очереди для планировщика.

Полностью справедливый планировщик (C.F.S) - это имя планировщика процессов, который был объединен с выпуском ядра Linux 2.6.23. Он управляет распределением ресурсов процессора для выполнения процессов и нацелен на максимизацию общего использования ЦП, а также максимальную интерактивную производительность.