Соответственно спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно <tex>2</tex>-м.
[[File:changeNode.png|600px|thumb|center| ]]
Будем поддерживать инвариант : Для любого узла либо сам узел, либо правый предок узла '''красный'''.
Заметим, что удалять лист легче, чем внутренний узел.
'''void''' deleteMin() root = deleteMin(root); root.color = BLACK;
'''Node''' deleteMin(h : '''Node''')
if (h.left == ''null'') '''return''' ''null''; '''if !'''isRed(h.left) '''&& !'''isRed(h.left.left) h = moveRedLeft(h); h.left = deleteMin(h.left);
'''return''' fixUp(h);
'''void''' deleteMin():
root = deleteMin(root) root.color = BLACK
'''Node''' deleteMin( h : '''Node'''):
'''if''' h.left == ''null'' '''return''' ''null'' '''if''' !isRed(h.left) '''&&''' !isRed(h.left.left) h = moveRedLeft(h) h.left = deleteMin(h.left)
'''return''' fixUp(h)
'''Node''' moveRedLeft('''Node''' : h):
colorFlip(h): '''if''' isRed(h.right.left) h.right = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) '''return''' h
'''Node''' moveRedRight(h :'''Node''' ):
colorFlip(h) '''if''' isRed(h.left.left)) h = rotateRight(h) colorFlip(h) '''return''' h
'''void''' delete(key : '''Key'''): root = delete(root, key) root.color = BLACK
'''Node''' delete('''Node''' : h, '''Key''' : key):
'''if''' key.compareTo(h.key) < 0)
'''if''' !isRed(h.left) '''&&''' !isRed(h.left.left)
h = moveRedLeft(h)
h.left = delete(h.left, key)
'''else''' '''if''' isRed(h.left) h = rotateRight(h) '''if''' key.compareTo(h.key) == 0 '''&&''' (h.right == null) '''return''' ''null'' '''if''' !isRed(h.right) '''&&''' !isRed(h.right.left) h = moveRedRight(h) '''if''' key.compareTo(h.key) == 0 h.val = get(h.right, min(h.right).key) h.key = min(h.right).key h.right = deleteMin(h.right) '''else''' h.right = delete(h.right, key) '''return''' fixUp(h)
