Algorithms in a Nutshell

(^134) | Chapter 5: Searching
The fundamental operation when restructuring the tree is a rotation about a node.
We modify the pointers in the tree to effect the rotation. Figure 5-12 shows the
results of rotating left or right about a node. The tree on the left can be rotated left
about nodeato get the tree on the right. Similarly, you can perform a right rota-
tion about nodeb to the tree on the right to get the tree on the left.
You can see that in order to perform rotations, the node structure in red-black
trees requires parent pointers. Code to perform a left rotation is shown in
Example 5-10; the implementation for right rotation is similar. You can find in
(Cormen et al. 2001) the details on why therotateLeftandrotateRightimple-
mentations work.
Notice that the rotations maintain the binary search tree property because the
ordering of nodes is unchanged. Once the new value is inserted into the red-black
tree, the tree updates itself to restore conditions 4 and 5 of red-black trees.
Figure 5-12. Red-black node rotations
Example 5-10. Java implementation of rotating a node left
protected void rotateLeft(BalancedBinaryNode<K,V> p) {
BalancedBinaryNode<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use
Licensed by
Ming Yi