Exercises - Algorithms - Java Programming Language

Implement an efficient method that rebalances BSTs that do not have a count field in their nodes.
Modify the standard BST insertion method in Program 12.15 to use Program 13.1 to rebalance the tree each time that the number of items in the symbol table reaches a power of 2. Compare the running time of your program with that of Program 12.15 for the tasks of (i) building a tree from N random keys and (ii) searching for N random keys in the resulting tree, for N = 10³, 10⁴, 10⁵, and 10⁶.
Estimate the number of comparisons used by your program from Exercise 13.2 when inserting an increasing sequence of N keys into a symbol table.
13.4 Show that Program 13.1 runs in time proportional to N log N for a degenerate tree. Then give as weak a condition on the tree as you can that implies that the program runs in linear time.
Modify the standard BST insertion method in Program 12.15 to partition about the median any node encountered that has less than one-quarter of its nodes in one of its subtrees. Compare the running time of your program with that of Program 12.15 for the tasks of (i) building a tree from N random keys and (ii) searching for N random keys in the resulting tree, for N = 10³, 10⁴, 10⁵, and 10⁶.
Estimate the number of comparisons used by your program from Exercise 13.5 when inserting an increasing sequence of N keys into a symbol table.
13.7 Extend your implementation in Exercise 13.5 to rebalance in the same way while performing the remove operation. Run experiments to determine whether the height of the tree grows as a long sequence of alternating random insertions and deletions are made in a random tree of N nodes, for N = 10, 100, and 1000, and for N² insertion-deletion pairs for each N.