288
правок
Изменения
→Вращения
}}
==Вращения==
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 N nodes is no longer than 2 lg N . 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 3-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-3-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'''):
