The TreeMap

This chapter is about TreeMap, an implementation of the Map ADT as an AVL tree ordered by key. Its get, containsKey, put, and remove all run in $O(\log n)$.

After reading this chapter, you should be able to:

• Implement TreeMap by adapting the search tree chapter’s BinarySearchTree, with each node holding a key and a value and the tree ordered by a Comparable key
• Implement the four rotations as methods that return the new root of the rotated subtree
• Implement a rebalance helper that chooses the rotation from two balance factors
• Add balancing to the recursive put and remove by rebalancing each node on the recursion’s way back up
• Cache each node’s height and keep it correct through every change, so put and remove run in $O(\log n)$ instead of $O(n)$
• Trace a sequence of TreeMap operations, including the call stack of a recursive put and the rotation it triggers
• Iterate a TreeMap’s keys and entries in ascending key order with the search tree’s in-order iterator
• Choose among the linked, array, sorted-array, and tree implementations of the Map ADT for a given workload, from their operation costs and memory

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Using a Balanced Tree to Implement a Map
2. Starting from the Search Tree
3. Implementing get and containsKey
4. Where Balancing Goes
5. Rotations in Code
6. The Rebalance Helper
7. put, First Version
8. Why Recomputing Height Is Slow
9. Caching the Height
10. Rotations Keep the Height
11. put, Final Version
12. Implementing remove
13. Iterating in Key Order
14. Tracing the TreeMap
15. The Complete TreeMap
16. Four Maps, Side by Side