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