Изменения
→Псевдокод
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
Из рассмотренных случаев ясно, что при удалении выполняется не более трёх вращений.
'''Псевдокод:'''
'''func''' delete(key)
Node p = root
<font color=green>// находим узел с ключом key</font>
'''while''' p.key != key
'''if''' p.key < key
p = p.right
'''else'''
p = p.left
<font color=green>// случай, когда нет детей</font>
'''if''' p.left == ''nil'' '''and''' p.right == ''nil''
'''if''' p == root
root = ''nil''
'''else'''
'''if''' p.parent.left == p
p.parent.left = ''nil''
'''else'''
p.parent.right = ''nil''
'''return'''
Node y = ''nil''
Node q = ''nil''
'''if''' p.left == ''nil'' '''or''' p.right == ''nil''
<font color=green>// один ребенок</font>
y = p
'''else'''
<font color=green>// два ребенка</font>
'''if''' p.left != ''nil''
y = p.left
'''while''' y.right != ''nil''
y = y.right
'''else'''
y = p.right;
'''while''' y.left != ''nil''
y = y.left
'''if''' y.left != ''nil''
q = y.left
'''else'''
q = y.right
'''if''' q != ''nil''
q.parent = y.parent;
'''if''' y.parent == ''nil''
root = q
'''else'''
'''if''' y is leftChild
y.parent.left = q
'''else'''
y.parent.right = q
'''if''' y != p
p.colour = y.colour
p.key = y.key
'''if''' y.colour == black
<font color=green>// при удалении черной вершины могла быть нарушена балансировка</font>
fixDeleting(q);
'''func''' fixDeleting(p: '''Node''')
Node brother = ''nil''
'''while''' p != root '''and''' p isBlack
'''if''' p is leftChild
brother = p.parent.right
'''if''' brother isRed
brother.colour = black
p.parent.colour = red
leftRotate(p.parent)
brother = p.parent.right
'''if''' brother.left isBlack '''and''' brother.right isBlack
brother.colour = red
p = p.parent
'''else'''
'''if''' brother.right isBlack
brother.left.colour = black
brother.colour = red
rightRotate(brother)
brother = p.parent.right
brother.colour = p.parent.colour
p.parent.colour = black
brother.right.colour = black
leftRotate(p.parent)
p = root
'''else''' <font color=green>// p is rightChild </font>
brother = p.parent.left
'''if''' brother isRed
brother.colour = black
p.parent.colour = red
rightRotate(p.parent)
brother = p.parent.left
'''if''' brother.left isBlack '''and''' brother.right isBlack
brother.colour = red
p = p.parent
'''else'''
'''if''' brother.left isBlack
brother.right.colour = black
brother.colour = red
leftRotate(brother);
brother = p.parent.left
brother.colour = p.parent.colour
p.parent.colour = black
brother.left.colour = black
rightRotate(p.parent)
p = root
p.colour = black
root.colour = black
=== Объединение красно-чёрных деревьев ===
