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

1 /**
2 * Adds an item to this collection.
3 * @param x any object.
4 * @return true if this item was added to the collection.
5 */
6 public boolean add( AnyType x )
7 {
8 int oldSize = size( );
9
10 root = insert( x, root );
11 return size( ) != oldSize;
12 }
13
14 /**
15 * Internal method to insert into a subtree.
16 * @param x the item to insert.
17 * @param t the node that roots the tree.
18 * @return the new root.
19 */
20 private AANode<AnyType> insert( AnyType x, AANode<AnyType> t )
21 {
22 if( t == nullNode )
23 {
24 t = new AANode<AnyType>( x, nullNode, nullNode );
25 modCount++;
26 theSize++;
27 }
28

figure 19.71
Insertion methods for
TreeSet

else

{ 29

int result = compare( x, t.element );

30

31
32 if( result < 0 )
33 t.left = insert( x, t.left );
34 else if( result > 0 )
35 t.right = insert( x, t.right );
36 else
37 return t;
38

}

39
40 t = skew( t );
41 t = split( t );
42 return t;
43 }

Figure 19.72 shows the public remove and clear methods. The public
remove calls a private remove , shown in Figure 19.73, which is very similar to
the code in Section 19.6. The main changes are the use of a comparator (via
method compare ), and the additional code at lines 31 and 32.