98
правок
Изменения
Нет описания правки
{{Лемма
|definitionstatement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.
}}
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Файл:RBT.jpg|350px|thumb|Пример красно-чёрного дерева.]]'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный".
При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.
== Свойства ==
Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный аттрибут – цвет и для которого выполняются следующие свойства:
# Каждый узел промаркирован красным или чёрным цветом
# Корень и конечные узлы (листья) дерева – чёрные
# У красного узла родительский узел – чёрный
# Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов – black-height(x)
# Чёрный узел может иметь чёрного родителя
{{Определение
|definition=Будем называть чёрной высотой вершины
