==Вращения==
One way to view red-black BST algorithms is as maintaining the following invariant properties under insertion and deletion:
• No path from the root to the bottom contains two consecutive red linksЧтобы поддерживать красно-черные двоичное деревья поиска необходимо соблюдать следующие инвариантные свойства при вставке и удалении:* Ни один путь от корня до листьев не содержит двух последовательных красных узлов.• The number of black links on every such path is the same* Количество черных узлов на каждом таком пути одинаково.These invariants imply that the length of every path in a redИз этих инвариантов следует, что длина каждого пути от корня до листьев в красно-black tree with черном дереве с <tex>N nodes is no longer than </tex> узлами не превышает <tex>2 lg \cdot log(N )</tex> . This worst case is realizedОсновные операции, for exampleиспользуемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, in a tree whose nodes are all black except forthose along a single path of alter- nating red and black nodesназываются вращениями.The basic operations that bal- anced-tree algorithms use to main- tain balance under insertion and deletion are known as rotations. In the context of red-black trees, these operations are easily understood as the transformations needed to transform a Эти операции трансформируют <tex>3</tex>-node whose red link leans to the left to a 3-node whose red link leans to the right and vice- versa. The Java code for these op- erations (for a Node type that we will consider late that contains a left link, a right linkузел, and a color eld that can be set to the value RED to represent the color of the incoming link) is given to the left and to the right on this page. Rotations obvi- ously preserve the two invariants stated above.In red-black treesлевый потомок которого окрашен в красный, we also use a simple operation known as a color в ip (shown at the bottom of thispage). In terms of 2-<tex>3</tex>-4 treesузел, a color ip is the essential operation: it corresponds to splitting a 4-node and passing the middle node up to the parentправый потомок которого окрашен в красный и наоборот. A color ip obviously does not change the number of black links on any path from the root to the bottom, but it may introduce two consecu- tive red links higher in the tree, which must be corrected.Red-black BST algorithms differ on whether and when they do rotations and color ipsВращения сохраняют два указанных выше инварианта, in order to maintain the global invariants stated at the top of this pageне изменяют поддеревья узла.
<code>
'''Node''' rotateRight(h : '''Node'''):
'''return''' x
</code>
В красно-черных деревьях используется такая операция как <tex>color flip</tex>, которая инвертирует цвет данного узла и двух его детей. Она не изменяет количество черых узлов на любом пути от корня до листьев, но может привести к появлению двух последовательных красных узлов.
<code>
