Изменения
→Высота красно-черного дерева
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корю корню иметь красных детей.
Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <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>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>x</tex> содержится не менее чем <tex>2^{h'-1} - 1 + 2^{h'-1} - 1 + 1 = 2^{h'+1} - 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.parent.right == t{{---}} правый сын t = t.parent
leftRotate(t)
t = grandfather
'''else'''<font color=green>// нет "дяди" </font> '''if''' t.parent.left == t{{---}} левый ребенок
t = t.parent
rightRotate(t)
leftRotate(grandfather)
root.colour = black <font color=green>// восстанавливаем свойство корня </font>
=== Удаление вершины ===
'''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
'''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
=== Объединение красно-чёрных деревьев ===
