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

1 public static void testRank( int N )
2 {
3 TreeSet<Integer> t = new TreeSet<Integer>( );
4
5 for( int i = 1; i <= N; i++ )
6 t.add( i );
7
8 for( int i = 1; i <= N; i++ )
9 if( t.headSet( i, true ).size( ) != i )
10 throw new IllegalStateException( );
11 }

figure 19.90
Tests the speed of a
rank computation
(Exercise 19.41).

use java . util , but if Exercise 19.38 is implemented reasonably, you
should be able to have your code be comparable to the Figure 7.20
implementation.

Extend Exercise 19.38 to add code to check for structural modifications
to the primary ArrayList . A structural modification to the primary
ArrayList invalidates all the sublists. Then add checks for structural
modifications to a sublist, which invalidates all descendent sublists.

19.40

The headSet method can be used to obtain the rank of a value x in
TreeSet t : t . headSet ( x , true ). size () . However, there are no guaran-
tees that this is efficient. Implement the code in Figure 19.90 and test
the running time for various values of N . What can you say about the
cost of obtaining the rank of a value x ? Describe how to maintain the
TreeSet and the views so the cost of size , and thus the cost to compute
a rank is O ( log N ).

19.41

Implement a B-tree that works in main memory.

19.42

Implement a B-tree that works for disk files.

19.43

references

More information on binary search trees, and in particular the mathematical
properties of trees, is available in [18] and [19].
Several papers deal with the theoretical lack of balance caused by biased
deletion algorithms in binary search trees. Hibbard [16] proposed the original
deletion algorithm and established that one deletion preserves the randomness
of the trees. A complete analysis has been performed only for trees with three
nodes [17] and four nodes [3]. Eppinger [10] provided early empirical evi-
dence of nonrandomness, and Culberson and Munro [7] and [8] provide some