60
правок
Изменения
Нет описания правки
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.
== Связь с 2-3 и 2-4 деревьями ==
Красно-черные деревья эквивалентны B-деревьям 4 порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют узлы, являющиеся одним узлом B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла {{---}} цвет. Только один из элементов узла в B-дереве имеет черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.
[[Файл:Rbtree.png|750px|]]
Сопоставив таким образом цвета узлам дерева, можно проверить, что полученное дерево удовлетворяет всем свойствам красно-черного дерева.
Во-первых, у красного узла родитель не может быть красного цвета, так как в 2-4 дереве в одном узле содержится не более трех элементов и один из элементов обязательно черный. Значит можно подвесить оставшиеся красные элементы так, чтобы их родитель был черным. Во-вторых, число черных узлов на любом пути от листа до вершины одинаково, так как в B-дереве это свойство выполнено, а из каждого узла B-дерева только один элемент красится в черный цвет. Наконец, корень дерева {{---}} черный, так как вершина B-дерева состоит из узла, в котором один элемент {{---}} черный.
==См. также==
* [http://nord.org.ua/static/course/algo_2009/lecture10.pdf Курс kiev-clrs {{---}} Лекция 10. Красно-чёрные деревья]
* [http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002 Визуализатор]
* [http://rflinux.blogspot.ru/2011/10/red-black-trees.html Абстрактные типы данных {{---}} Красно-чёрные деревья (Red black trees)]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
