288
правок
Изменения
→Псевдокод
===Псевдокод===
'''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);
