288
правок
Изменения
→Вращения
}}
==Вращения==
Чтобы поддерживать красно-черные двоичное деревья поиска необходимо соблюдать следующие инвариантные свойства при вставке и удалении:
* Ни один обход от корня до листьев дерева не содержит двух последовательных красных узлов.
Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращениями. Эти операции трансформируют <tex>3</tex>-узел,левый потомок которого окрашен в красный, в <tex>3</tex>-узел, правый потомок которого окрашен в красный и наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
<code>
'''Node''' rotateRight( h : '''Node''' ):
x = h.left
h.left= x.right
<code>
'''Node''' rotateLeft( h : '''Node''' ):
x = h.right
h.right = x.left
'''return''' x
</code>
==Color flip==
В красно-черных деревьях используется такая операция как <tex>color flip</tex>, которая инвертирует цвет данного узла и двух его детей. Она не изменяет количество черных узлов при любом обходе от корня до листьев дерева, но может привести к появлению двух последовательных красных узлов.
<code>
'''void''' flipColors(h : '''Node''' h): h.color = '''!'''h.color h.left.color = '''!'''h.left.color h.right.color = '''<tex> !'''</tex> h.right.color
</code>
