Java Reference
In-Depth Information
1 package weiss.nonstandard;
2
3 // BinarySearchTreeWithRank class
4 //
5 // CONSTRUCTION: with no initializer
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // Comparable findKth( k )--> Return kth smallest item
9 // All other operations are inherited
10 // ******************ERRORS********************************
11 // IllegalArgumentException thrown if k is out of bounds
12
13 public class BinarySearchTreeWithRank<AnyType extends Comparable<? super AnyType>>
14 extends BinarySearchTree<AnyType>
15 {
16 private static class BinaryNodeWithSize<AnyType> extends BinaryNode<AnyType>
17 {
18 BinaryNodeWithSize( AnyType x )
19 { super( x ); size = 0; }
20
21 int size;
22 }
23
24 /**
25 * Find the kth smallest item in the tree.
26 * @param k the desired rank (1 is the smallest item).
27 * @return the kth smallest item in the tree.
28 * @throws IllegalArgumentException if k is less
29 * than 1 or more than the size of the subtree.
30 */
31 public AnyType findKth( int k )
32 { return findKth( k, root ).element; }
33
34 protected BinaryNode<AnyType> findKth( int k, BinaryNode<AnyType> t )
35 { /* Figure 19.15 */ }
36 protected BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> tt )
37 { /* Figure 19.16 */ }
38 protected BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> tt )
39 { /* Figure 19.18 */ }
40 protected BinaryNode<AnyType> removeMin( BinaryNode<AnyType> tt )
41 { /* Figure 19.17 */ }
42 }
figure 19.14
The BinarySearchTreeWithRank class skeleton
The findKth operation shown in Figure 19.15 is written recursively,
although clearly it need not be. It follows the algorithmic description line for
line. The test against null at line 10 is necessary because k could be invalid.
 
Search WWH ::




Custom Search