Красно-чёрное дерево (удалить)

Красно - чёрное дерево - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный". При этом дерево должно удовлетворять следующим свойствам:

1. Все листья дерева чёрные.
2. Все сыновья красного узла чёрные.
3. На каждой ветви дерева, идущей от корня к листу, число чёрных узлов одно и то же.

При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется чёрной высотой дерева.

Свойства

Свойство 1: Число листьев в дереве с чёрной высотой [math]h[/math] не менее, чем [math]2^{h-1}[/math].
Доказательство: Докажем по индукции. При [math]h=1[/math]получаем дерево, в котором чёрными являются только листья, а их больше одного. Иначе пусть корень - чёрный, тогда оба его поддерева имеют чёрную высоту h-1 и, следовательно, не менее, чем [math]2^{h-2}[/math] элементов. Тогда всё дерево имеет более [math]2^{h-1}[/math] элементов. В случае, если корень красный, то оба его поддерева имеют чёрные корни и чёрную высоту [math]h[/math], то есть, как только что было показано, не менее [math]2^{h-1}[/math] элементов. Таким образом, дерево будет иметь более [math]2^{h}[/math] элементов.
Свойство 2: Число листьев в красно-чёрном дереве высоты [math]h[/math] не менее [math]2^{(h-1)/2}[/math].
Доказательство: Возьмём самый длинный путь в дереве. Всего в нём [math]h+1[/math] узлов. По крайней мере половина узлов чёрные, поскольку двух подряд идущих красных узлов быть не может, а лист чёрный. Поэтому чёрная высота дерева не меньше [math](h-1)/2[/math], и, по первому утверждению, [math]2^{(h-1)/2}[/math] элементов.

Отсюда также получаем, что высота дерева не более [math]2log_2 N+1[/math], где N - число элементов дерева, т.е. [math]O(log N)[/math]

Операции

1. Вставка элемента. Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын - лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то рассматриваем два случая:

1. "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" - в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.
2. "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком.