Tracing the TreeMap

Here is a sequence of operations on a TreeMap with integer keys and string values. Each node below is drawn as key:value.

We start with new TreeMap<>():

(empty map — root is null, size is 0)

put(4, "w") finds an empty tree, so the new pair becomes the root, and the call returns true. The size is 1.

╭─────╮
│ 4:w │
╰─────╯

put(9, "x") goes to the right of 4. 4 is now right-heavy, with a balance factor of $-1$, which is allowed, so nothing rotates. The size is 2.

╭─────╮
│ 4:w │
╰──┬──╯
   └───┐
    ╭──┴──╮
    │ 9:x │
    ╰─────╯

put(6, "y") places 6 as 9’s left child. Now 4 has a balance factor of $-2$, and its right child 9 is left-heavy, so rebalance applies a right-left rotation and 6 becomes the root. The size is 3.

      ╭─────╮
      │ 6:y │
      ╰──┬──╯
   ┌─────┴─────┐
╭──┴──╮     ╭──┴──╮
│ 4:w │     │ 9:x │
╰─────╯     ╰─────╯

put(9, "z") finds key 9 already there. It overwrites the value, from x to z, and returns false. The shape and the size do not change.

      ╭─────╮
      │ 6:y │
      ╰──┬──╯
   ┌─────┴─────┐
╭──┴──╮     ╭──┴──╮
│ 4:w │     │ 9:z │
╰─────╯     ╰─────╯

get(4) returns "w", and get(5) returns null. Neither changes the tree.

remove(9) finds key 9 at a leaf and unlinks it. 6 is now left-heavy, with a balance factor of $1$, which is allowed, so no rotation is needed. The size is 2.

    ╭─────╮
    │ 6:y │
    ╰──┬──╯
   ┌───┘
╭──┴──╮
│ 4:w │
╰─────╯

Finally, remove(7) does not find the key, so it returns false and changes nothing.