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

Question

Каковы применения красно-черных деревьев? Есть ли какое-либо приложение, в котором могут использоваться только деревья RB, а также никакие другие структуры данных?

Answer 1

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

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

Answer 2

A red-black tree - особая реализация self-balancing binary search tree, и сегодня это, по-видимому, самый популярный выбор реализации.

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

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

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

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

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

Answer 3

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

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

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

 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) 

Answer 4

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

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

Answer 5

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

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