Аппликации красно-черных деревьев - PullRequest
Новая
       34

Аппликации красно-черных деревьев

36 голосов
/ 10 октября 2010

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

Ответы [ 4 ]

34 голосов
/ 10 октября 2010

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

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

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

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

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

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

13 голосов
/ 21 марта 2014

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

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

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

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

4 голосов
/ 19 декабря 2012

Нет такого правила, как красный черный можно использовать только в конкретном случае это зависит от приложения в тех случаях, когда вам нужно построить дерево только один раз и запрашивать его много раз, тогда вы можете перейти к дереву AVL, потому что поиск в дереве AVL довольно быстрый ... Но он строго сбалансирован, поэтому вставка и удаление может занять некоторое время Дерево AVI может быть использовано для языковой словари, где вы должны построить структуру данных только один раз. а красное черное дерево используется в планировщике «Совершенно честно», который используется в современных ядрах 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)
...