Java Reference
In-Depth Information
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.
Search WWH ::
Custom Search