TreeMap Design and Costs

TreeMap implements the Map ADT (put, get, remove, containsKey, size) as an AVL tree ordered by key. Each node holds a key and its value.

Solution

Unsorted linked list: get is $O (n)$ and put is $O (n)$ . Both scan the entries to find the key.
Sorted arrays: get is $O (lo g n)$ , by binary search. put is $O (n)$ , because a new key shifts the entries after it.
TreeMap: get and put are both $O (lo g n)$ . Each follows one path from the root, and the AVL tree’s height is $O (lo g n)$ .

Solution

The tree compares keys to decide where each node goes, so keys need compareTo. Values are stored and returned but never compared.

Solution

put and remove. put can add a node, which can make a subtree taller, and remove can take one out, which can make a subtree shorter. get and containsKey only follow one path down from the root. A put that replaces the value of a key already in the map does not change the shape either.