Изменения
Нет описания правки
*Каждый новый узел всегда окрашен в красный цвет.
*Каждый дочерний узел листа дерева считается черным.
==Переворот цветовВращения==
Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:
* Ни один путь от корня до листьев дерева не содержит двух последовательных красных узлов.
Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют <tex>3</tex>-узел, левый потомок которого окрашен в красный, в <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
[[File:rotateRight.png|310px|thumb|upright|Rotate Right]]
'''Node''' rotateRight(h : '''Node''')
h.color = RED
'''return''' x
==Переворот цветов==
В красно-черных деревьях используется такая операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.
===Псевдокод===
[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]]
'''void''' flipColors(h : '''Node''' h)
