A Rotation Is Just Re-Hanging Three Subtrees, and the Order Never Changes

The insert-order lab ends on a problem it does not solve. A binary search tree built from sorted input degenerates into a linked list — and sorted is the order data most often arrives in. That page names self-balancing trees as the fix and says how they work belongs elsewhere. This is elsewhere.

The mechanism is smaller than its reputation. An AVL tree does an ordinary search-tree insertion, and then checks one number on the way back up.

The number is the balance factor

For any node, the balance factor is the height of its left subtree minus the height of its right. Allowed values are −1, 0 and +1. The instant an insertion pushes some node to −2 or +2, that node’s subtrees get rearranged until it is back in range.

Insert with rebalancing off and then on. The small number beside each node is its balance factor.

Same seven values. Same order. Seven levels against three — and three is the optimum that the first lab asked you to hunt for by hand. On sorted input, which is exactly the input where no human would have found it.

What a rotation actually does

Every treatment of this topic drowns in four case names before establishing what the operation is. A rotation re-hangs three subtrees around two nodes so that one side becomes shorter and the other becomes longer.

The critical property is what it does not change. Watch the in-order traversal row while the picture rearranges: it never moves. The tree still holds the same values in the same left-to-right order — only the depths differ. That is not a pleasant side effect, it is the entire justification. An operation that reshuffled the ordering would have broken the search tree; one that preserves it is free to reshape as violently as it likes.

Once that is clear, the four cases stop being arbitrary:

• left-left — too heavy on the left, and the weight is on the left child’s left. One rotation to the right.
• right-right — the mirror image. One rotation to the left.
• left-right — too heavy on the left, but the weight is on the left child’s right. One rotation cannot reach it, so rotate the child left first to turn it into a left-left, then rotate right.
• right-left — the mirror image again.

There are only two shapes: the weight is on the outside (one rotation) or on the inside (rotate to move it outside, then rotate). The four names are two ideas and a mirror.

What staying balanced costs

def h(node):
    return node["h"] if node else 0


def refresh(node):
    node["h"] = 1 + max(h(node["left"]), h(node["right"]))


def balance(node):
    return h(node["left"]) - h(node["right"]) if node else 0


def rotate_right(y):
    x = y["left"]
    y["left"] = x["right"]
    x["right"] = y
    refresh(y)
    refresh(x)
    return x


def rotate_left(x):
    y = x["right"]
    x["right"] = y["left"]
    y["left"] = x
    refresh(x)
    refresh(y)
    return y


def plain_height(values):
    """Height of the plain BST these values build. Iterative on purpose: sorted input makes a
    chain, and recursing down a 1023-node chain overflows the stack in a browser."""
    root, tallest = None, 0
    for value in values:
        if root is None:
            root, tallest = {"v": value, "left": None, "right": None}, 1
            continue
        node, depth = root, 1
        while True:
            side = "left" if value < node["v"] else "right"
            depth += 1
            if node[side] is None:
                node[side] = {"v": value, "left": None, "right": None}
                break
            node = node[side]
        tallest = max(tallest, depth)
    return tallest


def avl_insert(node, value, counter):
    """Ordinary BST insert, then ONE rebalance on the way back up."""
    if node is None:
        return {"v": value, "left": None, "right": None, "h": 1}
    side = "left" if value < node["v"] else "right"
    node[side] = avl_insert(node[side], value, counter)
    refresh(node)
    b = balance(node)
    if b > 1 and value < node["left"]["v"]:
        counter[0] += 1
        return rotate_right(node)                    # left-left: one rotation
    if b < -1 and value > node["right"]["v"]:
        counter[0] += 1
        return rotate_left(node)                     # right-right: one rotation
    if b > 1:
        counter[0] += 2
        node["left"] = rotate_left(node["left"])     # left-right: two
        return rotate_right(node)
    if b < -1:
        counter[0] += 2
        node["right"] = rotate_right(node["right"])  # right-left: two
        return rotate_left(node)
    return node


def is_balanced(node):
    if node is None:
        return True
    return abs(balance(node)) <= 1 and is_balanced(node["left"]) and is_balanced(node["right"])


print(f"{'values':>7}  {'plain BST':>9}  {'AVL':>4}  {'rotations':>9}  {'AVL balanced':>12}")
for n in (7, 15, 63, 1023):
    values = list(range(1, n + 1))           # sorted input: the worst case for a plain tree
    counter, avl = [0], None
    for v in values:
        avl = avl_insert(avl, v, counter)
    print(f"{n:>7}  {plain_height(values):>9}  {h(avl):>4}  {counter[0]:>9}  {str(is_balanced(avl)):>12}")

 values  plain BST   AVL  rotations  AVL balanced
      7          7     3          4          True
     15         15     4         11          True
     63         63     6         57          True
   1023       1023    10       1013          True

At 1,023 sorted values the plain tree is 1,023 levels deep — a linked list — and the AVL tree is 10, the theoretical minimum. It cost 1,013 rotations across 1,023 insertions, so roughly one rotation per insertion, each of which is a handful of pointer writes.

That is the trade in full. Insertions get slightly more expensive and gain a worst case; every lookup for the rest of the structure’s life goes from up to 1,023 comparisons to at most 10. The last column checks the balance invariant actually holds on every node, because a cheaper tree that was not balanced would not be a cheaper tree, it would be a broken one.

When you would not use one

Balanced trees are not the automatic answer. If you only need exact lookup and never need order, a hash table is faster and simpler. If your data genuinely arrives in random order, a plain search tree is already about 1.39 × log₂(n) deep on average and costs nothing to maintain.

The case for balancing is precisely the case the first lab set up: you do not control the input order, and one bad order is catastrophic rather than merely unlucky. Sorted input is not a rare accident — it is what you get from a database export, a sorted file, or an auto-incrementing id.

What this page simplifies

• Insertion only. Deletion from an AVL tree also rebalances and can cascade rotations all the way to the root, where an insertion never needs more than one fix.
• AVL, not red-black. Red-black trees keep a looser invariant, so they rotate less on write and sit slightly deeper on read. Most standard-library ordered maps use red-black or a B-tree variant for that reason.
• Rotations, not seconds. Rotation counts are deterministic. Real cost also includes the extra height field on every node and the cache behaviour of pointer-chasing, neither of which is measured here.
• The balance factor is stored as a height. Real implementations often store the factor itself in two bits rather than a full integer height, which changes the bookkeeping but not the idea.