Изменения
Нет описания правки
==Вращения==
Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:
* Ни один обход путь от корня до листьев дерева не содержит двух последовательных красных узлов.
* Количество черных узлов на каждом таком пути одинаково.
Из этих инвариантов следует, что длина каждого пути от корня до листьев в красно-черном дереве с <tex>N</tex> узлами не превышает <tex>2 \cdot \log(N)</tex> .
'''Node''' insert(h : '''Node''', key : '''Key''', value : '''Value''')
<span style="color:#008000">//Вставка нового узла к листу дерева</span>
'''if''' (h == ''null'')
'''return''' '''new''' Node(key, value)
<span style="color:#008000">//Расщепление узла с <tex>4</tex>-я потомками</span>
'''if''' (isRed(h.left) '''&&''' isRed(h.right))
colorFlip(h)
<span style="color:#008000">//Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span>
'''int''' cmp = key.compareTo(h.key)
'''if''' (cmp == 0)
'''else'''
h.right = insert(h.right, key, value)
<span style="color:#008000">//Принудительное вращение влево</span>
'''if''' (isRed(h.right) '''&&''' '''!'''isRed(h.left))
h = rotateLeft(h)
<span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span>
'''if''' (isRed(h.left) '''&&''' isRed(h.left.left))
h = rotateRight(h)
*Использование Переворота цветов и вращений сохраняет баланс черной связи.
*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4</tex>-я потомками
<span style="color:#008000">//Исправление правых красных связей</span>
'''Node''' fixUp(h : '''Node''')
'''if''' (isRed(h.right))
h = rotateLeft(h)
<span style="color:#008000">//Вращение <tex>2</tex>-ой красной пары пары</span>
'''if''' (isRed(h.left) '''&&''' isRed(h.left.left))
h = rotateRight(h)
<span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span>
'''if''' (isRed(h.left) '''&&''' isRed(h.right))
colorFlip(h)
'''Node''' deleteMax(h : '''Node''')
if (isRed(h.left))
<span style="color:#008000">//вращаем все 3-вершины вправо</span>
h = rotateRight(h)
<span style="color:#008000">//поддерживаем инвариант (h должен быть красным)</span>
if (h.right == null)
return null
<span style="color:#008000">//заимствуем у брата если необходимо</span>
if (!isRed(h.right) '''&&''' !isRed(h.right.left))
h = moveRedRight(h)
<span style="color:#008000">// опускаемся на один уровень глубже </span>
h.left = deleteMax(h.left)
<span style="color:#008000">//исправление правых красных ссылок и 4-вершин на пути вверх</span>
'''return''' fixUp(h)
'''Node''' deleteMin(h : '''Node''')
<span style="color:#008000">//удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span>
if (h.left == ''null'')
'''return''' ''null''
<span style="color:#008000">//Если необходимо, пропушим красную ссылку вниз</span>
'''if (!'''isRed(h.left) '''&& !'''isRed(h.left.left))
h = moveRedLeft(h)
<span style="color:#008000">//опускаемся на уровень ниже </span>
h.left = deleteMin(h.left)
'''return''' fixUp(h)
