The Height Cache

In TreeMap, every node caches the height of its subtree in a field. height(node) reads that field and returns $- 1$ for null. updateHeight(node) recomputes it from the children’s cached heights. On the way back up, the recursive put calls updateHeight and then rebalance on each node, and each rotation updates the heights it changes.

Solution

The cost grows linearly with $n$ , even though the tree is balanced. The search in containsKey and the trip down to the new leaf are $O (lo g n)$ , and each rotation is $O (1)$ . The slow part is the balance factor. Each rebalance on the way back up calls height on both children, and a recursive height visits every node in the subtree it is given. The walk back up always ends at the root, so the last rebalance alone visits all $n - 1$ nodes below the root.

Solution

$O (lo g n)$ . It visits the $O (lo g n)$ nodes on one path, and each costs one $O (1)$ updateHeight and one $O (1)$ rebalance on the way back up.

Solution

Inside the rotated subtree, only the heights of root and child. They are the only nodes whose children changed. Every subtree below them kept its shape, so its root’s height is still correct.