Java Reference
In-Depth Information
nullNode
sentinel; however, we do not need a pseudoroot. The constructor
allocates
nullNode
, as for red-black trees, and has
root
reference at it. The
nullNode
is at level 0. The routines use private helpers.
The
insert
method is shown in Figure 19.65. As mentioned earlier in this
section, it is nearly identical to the recursive binary search tree
insert
. The
only difference is that it adds a call to
skew
followed by a call to
split
. In
Figure 19.66
skew
and
split
are easily implemented, using the already exist-
ing tree rotations. Finally,
remove
is shown in Figure 19.67.
To help us out, we keep two instance variables,
deletedNode
and
last-
Node
. When we traverse a right child, we adjust
deletedNode
. Because we
call
remove
recursively until we reach the bottom (we do not test for equal-
ity on the way down), we are guaranteed that, if the item to be removed is
in the tree,
deletedNode
will reference the node that contains it. Note that
this technique can be used in the
find
procedure to replace the three-way
comparisons done at each node with two-way comparisons at each node
1
/**
2
* Internal method to insert into a subtree.
3
* @param x the item to insert.
4
* @param t the node that roots the tree.
5
* @return the new root.
6
* @throws DuplicateItemException if x is already present.
7
*/
8
private AANode<AnyType> insert( AnyType x, AANode<AnyType> t )
9
{
10
if( t == nullNode )
11
t = new AANode<AnyType>( x, nullNode, nullNode );
12
else if( x.compareTo( t.element ) < 0 )
13
t.left = insert( x, t.left );
14
else if( x.compareTo( t.element ) > 0 )
15
t.right = insert( x, t.right );
16
else
17
throw new DuplicateItemException( x.toString( ) );
18
19
t = skew( t );
20
t = split( t );
21
return t;
22
}
figure 19.65
The
insert
routine for
the
AATree
class
Search WWH ::
Custom Search