Why Recomputing Height Is Slow

We built the map on an AVL tree so that put would be $O (lo g n)$ . Let’s check whether the first version of put gets there. We add up its work one piece at a time.

The public method first calls containsKey. That is one search down the tree, and assuming the tree is balanced, it is $O (lo g n)$ .

Then the helper goes down one path, from the root to the empty spot where the new leaf goes. The path has $O (lo g n)$ nodes under the same assumption. At each node, the helper does one compareTo and makes one recursive call, which is $O (1)$ per node. Creating the leaf is $O (1)$ . So the trip down is $O (lo g n)$ .

On the way back up, each call on the path runs rebalance(node). A rotation changes only a few links, so it is $O (1)$ . But before rebalance can choose a rotation, it calls balanceFactor, and balanceFactor calls height on both children. How much work is that?

Count it on the put(4) from the last page. Here is the tree right after 4 goes in, before any repair:

              ╭────╮
              │ 14 │
              ╰──┬─╯
          ┌──────┴──────┐
       ╭──┴─╮        ╭──┴─╮
       │ 11 │        │ 17 │
       ╰──┬─╯        ╰──┬─╯
      ┌───┘             └───┐
    ╭─┴─╮                ╭──┴─╮
    │ 7 │                │ 19 │
    ╰─┬─╯                ╰────╯
  ┌───┘
╭─┴─╮
│ 4 │
╰───╯

Each height call visits every node in the subtree it is given. Here is what each rebalance visits, not counting the empty subtrees:

rebalance(7): height(7.left) visits 4, and 7.right is empty. That is $1$ node.
rebalance(11): height(11.left) visits 7 and 4, and 11.right is empty. That is $2$ nodes. 11 is unbalanced, so rebalance also asks for the balance factor of its heavy child 7, which visits 4 again. That makes $3$ .

The rotation at 11 lifts 7, so 14’s left subtree is now 7 with children 4 and 11:

             ╭────╮
             │ 14 │
             ╰──┬─╯
       ┌────────┴────────┐
     ╭─┴─╮            ╭──┴─╮
     │ 7 │            │ 17 │
     ╰─┬─╯            ╰──┬─╯
  ┌────┴────┐            └───┐
╭─┴─╮    ╭──┴─╮           ╭──┴─╮
│ 4 │    │ 11 │           │ 19 │
╰───╯    ╰────╯           ╰────╯

rebalance(14): height(14.left) visits 7, 4, and 11, and height(14.right) visits 17 and 19. That is $5$ nodes, every node in the tree except 14 itself.

The last count is the one that matters the most. The unwinding of recursive calls always ends at the root. rebalance(root) visits every node below the root in the process of calculating the heights to compute the balance factors, which is $n - 1$ nodes. So this one call alone takes at least $n - 1$ steps, and the calls below it add more. The cost of put grows linearly with $n$ . It is not $O (lo g n)$ , even though the tree is balanced.

The Cost of put

The cost of put is $O (n)$ . Each call on the path visits only the subtree under its own node. In a balanced tree, each subtree on the path holds roughly half as many nodes as the one above it. So all the calls together visit about

n + \frac{n}{2} + \frac{n}{4} + \dots < 2 n

nodes. When a node is unbalanced, rebalance also asks for the balance factor of its heavy child. That child is inside the same subtree, so these extra visits at most double the count. The total is $O (n)$ .

Everything else in put is $O (lo g n)$ . The slow part is computing the heights.

The problem is that every call computes the heights from scratch and then throws them away, even though most nodes still have the same height they had a moment ago. The linked list chapter had the same problem with size. It stopped counting the nodes on every call, and kept the count in a field that each change updated. We can do the same here and store each node’s height in the node.