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

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 */
7 private AANode<AnyType> remove( AnyType x, AANode<AnyType> t )
8 {
9 if( t != nullNode )
10 {
11 // Step 1: Search down the tree and
12 // set lastNode and deletedNode
13 lastNode = t;
14 if( compare( x, t.element ) < 0 )
15 t.left = remove( x, t.left );
16 else
17 {
18 deletedNode = t;
19 t.right = remove( x, t.right );
20 }
21
22 // Step 2: If at the bottom of the tree and
23 // x is present, we remove it
24 if( t == lastNode )
25 {
26 if( deletedNode == nullNode ||
27 compare( x, deletedNode.element ) != 0 )
28 return t; // Item not found; do nothing
29 deletedNode.element = t.element;
30 t = t.right;
31 theSize--;
32 modCount++;
33 }
34
35 // Step 3: Otherwise, we are not at the bottom; rebalance
36 else
37 if( t.left.level < t.level - 1 || t.right.level < t.level - 1 )
38 {
39 if( t.right.level > --t.level )
40 t.right.level = t.level;
41 t = skew( t );
42 t.right = skew( t.right );
43 t.right.right = skew( t.right.right );
44 t = split( t );
45 t.right = split( t.right );
46 }
47 }
48 return t;
49 }
figure 19.73
Private remove method for TreeSet