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

case of dealing with the root (which, among other things, has no parent). To
remove special cases, we use two sentinels.

We remove special
cases by using a
sentinel for the
null node and a
pseudoroot. Doing
so requires minor
modifications of
almost every
routine.

We use nullNode in place of a null link; nullNode will always be col-
ored black.

n

We use header as a pseudoroot; it has a key value of - ∞ and a right
link to the real root.

n

Therefore even basic routines such as isEmpty need to be altered. Conse-
quently, inheriting from BinarySearchTree does not make sense, and we write
the class from scratch. The RedBlackNode class, which is nested in RedBlack-
Tree , is shown in Figure 19.42 and is straightforward. The RedBlackTree class
skeleton is shown in Figure 19.43. Lines 55 and 56 declare the sentinels that
we discussed previously. Four references— current , parent , grand , and great —
are used in the insert routine. Their placement at lines 62-65 allows them to
be shared by insert and the handleReorient routine. The remove method is
unimplemented.
The remaining routines are similar to their BinarySearchTree counterparts,
except that they have different implementations because of the sentinel nodes.
The constructor could be provided with the value of - ∞ , to initialize the
header node. We do not do that. The alternative is to use the compare method,

On the way down,
we maintain refer-
ences to the
current, parent,
grandparent, and
great-grandparent
nodes.

1 private static class RedBlackNode<AnyType>
2 {
3 // Constructors
4 RedBlackNode( AnyType theElement )
5 {
6 this( theElement, null, null );
7 }
8
9 RedBlackNode( AnyType theElement, RedBlackNode<AnyType> lt,
10 RedBlackNode<AnyType> rt )
11 {
12 element = theElement;
13 left = lt;
14 right = rt;
15 color = RedBlackTree.BLACK;
16 }
17
18 AnyType element; // The data in the node
19 RedBlackNode<AnyType> left; // Left child
20 RedBlackNode<AnyType> right; // Right child
21 int color; // Color
22 }

figure 19.42
The RedBlackNode
class