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

1 /**
2 * Internal method to remove from a subtree.
3 * @param x the item to remove.
4 * @param t the node that roots the tree.
5 * @return the new root.
6 * @throws ItemNotFoundException if x is not found.
7 */
8 private AANode<AnyType> remove( AnyType x, AANode<AnyType> t )
9 {
10 if( t != nullNode )
11 {
12 // Step 1: Search down the tree and
13 // set lastNode and deletedNode
14 lastNode = t;
15 if( x.compareTo( t.element ) < 0 )
16 t.left = remove( x, t.left );
17 else
18 {
19 deletedNode = t;
20 t.right = remove( x, t.right );
21 }
22
23 // Step 2: If at the bottom of the tree and
24 // x is present, remove it
25 if( t == lastNode )
26 {
27 if( deletedNode == nullNode ||
28 x.compareTo( deletedNode.element ) != 0 )
29 throw new ItemNotFoundException( x.toString( ) );
30 deletedNode.element = t.element;
31 t = t.right;
32 }
33
34 // Step 3: Otherwise, we are not at the bottom; rebalance
35 else
36 if( t.left.level < t.level - 1 || t.right.level < t.level - 1 )
37 {
38 if( t.right.level > --t.level )
39 t.right.level = t.level;
40 t = skew( t );
41 t.right = skew( t.right );
42 t.right.right = skew( t.right.right );
43 t = split( t );
44 t.right = split( t.right );
45 }
46 }
47 return t;
48 }
figure 19.67
The remove method for AA-trees