Левосторонние красно-чёрные деревья
| Определение: |
| Left-leaning Red-Black Trees— . |
Вращения
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 for
those 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 this
page). 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.
Node rotateRight(h : Node): x = h.left h.left= x.right x.right= h x.color = h.color h.color = RED return x
Node rotateLeft(h : Node): x = h.right h.right = x.left x.left = h x.color = h.color h.color = RED return x
void flipColors(h : Node h): h.color = !h.color h.left.color = !h.left.color h.right.color = !h.right.color
Методы
void insert( key : Key, value : Value ):
root = insert(root, key, value)
root.color = BLACK
Node insert( h : Node, key : Key, value : Value):
if h == null
return new Node(key, value)
if isRed(h.left) && isRed(h.right)
colorFlip(h)
int cmp = key.compareTo(h.key)
if cmp == 0
h.val = value
else
if cmp < 0
h.left = insert(h.left, key, value)
else
h.right = insert(h.right, key, value)
if isRed(h.right) && !isRed(h.left)
h = rotateLeft(h)
if isRed(h.left) && isRed(h.left.left)
h = rotateRight(h)
return h
Value search(key : Key):
Node x = root
while x != null
int cmp = key.compareTo(x.key)
if cmp == 0
return x.val
else
if cmp < 0
x = x.left
else
if cmp > 0
x = x.right
return null
Удаление
f cient implementation of the delete operation is a challenge in many symbol-table implementa- tions, and red-black trees are no exception. Industrial-strength implementations run to over 100 lines of code, and text books generally describe the operation in terms of detailed case studies, eschewing full implementations. Guibas and Sedgewick presented a delete implementation in [7], but it is not fully speci ed and depends on a call-by-reference approach not commonly found in modern code. The most popular method in common use is based on a parent pointers (see [6]), which adds substantial overhead and does not reduce the number of cases to be handled.
The code on the next page is a full implementation of for LLRB 2-3 trees. It is based on the reverse of the approach used for insert in top-down 2-3-4 trees: we perform rotations and color ips on the way down the search path to ensure that the search does not end on a 2-node, so that we can just delete the node at the bottom. We use the method to share the code for the color ip and rotations following the
recursive calls in the code.With , we can leave right-leaning red links and unbalanced 4-nodes along the search path, secure
that these conditions will be xed on the way up the tree. (The approach is also effective 2-3-4 trees, but requires an extra rotation when the right node
off the search path is a 4-node.)
As a warmup, consider the delete-the-minimum operation, where the goal is to delete the bottom node on the left spine while maintaining balance. To do so, we maintain the invariant that the current node or its left child is red. We can do so by moving to the left unless the current node is red and its left child and left grandchild are both black. In that case, we can do a color ip, which restores the invariant but may introduce successive reds on the right. In that case, we can correct the condition with two rotations and a color ip. These operations are implemented in the method on the next page. With , the recursive implementation of above is straightforward.
For general deletion, we also need , which is similar, but simpler, and we need to rotate left-leaning red links to the right on the search path to maintain the invariant. If the node to be deleted is an internal node, we replace its key and value elds with those in the minimum node in its right subtree and then delete the minimum in the right subtree (or we could rearrange pointers to use the node instead of copying elds). The full implementation of that dervies from this discussion is given on the facing page. It uses one-third to one-quarter the amount of code found in typical implementations. It has been demonstrated before [2, 11, 13] that maintaining a eld in each node containing its height can lead to code for delete that is similarly concise, but that extra space is a high price to pay in a practical implementation. With trees, we can arrange for concise code having a logarithmic performance guarantee and using no extra space.
void deleteMin() root = deleteMin(root); root.color = BLACK;
Node deleteMin(h : Node)
if (h.left == null) return null;
if !isRed(h.left) && !isRed(h.left.left)
h = moveRedLeft(h);
h.left = deleteMin(h.left);
return fixUp(h);
Delete-the-minimum code for LLRB 2-3 trees
void deleteMin(): root = deleteMin(root) root.color = BLACK
Node deleteMin( h : Node):
if h.left == null
return null
if !isRed(h.left) && !isRed(h.left.left)
h = moveRedLeft(h)
h.left = deleteMin(h.left)
return fixUp(h)
Node moveRedLeft(Node : h):
colorFlip(h):
if isRed(h.right.left)
h.right = rotateRight(h.right)
h = rotateLeft(h)
colorFlip(h)
return h
Node moveRedRight(h :Node ):
colorFlip(h)
if isRed(h.left.left))
h = rotateRight(h)
colorFlip(h)
return h
void delete(key : Key): root = delete(root, key) root.color = BLACK
Node delete(Node : h, Key : key):
if key.compareTo(h.key) < 0)
if !isRed(h.left) && !isRed(h.left.left)
h = moveRedLeft(h)
h.left = delete(h.left, key)
else
if isRed(h.left)
h = rotateRight(h)
if key.compareTo(h.key) == 0 && (h.right == null)
return null
if !isRed(h.right) && !isRed(h.right.left)
h = moveRedRight(h)
if key.compareTo(h.key) == 0
h.val = get(h.right, min(h.right).key)
h.key = min(h.right).key
h.right = deleteMin(h.right)
else
h.right = delete(h.right, key)
return fixUp(h)
