[[Файл:RBT.jpg|350px|thumb|Пример красно-чёрного дерева.]]'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный".
При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется '''чёрной высотой дерева.'''
== Свойства ==
# Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.
* == Высота красно-черного дерева ==Назовем черной высотой дерева с корневой вершиной '''r'''Свойство 1: максимальное количество черных вершин во всех ветвях, начинающихся в '''r'''Число листьев и заканчивающихся в листьях, не считая саму вершину '''r'''. Будем обозначать ее '''hb(r)'''.'''Лемма'''. В красно-черном дереве с черной высотой <tex>h</tex> '''hb''' количество внутренних вершин не менее, чем <tex>2^{hhb+1}-1}</tex>.<br/>'''Доказательство: '''Докажем по индукции. При <tex>Если рассмотреть лист (фиктивную вершину), то для нее лемма верна. Рассмотрим внутреннюю вершину '''x'''. Пусть '''hb(x)=h'''. Тогда если ее потомок '''p''' - черный, то высота '''hb(p)=h-1</tex> получаем дерево, в котором чёрными являются только листья''', а их больше одного.Иначе пусть корень - чёрныйесли – красный, тогда оба его поддерева имеют чёрную высоту то '''hb(p)=h-1 и'''. Таким образом, следовательнопо предположению индукции, в поддеревьях содержится не менее, чем <tex>2^{h-2}</tex> элементов. Тогда всё дерево имеет более <tex>2^{h-1}</tex> элементов. В случаевершин, если корень красный, то оба его поддерева имеют чёрные корни и чёрную высоту <tex>h</tex>, то естьа во всём дереве, как только что было показаносоответственно, не менее <tex>2^{h-1}</tex> элементов. Таким образом, дерево будет иметь более <tex>+ 2^h-1 + 1=2^{h+1}-1</tex> элементов.<br/>* Если обычная высота дерева равна '''h''', то черная высота дерева будет не меньше 'Свойство ''h/2: -1'''Число листьев и, по лемме, количество внутренних вершин в красно-чёрном дереве высоты <tex>h</tex> не менее <texN >= 2^{(h-1)/2}-1</tex>.<br/>'''ДоказательствоПрологарифмировав неравенство, имеем: '''Возьмём самый длинный путь в дереве. Всего в нём <tex>h\log(N+1) >= h/2</tex> узлов. По крайней мере половина узлов чёрные, поскольку двух подряд идущих красных узлов быть не может, а лист чёрный. Поэтому чёрная высота дерева не меньше <tex>2\log(h-N+1)/2>= h</tex>, и, по первому утверждению, <tex>h <= 2^{\log(h-N+1)/2}</tex> элементов.
Отсюда также получаем, что высота дерева не более <tex>2log_2 N+1</tex>, где N - число элементов дерева, т.е. <tex>O(log N)</tex> ==Операции==
* '''Вставка элемента.''' Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын - лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то достаточно рассмотреть только два случая:
1. "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" - в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.
