Suppose we wish to support a new method count range(start, stop) that
determines how many keys of a sorted map fall in the specified range. We
could clearly implement this in
O(s+h) time by adapting our approach to
find range. Describe how to modify the search tree structure to support
O(h) worst-case time for count range.
If the approach described in the previous problem were implemented as
part of the TreeMap class, what additional modifications (if any) would be
necessary to a subclass such as AVLTreeMap in order to maintain support
for the new method?
Q222
Draw a schematic of an AVL tree such that a single remove operation
could require ∑(logn) trinode restructurings (or rotations) from a leaf to
the root in order to restore the height-balance property.
If we maintain a reference to the position of the leftmost node of a binary
search tree, then operation find min can be performed in
O(1) time.
Describe how the implementation of the other map methods need to be
modified to maintain a reference to the leftmost position.