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

1 /**
2 * Internal method to insert into a subtree.
3 * @param x the item to insert.
4 * @param tt the node that roots the tree.
5 * @return the new root.
6 * @throws DuplicateItemException if x is already present.
7 */
8 protected BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> tt )
9 {
10 BinaryNodeWithSize<AnyType> t = (BinaryNodeWithSize<AnyType>) tt;
11
12 if( t == null )
13 t = new BinaryNodeWithSize<AnyType>( x );
14 else if( x.compareTo( t.element ) < 0 )
15 t.left = insert( x, t.left );
16 else if( x.compareTo( t.element ) > 0 )
17 t.right = insert( x, t.right );
18 else
19 throw new DuplicateItemException( x.toString( ) );
20 t.size++;
21 return t;
22 }
figure 19.16
The insert operation for a search tree with order statistics
1 /**
2 * Internal method to remove the smallest item from a subtree,
3 * adjusting size fields as appropriate.
4 * @param t the node that roots the tree.
5 * @return the new root.
6 * @throws ItemNotFoundException if the subtree is empty.
7 */
8 protected BinaryNode<AnyType> removeMin( BinaryNode<AnyType> tt )
9 {
10 BinaryNodeWithSize<AnyType> t = (BinaryNodeWithSize<AnyType>) tt;
11
12 if( t == null )
13 throw new ItemNotFoundException( );
14 if( t.left == null )
15 return t.right;
16
17 t.left = removeMin( t.left );
18 t.size--;
19 return t;
20 }
figure 19.17
The removeMin operation for a search tree with order statistics