Изменения

* Количество черных узлов на каждом таком пути одинаково.

Из этих инвариантов следует, что длина каждого пути от корня до листьев в красно-черном дереве с <tex>N</tex> узлами не превышает <tex>2 \cdot log(N)</tex> .

[[File:rotateRight.png|400px|thumb|upright|Rotate Right]]

Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращениями. Эти операции трансформируют <tex>3</tex>-узел,левый потомок которого окрашен в красный, в <tex>3</tex>-узел, правый потомок которого окрашен в красный и наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.

'''return''' x

</code>

<code>

'''Node''' rotateLeft( h : '''Node''') :

==Переворот цветов==

В красно-черных деревьях используется такая операция как <tex>color flip</tex>, которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов при любом обходе от корня до листьев дерева, но может привести к появлению двух последовательных красных узлов.

<code>

'''void''' flipColors( h : '''Node''' h) :