Изменения
Нет описания правки
if (h == null)
return new Node(key, value, RED);
*Расщепление узла с <tex>4</tex>-я потомками:
[[File:Split4node.png|310px|thumb|upright|Расщепление узла]]
if (isRed(h.left) && isRed(h.right))
colorFlip(h);
*Принудительное вращение влево:
Если правый предок красный, вращаем текущую вершину влево.
if (isRed(h.right))
h = rotateLeft(h);
*Балансировка узла с <tex>4</tex>-я потомками:
Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.
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); '''return''' h;
===Удаление максимума===
===Псевдокод===
'''void''' deleteMax()
root = deleteMax(root); root.color = BLACK;
'''Node''' moveRedLeft(h : '''Node''')
colorFlip(h);
if (isRed(h.right.left)
h.right = rotateRight(h.right); h = rotateLeft(h); colorFlip(h); '''return''' 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''' moveRedLeft(h : '''Node''')
colorFlip(h);
if (isRed(h.right.left))
h.right = rotateRight(h.right); h = rotateLeft(h); colorFlip(h); '''return''' h;
'''void''' deleteMin()
root = deleteMin(root); root.color = BLACK;
'''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);
==Асимптотика==
