Изменения

Перейти к: навигация, поиск

Красно-черное дерево

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

Навигация