Будем поддерживать инвариант : Для любого узла либо сам узел, либо правый предок узла '''красный'''.
ЗаметимТакже,заметим, что удалять лист легче, чем внутренний узел.===Псевдокод=== '''void''' deleteMax() root = deleteMax(root); root.color = BLACK; '''Node''' deleteMax(Node h) if (isRed(h.left)) //вращаем все 3-вершины вправо h = rotateRight(h); if (h.right == null) //поддерживаем инвариант (h должен быть красным) return null; if (!isRed(h.right) && !isRed(h.right.left)) //заимствуем у брата если необходимо h = moveRedRight(h); h.left = deleteMax(h.left); // опускаемся на один уровень глубже return fixUp(h); //исправление правых красных ссылок и 4-вершин на пути вверх
