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

52 public boolean add( AnyType x )
53 { /* Figure 19.71 */ }
54 private AANode<AnyType> insert( AnyType x, AANode<AnyType> t )
55 { /* Figure 19.71 */ }
56
57 private AANode<AnyType> deletedNode;
58 private AANode<AnyType> lastNode;
59
60 public boolean remove( Object x )
61 { /* Figure 19.72 */ }
62 private AANode<AnyType> remove( AnyType x, AANode<AnyType> t )
63 { /* Figure 19.73 */ }
64 public void clear( )
65 { /* Figure 19.72 */ }
66
67 public Iterator<AnyType> iterator( )
68 { return new TreeSetIterator( ); }
69
70 private static <AnyType> AANode<AnyType> skew( AANode<AnyType> t )
71 { /* Same as in Figure 19.66 */ }
72 private static <AnyType> AANode<AnyType> split( AANode<AnyType> t )
73 { /* Same as in Figure 19.66 */ }
74 private static <AnyType> AANode<AnyType> rotateWithLeftChild( AANode<AnyType> k2 )
75 { /* Same as usual */ }
76 private static <AnyType> AANode<AnyType> rotateWithRightChild( AANode<AnyType> k1 )
77 { /* Same as usual */ }
78 }
Figure 19.68b
TreeSet class skeleton ( continued )
inserted, whereas this insert returns immediately, this version of insert
maintains the size and modCount data members, and this new version uses a
comparator.
The constructors and comparator accessor for the TreeSet class are
shown in Figure 19.69. The private helper, copyFrom , is also shown.
Figure 19.70 implements the public getMatch , which is a nonstandard method
(that is used to help out with TreeMap later on). The private find method is
identical to the one in Section 19.6. The compare method uses the comparator
if one was provided; otherwise it assumes that the parameters are Comparable
and uses their compareTo method. If no comparator was provided, and the
parameters are not themselves Comparable , then a ClassCastException will be
thrown, which is a very reasonable action for this situation.
The public add method is shown in Figure 19.71. It simply calls the pri-
vate insert method, which is similar to the previously seen code in Section
19.6. Observe that add succeeds if and only if the size of the set changes.