Java Reference
In-Depth Information
1 /**
2 * Internal routine that is called during an insertion
3 * if a node has two red children. Performs flip and rotations.
4 * @param item the item being inserted.
5 */
6 private void handleReorient( AnyType item )
7 {
8 // Do the color flip
9 current.color = RED;
10 current.left.color = BLACK;
11 current.right.color = BLACK;
12
13 if( parent.color == RED ) // Have to rotate
14 {
15 grand.color = RED;
16 if( ( compare( item, grand ) < 0 ) != ( compare( item, parent ) < 0 ) )
17 parent = rotate( item, grand ); // Start dbl rotate
18 current = rotate( item, great );
19
20 current.color = BLACK;
21 }
22 header.right.color = BLACK; // Make root black
23 }
figure 19.48
The handleReorient routine, which is called if a node has two red children or when a new node is inserted
At lines 11 and 14 we see the call to compare , which is used since the
header might be one of the nodes involved in the comparison. The value in the
header is logically -
, but is actually null . The implementation of compare
ensures that the value in the header compares as less than any other value.
compare is also shown in Figure 19.47.
The code used to perform a single rotation is shown in the rotate method
in Figure 19.49. Because the resultant tree must be attached to a parent, rotate
takes the parent node as a parameter. Rather than keep track of the type of
rotation (left or right) as we descend the tree, we pass item as a parameter. We
expect very few rotations during the insertion, so doing it this way is not only
simple but is actually faster.
The handleReorient routine calls rotate as necessary to perform either a
single or double rotation. As a double rotation is just two single rotations, we
can test whether we have an inside case, and if so, do an extra rotation
between the current node and its parent (bypassing the grandparent to rotate ).
In either case we rotate between the parent and grandparent (by passing the
great-grandparent to rotate ). This action is succinctly coded in lines 16-17 of
Figure 19.48.
The rotate method
has four possibili-
ties. The ?: opera-
tor collapses the
code but is logi-
cally equivalent to
an if / else test.
Search WWH ::




Custom Search