Изменения
Нет описания правки
===Псевокод===
[[File:rotateRight.png|310px|thumb|upright|Rotate Right]]
'''Node''' rotateRight( h : '''Node''') :
x = h.left
h.left= x.right
'''return''' x
[[File:rotateLeft.png|310px|thumb|upright|Rotate Left]]
'''Node''' rotateLeft( h : '''Node''') :
x = h.right
h.right = x.left
[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]]
'''void''' flipColors( h : '''Node''' h) :
h.color = '''!''' h.color
h.left.color = '''!''' h.left.color
===Псевдокод===
'''void''' insert( '''key''' : Key, '''value''' : Value ):
root = insert(root, key, value)
root.color = BLACK
'''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value'''):
<span style="color:#008000">//Вставка нового узла к листу дерева</span>
'''if''' (h == ''null'')
Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом, проходит от вершины до искомого элемента. Если же элемент отсутствует цикл пройдет то листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
===Псевдокод===
'''Value''' search(key : '''Key'''):
'''Node''' x = root
'''while''' (x '''!'''= null)
*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4--</tex>я потомками
<span style="color:#008000">//Исправление правых красных связей</span>
'''Node''' fixUp(h : '''Node'''):
'''if''' (isRed(h.right))
h = rotateLeft(h);
===Псевдокод===
'''void''' deleteMax():
root = deleteMax(root);
root.color = BLACK;
'''Node''' moveRedLeft(h : '''Node'''):
colorFlip(h);
if (isRed(h.right.left)
'''return''' h;
'''Node''' deleteMax(h : '''Node'''):
if (isRed(h.left))
<span style="color:#008000">//вращаем все 3-вершины вправо</span>
[[File:MoveRedLeftNoEasy.png|400px|thumb|upright|Перемещение красной ссылки. Сложный случай]]
===Псевдокод===
'''Node''' moveRedLeft(h : '''Node'''):
colorFlip(h);
if (isRed(h.right.left))
'''return''' h;
'''void''' deleteMin():
root = deleteMin(root);
root.color = BLACK;
'''Node''' deleteMin(h : '''Node'''):
<span style="color:#008000">//удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span>
if (h.left == ''null'')
