Using a Balanced Tree to Implement a Map

The map chapter built two implementations of the Map ADT, LinkedMap and ArrayMap. Neither kept its entries in any order, so the only way to find a key was to scan the entries one by one, and get, put, and remove were all $O (n)$ . That chapter’s practice built a third one, SortedArrayMap, which keeps its keys and values in parallel arrays sorted by key. Binary search brought get down to $O (lo g n)$ , but put and remove stayed $O (n)$ , because keeping the arrays in order means shifting entries to open or close a gap.

A binary search tree also keeps its values in order, and it does not need to shift values to do so. Search, add, and remove each follow one path from the root down, so each costs $O (h)$ , where $h$ is the tree’s height. The search tree chapter showed that $h$ can be as large as $n - 1$ . An AVL tree rebalances after every insertion and removal, so its height stays $O (lo g n)$ . So if we build the map on an AVL tree, with a key and its value at each node and the tree ordered by key, we get a map with logarithmic time complexity for all three operations. We call this implementation TreeMap.

TreeMap implements the same Map interface as the map chapter’s implementations, so the same MapTest suite applies.

A Comparable bound on the key

The AVL tree compares keys to decide where a node goes, so the keys must be comparable to one another. The type bound goes on K:

public class TreeMap<K extends Comparable<K>, V> implements Map<K, V> {
  // ...
}

Values are stored and returned but never compared, so V needs no bound, just as in LinkedMap and ArrayMap.

We should also consider that two keys are the same when compareTo returns $0$ rather than relying on equals. I assume that the user will ensure that the compareTo method is consistent with the equals method.