Изменения
→Высота красно-черного дерева
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корю корню иметь красных детей.
Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <tex>10, 6, 45, 4, 8</tex>. На примере можно видеть, что после добавления вершины с ключом <tex>0</tex> и соответствующих перекрашиваний вершина с ключом <tex>6</tex> становится красной с красным родителем. Дальше добавим <tex>5</tex>. Так как мы добавляем к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого <tex>-3</tex>. Тогда вершина с ключом <tex>4</tex> станет красной (<tex>0</tex> и <tex>5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
{{Лемма
|statement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.
|proof=
По индукции докажем, что поддерево любого узла <tex>x</tex> с черной высотой <tex>hb(x)</tex> содержит не менее <tex>2^{hb(x)} - 1</tex> внутренних узлов. '''База индукции:''' Если рассмотреть высота узла <tex>x</tex> равна <tex>0,</tex> то <tex>x</tex> {{---}} это лист , <tex>hb(фиктивную вершинуx)= 0, то </tex> <tex>2^{0} - 1 = 0.</tex> '''Индукционный переход:''' Пусть наше предположение верно для нее лемма вернавысот до <tex>h'. Рассмотрим </tex> Теперь рассмотрим внутреннюю вершину <tex>x</tex>. Пусть с двумя потомками, для которой <tex>hb(x)=h'</tex>. Тогда если ее потомок <tex>p</tex> {{---}} черный, то его высота <tex>hb(p)=h'-1</tex>, а если красный, то <tex>hb(p) = h'</tex>. Таким образомНо поскольку высота потомка меньше, по предположению индукциичем высота узла <tex>x</tex>, для него выполняется индукционное предположение. В таком случае в поддеревьях содержится не менее поддереве узла <tex>2^{h'}-1x</tex> вершин, а во всём дереве, соответственно, содержится не менее чем <tex>2^{h'-1}-1 + 2^{h'-1}-1 + 1=2^{h'+1}-1</tex>. Следовательно, утверждение верно и для всего дерева.
}}
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
|proof=
Рассмотрим красно-чёрное дерево с высотой <tex>h.</tex> Так как у красной вершины чёрные дети <tex>(</tex>по свойству <tex>3),</tex> количество красных вершин не больше <tex>h / 2. </tex> Тогда чёрных вершин не меньше, чем <tex>h / 2 - 1.</tex>
<tex>N \geqslant 2^{h/2}-1</tex>
'''func''' insert(key)
Node t = Node(key, red, ''nil'', ''nil'') <font color=green>// конструктор, в который передаем ключ, цвет, левого и правого ребенка </font>
'''if''' root == ''nil''дерево пустое
root = t
t.parent = ''nil''
Node p = root
Node q = ''nil''
'''while''' p != ''nil''<font color=green>// спускаемся вниз, пока не дойдем до подходящего листа </font>
q = p
'''if''' p.key < t.key
p = p.left
t.parent = q
<font color=green>// добавляем новый элемент красного цвета </font>
'''if''' q.key < t.key
q.right = t
'''func''' fixInsertion(t: '''Node''')
'''if''' root == t{{---}} корень t.colour = black
'''return'''
<font color=green>// далее все предки упоминаются относительно t </font> '''while''' t.parent !"отец" красный <font color= ''nil'' '''and''' t.parent.colour == red Node grandfather = t.parent.parent Node uncle = ''nil''green>// нарушается свойство <tex>3</tex> </font> '''if''' grandfather.left == t.parent "отец" {{---}} левый ребенок '''if''' grandfather.right != ''nil'' uncle = grandfather.rightесть "дядя" '''if''' uncle.colour == red <font color=green>// случай, когда "дядя" красный </font> t.parent.colour = black uncle.colour = black grandfather.colour = red
t = grandfather
'''else'''
<font color=green>// случай, когда нет "дяди" </font> '''if''' t.{{---}} правый сын t = parent leftRotate(t) parent = black grandfather = red rightRotate(grandfather) '''else''' <font color=green>// "отец" {{---}} правый ребенок </font> '''if''' есть "дядя" '''if''' "дядя" красный parent.right =black uncle = black grandfather = red t = grandfather '''else''' <font color=green>// нет "дяди" </font> '''if''' t{{---}} левый ребенок
t = t.parent
=== Удаление вершины ===
'''else'''
p = p.left
root = ''nil''
'''else'''
'''return'''
Node y = ''nil''
Node q = ''nil''
'''if''' p.left == ''nil'' '''or''' p.right == ''nil'' <font color=green>// один ребенок</font> ссылку на у от "отца" меняем на ребенка y = p
'''else'''
<font color=green>// два ребенка</font>
'''else'''
у родителя ссылку на y меняем на ссылку на первого ребенка y.parent.right = q
'''if''' y != p
p.colour = y.colour
'''if''' y.colour == black
<font color=green>// при удалении черной вершины могла быть нарушена балансировка</font>
fixDeleting(q);
'''func''' fixDeleting(p: '''Node''')
'''else'''
'''if''' brother.right isBlackправый ребенок "брата" черный <font color=green>// случай, рассматриваемый во втором подпункте:</font> brother.left.colour = black <font color=green>// "брат" красный с черными правым ребенком</font> brother.colour = red
rightRotate(brother)
p = root
'''else''' <font color=green>// p is rightChild {{---}} правый ребенок</font> brother <font color= p.parent.leftgreen>// все случаи аналогичны тому, что рассмотрено выше</font> '''if''' brother isRed"брат" красный brother.colour = black p.parent.colour = red
rightRotate(p.parent)
'''else'''
'''if''' brother.left isBlackлевый ребенок "брата" черный brother.right.colour = black brother.colour = red
leftRotate(brother);
rightRotate(p.parent)
p = root
p.colour = black root.colour = black
=== Объединение красно-чёрных деревьев ===
Число черных узлов на любом пути от листа до вершины одинаково.
|proof=
В B-дереве глубина всех листьев одинакова. Из каждого узла B-дерева выбирается только один элемент для окраски в черный цвет, следовательно, одинаково и путь в симметричным бинарным B-дереве состоит только из элементов, лежащих количество внутренних узлов на одном каждом пути в . Мы сопоставляем чёрный цвет одному элементу внутреннего узла B-дереведерева. Значит , количество черных чёрных элементов на любом пути от листа до вершины одинаково.
}}
{{Утверждение
Корень дерева {{---}} черный.
|proof=
}}
