577
правок
Изменения
Нет описания правки
Для экономии памяти фиктивные листья можно сделать одним общим фиктивным листом.
В книге Кормена "Алгоритмы: построение и анализ" дается немного иное определение красно-черного дерева, а именно:
{{Определение
|definition =
'''Красно-чёрное дерево''' {{---}} это двоичное дерево поиска, вершины которого разделены на красные и черные. Таким образом, каждая вершина хранит один дополнительный бит {{---}} её цвет. При этом должны выполняться определенные требования, которые гарантируют, что глубины любых двух листьев отличаются не более, чем в два раза, поэтому дерево можно назвать сбалансированным (англ. ''balanced'')
}}
== Свойства ==
Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный аттрибут атрибут {{---}} цвет и для которого выполняются следующие свойства (англ. ''red-black properties''):
# Каждый узел промаркирован красным или чёрным цветом
# Корень и конечные узлы(листья) дерева {{---}} чёрные
