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