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

1 /**
2 * Internal method to print a subtree in sorted order.
3 * @param t the node that roots the tree.
4 */
5 private void printTree( RedBlackNode<AnyType> t )
6 {
7 if( t != nullNode )
8 {
9 printTree( t.left );
10 System.out.println( t.element );
11 printTree( t.right );
12 }
13 }

figure 19.45
The printTree method
for the RedBlackTree
class

1 /**
2 * Find an item in the tree.
3 * @param x the item to search for.
4 * @return the matching item or null if not found.
5 */
6 public AnyType find( AnyType x )
7 {
8 nullNode.element = x;
9 current = header.right;
10
11 for( ; ; )
12 {
13 if( x.compareTo( current.element ) < 0 )
14 current = current.left;
15 else if( x.compareTo( current.element ) > 0 )
16 current = current.right;
17 else if( current != nullNode )
18 return current.element;
19 else
20 return null;
21 }
22 }

figure 19.46
The RedBlackTreefind
routine. Note the use
of header and
nullNode .

The code is rela-
tively compact for
the number of
cases involved and
the fact that the
implementation is
nonrecursive. For
these reasons the
red-black tree
performs well.

values stored in the grandparent and great-grandparent are no longer correct.
However, they will be restored by the time they are next needed. When the
loop ends, either x is found (as indicated by current!=nullNode ) or x is not
found (as indicated by current==nullNode ). If x is found, we throw an excep-
tion at line 24. Otherwise, x is not already in the tree, and it needs to be made
a child of parent . We allocate a new node (as the new current node), attach it
to the parent, and call handleReorient at lines 25-32.