Binary search trees - Data Structures and Problem Solving Using Java - page 722

figure 19.43b
The RedBlackTree
class skeleton
( continued )

52 private static class RedBlackNode<AnyType>
53 { /* Figure 19.42 */ }
54
55 private RedBlackNode<AnyType> header;
56 private RedBlackNode<AnyType> nullNode;
57
58 private static final int BLACK = 1; // BLACK must be 1
59 private static final int RED = 0;
60
61 // Used in insert routine and its helpers
62 private RedBlackNode<AnyType> current;
63 private RedBlackNode<AnyType> parent;
64 private RedBlackNode<AnyType> grand;
65 private RedBlackNode<AnyType> great;
66 }

defined at lines 38 and 39, where appropriate. A constructor is shown in
Figure 19.44. The constructor allocates nullNode and then the header and sets
the header's left and right links to nullNode .

Figure 19.45 shows the simplest change that results from the use of the sen-
tinels. The test against null needs to be replaced with a test against nullNode .
For the find routine shown in Figure 19.46 we use a common trick.
Before we begin the search, we place x in the nullNode sentinel. Thus we are
guaranteed to match x eventually, even if x is not found. If the match occurs at
nullNode , we can tell that the item was not found. We use this trick in the
insert procedure.
The insert method follows directly from our description and is shown in
Figure 19.47. The while loop encompassing lines 11 to 20 descends the tree
and fixes nodes that have two red children by calling handleReorient , as shown
in Figure 19.48. To do so, it keeps track of not only the current node but also
the parent, grandparent, and great-grandparent. Note that after a rotation the

Tests against null
are replaced by
tests against
nullNode .

When performing a
find operation, we
copy x into the
nullNode sentinel to
avoid extra tests.

figure 19.44
The RedBlackTree
constructor

1 /**
2 * Construct the tree.
3 */
4 public RedBlackTree( )
5 {
6 nullNode = new RedBlackNode<AnyType>( null );
7 nullNode.left = nullNode.right = nullNode;
8 header = new RedBlackNode<AnyType>( null );
9 header.left = header.right = nullNode;
10 }