[[Файл:RBTRbtree.jpgJPG|350px|thumb|Пример красно-чёрного дерева.]]'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный".
При этом все листья дерева являются фиктивными и не содержат данных.
== Свойства ==
Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлена дополнительный аттрибут – цвет и для которого выполняются следующие '''свойства''':
# Каждый узел промаркирован красным или чёрным цветом
# Корень и конечные узлы (листья) дерева – чёрные
== Высота красно-черного дерева ==
Назовем черной высотой дерева {{Теорема |statement=Красно-чёрное дерево с корневой вершиной <tex>rn</tex> максимальное количество черных вершин во всех ветвях, начинающихся в ключами имеет высоту <tex>r</tex> и заканчивающихся в листьях, не считая саму вершину <tex>r</tex>. Будем обозначать ее <tex>hbh \geqslant \log(n + 1) = O(r\log n)</tex>.||proof=Схема доказательства:
'''Лемма'''. # Совмещаем все красные узлы с родительскими чёрными (они существуют по свойству 2) начиная с корня# В результате получим дерево, каждый узел котрого имеет 2, 3 или 4 потомка# В следствии свойства 4 красно-черном дереве с черной высотой чёрного дерева, все листья 2-3-4 дерева будут иметь одинаковую глубину – black-height корня исходного дерева# Пусть дерево из п.2 имеет высоту <tex>hbh'</tex> количество внутренних вершин не менее . Тогда <tex>h' \geqslant h/2^{hb+1}-1</tex>, т.к. не более половины узлов на каждом пути – красные
'''Доказательство'''. Если рассмотреть лист (фиктивную вершину), то для нее лемма верна. Рассмотрим внутреннюю вершину <tex>x</tex>. Пусть <tex>hb(x)=h</tex>. Тогда если ее потомок <tex>p</tex> - черный, то высота <tex>hb(p)=h-1</tex>, а если – красный, то <tex>hb(p)=h</tex>. Таким образом, по предположению индукции, в поддеревьях содержится не менее <tex>2^h-1</tex> вершин, а во всём дереве, соответственно, не менее <tex>[[Файл:2^h-1 + 2^h3-1 + 1=2^{h+1}-1</tex>4_tree.Если обычная высота дерева равна <tex>h</tex>, то черная высота дерева будет не меньше <tex>h/2-1</tex> и, по лемме, количество внутренних вершин в деревеJPG|350px|]]
# Количество листьев не изменяется и равно <tex>N \ge n + 1</tex> для обоих деревьев, т.к. в красно-чёрном дереве все внутренние узлы имеют ровно два листа6. В 2^{-3-4 дереве высоты <tex>h'</2}-tex> количество листьев <tex>n + 1</tex>ограничено:
Прологарифмировав неравенство, имеем:<tex>2^{h'} \leqslant n + 1 \leqslant 4^{h'}</tex>
<tex>\log(N+1) \ge h/2</tex># Тогда:
<tex>2\log(Nn +1) \ge geqslant 2^{h'}</tex>
<tex>h \le 2\log(Nn +1)\geqslant h' \geqslant h/2</tex>
Итак, учитывая, что для любого бинарного дерева <tex>h > \leqslant 2\log(Nn + 1)</tex>, получаем, что доказана следующая}}
'''Теорема'''. Для красно-черного дерева, имеющего <tex>N</tex> внутренних вершин, верна следующая оценка для его высоты <tex>h=O(\log(N))</tex>, или, более точно, <tex>\log(N) < h \le 2\log(N+1)</tex>.
== Операции ==
