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

1 /**
2 * Internal method to find kth smallest item in a subtree.
3 * @param k the desired rank (1 is the smallest item).
4 * @return the node containing the kth smallest item in the subtree.
5 * @throws IllegalArgumentException if k is less
6 * than 1 or more than the size of the subtree.
7 */
8 protected BinaryNode<AnyType> findKth( int k, BinaryNode<AnyType> t )
9 {
10 if( t == null )
11 throw new IllegalArgumentException( );
12 int leftSize = ( t.left != null ) ?
13 ((BinaryNodeWithSize<AnyType>) t.left).size : 0;
14
15 if( k <= leftSize )
16 return findKth( k, t.left );
17 if( k == leftSize + 1 )
18 return t;
19 return findKth( k - leftSize - 1, t.right );
20 }

figure 19.15
The findKth operation for a search tree with order statistics

Lines 12 and 13 compute the size of the left subtree. If the left subtree exists,
accessing its size member gives the required answer. If the left subtree does
not exist, its size can be taken to be 0. Note that this test is performed after we
are sure that t is not null .
The insert operation is shown in Figure 19.16. The potentially tricky
part is that, if the insertion call succeeds, we want to increment t 's size
member. If the recursive call fails, t 's size member is unchanged and an
exception should be thrown. In an unsuccessful insertion, can some sizes
change? The answer is no; size is updated only if the recursive call succeeds
without an exception. Note that when a new node is allocated by a call to
new , the size member is set to 0 by the BinaryNodeWithSize constructor, and
then incremented at line 20.
Figure 19.17 shows that the same trick can be used for removeMin . If the
recursive call succeeds, the size member is decremented; if the recursive call
fails, size is unchanged. The remove operation is similar and is shown in
Figure 19.18.

The findKth opera-
tion is easily imple-
mented once the
size members are
known.

The insert and
remove operations
are potentially tricky
because we do not
update the size
information if the
operation is unsuc-
cessful.