Изменения

'''if''' root == ''nil''дерево пустое

'''while''' p != ''nil''<font color=green>// спускаемся вниз, пока не дойдем до подходящего листа </font>

'''if''' root == t{{---}} корень t.colour = black

<font color=green>// далее все предки упоминаются относительно t </font> '''while''' t.parent !"отец" красный <font color= ''nil'' '''and''' t.parent.colour == red Node grandfather = t.parent.parent Node uncle = ''nil''green>// нарушается свойство <tex>3</tex> </font> '''if''' grandfather.left == t.parent "отец" {{---}} левый ребенок '''if''' grandfather.right != ''nil'' uncle = grandfather.rightесть "дядя" '''if''' uncle.colour == red <font color=green>// случай, когда "дядя" красный </font> t.parent.colour = black uncle.colour = black grandfather.colour = red

<font color=green>// случай, когда нет "дяди" </font> '''if''' t.parent.right == t{{---}} правый сын t = t.parent

t.parent.colour = black grandfather.colour = red rightRotate(ggrandfather) '''else'''<font color=green>// "отец" {{---}} правый ребенок </font> '''if''' grandfather.left != ''nil'' uncle = grandfather.left;есть "дядя" '''if''' uncle.colour == red <font color=green>// случай, когда "дядя" красный </font> t.parent.colour = black uncle.colour = black grandfather.colour = red

'''else'''<font color=green>// нет "дяди" </font> '''if''' t.parent.left == t{{---}} левый ребенок

t.parent.colour = black grandfather.colour = red

root.colour = black <font color=green>// восстанавливаем свойство корня </font>

<font color=green>// случай, когда нет детей</font> '''if''' у p.left == ''nil'' '''and''' p.right == ''nil''нет детей '''if''' p == root{{---}} корень

'''if''' ссылку на p.parent.left == p p.parent.left = ''nil'' '''else''' p.parent.right = у "отца" меняем на ''nil''

'''if''' p.left == ''nil'' '''or''' p.right == ''nil'' <font color=green>// один ребенок</font> ссылку на у от "отца" меняем на ребенка y = p

'''if''' p.left != ''nil'' y = p.left '''while''' y.right !вершина, со следующим значением ключа <font color= ''nil'' y = y.rightgreen>// у нее нет левого ребенка </font> '''elseif''' y = p.right;имеет правого ребенка '''while''' y.left != ''nil'' y = y.left '''if''' y.left != ''nil'' q = y.left '''else''' q = yt.right '''if''' q != ''nil'' q.parent = y.parent; '''if''' y.parent == ''nil''{{---}} корень root = q '''else''' '''if''' y is leftChild yt.parent.left = qright

у родителя ссылку на y меняем на ссылку на первого ребенка y.parent.right = q

Node brother <font color= ''nil''green>// далее родственные связи относительно p</font> '''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у "брата" черные дети <font color=green>// случай <tex>1:</tex> "брат" красный с черными детьми</font> brother.colour = red p = p.parent

'''if''' brother.right isBlackправый ребенок "брата" черный <font color=green>// случай, рассматриваемый во втором подпункте:</font> brother.left.colour = black <font color=green>// "брат" красный с черными правым ребенком</font> brother.colour = red

brother = p.parent.right brother.colour = p.parent.colour <font color=green>// случай, рассматриваемый в последнем подпункте</font> p.parent.colour = black brother.right.colour = black leftRotate(p.parent)

'''else''' <font color=green>// p is rightChild {{---}} правый ребенок</font> brother <font color= p.parent.leftgreen>// все случаи аналогичны тому, что рассмотрено выше</font> '''if''' brother isRed"брат" красный brother.colour = black p.parent.colour = red

brother = p.parent.left '''if''' brother.left isBlack '''and''' brother.right isBlackу "брата" черные дети brother.colour = red p = p.parent

'''if''' brother.left isBlackлевый ребенок "брата" черный brother.right.colour = black brother.colour = red

brother = p.parent.left brother.colour = p.parent.colour p.parent.colour = black brother.left.colour = black

p.colour = black root.colour = black