Изменения
→Псевдокод
[[Файл:Untitled-2.png|250px|]]
== Псевдокод ==
'''func''' insert(key)
Node t = Node(key, red, ''nil'', ''nil'') <font color=green>// конструктор, в который передаем ключ, цвет, левого и правого ребенка </font>
'''if''' root == ''nil''
root = t
t.parent = ''nil''
'''else'''
Node p = root
Node q = ''nil''
'''while''' p != ''nil''
q = p
'''if''' p.key < t.key
p = p.right
'''else'''
p = p.left
t.parent = q
'''if''' q.key < t.key
q.right = t
'''else'''
q.left = t
fixInsertion(t) <font color=green>// проверяем, не нарушены ли свойства красно-черного дерева </font>
'''func''' fixInsertion(t: '''Node''')
'''if''' root == t
t.colour = black
'''return'''
'''while''' t.parent != ''nil'' '''and''' t.parent.colour == red
Node grandfather = t.parent.parent
Node uncle = ''nil''
'''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
t = grandfather
'''else'''
'''if''' t.parent.right == t
t = t.parent
leftRotate(t)
t.parent.colour = black
grandfather.colour = red
rightRotate(g)
'''else'''
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
t = grandfather
'''else'''
'''if''' t.parent.left == t
t = t.parent
rightRotate(t)
t.parent.colour = black
grandfather.colour = red
leftRotate(grandfather)
root.colour = black <font color=green>// восстанавливаем свойство корня </font>
=== Удаление вершины ===
