6.1 AVL Trees and Rotations

Prerequisite: Binary Search Tree | Next: Red-Black Tree

A regular BST only maintains order and imposes no shape constraints. This section adds height information to nodes, starting from a tree bent by sequentially inserted data and gradually deriving the four rotations, a complete AVL insertion algorithm, and invariant verification.

1. Why Ordered Input Can Collapse a BST into a Chain

Insert 1, 2, 3, 4, 5 into an ordinary BST in that order and every non-leaf node has only a right child:

1 -> 2 -> 3 -> 4 -> 5

Chapter 5 expressed operation costs in terms of tree height. Here we count height in nodes:

• The height of an empty tree is 0;
• Leaf node height is 1;
• Node height is 1 + max(left height, right height).

In the previous chapter, height was defined by the number of edges. For non-empty trees, the two definitions differ by 1, without affecting asymptotic complexity. The easiest mistake is mixing both conventions in the same code.

After inserting n keys in order, the height of the ordinary BST is n, so finding the last key requires visiting n nodes. AVL adds a local constraint to each node:

abs(height(left) - height(right)) <= 1

Why does a local condition bound the whole tree? Let N(h) be the minimum number of nodes in an AVL tree of height h. To reach height h with as few nodes as possible, its subtrees have heights h-1 and h-2:

N(0) = 0, N(1) = 1
N(h) = 1 + N(h-1) + N(h-2)    (h >= 2)
N(h): 0, 1, 2, 4, 7, 12, ...

This recurrence grows exponentially, like the Fibonacci sequence, so height grows only logarithmically with node count. Operations along one path in a nonempty tree therefore take O(log(n+1)); empty-tree operations take constant time. The MIT AVL lecture notes develop this argument further.

2. The balance factor tells us which way to adjust

Definition:

balance(node) = height(node.left) - height(node.right)

Balance factor	Meaning
1	One level higher on the left, still valid
0	Equal height on both sides
-1	Higher on the right, still valid
>= 2	Left imbalance
<= -2	Right-side imbalance

"Left imbalance" isn't enough to determine rotation. The new key might fall to the left or right of the left child; that's the difference between LL and LR.

3. What connections were affected by one rotation

Right Rotation

        y                     x
       / \                   / \
      x   T3     -->        T1  y
     / \                       / \
    T1 T2                     T2 T3

Execution order:

1. Save x.right, that is T2.
2. Let x.right point to the old root y.
3. Attach T2 to y.left.
4. First update y.height, then update x.height.

Step four has dependencies: after rotation, y is now a child of x. Computing x first would read the old height of y.

An in-order traversal can prove that rotation does not disrupt BST order:

Before rotation: T1, x, T2, y, T3
After rotation: T1, x, T2, y, T3

Left Rotation

A left rotation mirrors the figure: promote the right child and attach its left subtree to the old root's right pointer. The connection and height update dependencies are the same. A right rotation requires a left child; a left rotation requires a right child. The imbalance branches guarantee these preconditions for the internal methods below.

4. Look at each of the four imbalances one by one

The name is read two steps downward from an unbalanced node.

LL: [30, 20, 10]

    30             20
   /              /  \
  20     -->     10  30
 /
10

At 30, the left subtree is two levels taller. The new key lies to the left of its left child, 20. A single right rotation suffices.

RR: [10, 20, 30]

10                 20
  \               /  \
  20     -->     10  30
    \
    30

This mirrors LL and needs one left rotation.

LR: [30, 10, 20]

    30          30             20
   /           /              /  \
  10   -->    20     -->     10  30
    \        /
    20      10

First, straighten the bend in the left child, turning LR into LL; then right-rotate the unbalanced node.

RL: [10, 30, 20]

10          10                 20
  \           \               /  \
  30   -->    20     -->     10  30
  /             \
20              30

It's symmetric with LR.

A practical rule: first check whether the unbalanced node is leaning left or right, then see which side its taller child leans toward. Don't try to guess the name based on a single comparison between the new key and the root.

5. Complete AVL Insertion

The following implementation stores unique integer keys. insert() returns whether a new key was inserted; duplicate keys return False. It checks the int type before comparison, so NaN, which is neither less nor greater than an existing key, cannot be mistaken for a duplicate. The validator checks key bounds, stored heights, and balance factors. Python treats bool as an int subclass, so the set retains the usual True == 1 behavior.

def require_int_key(key):
    if not isinstance(key, int):
        raise TypeError("key must be an integer")

class AVLNode:
    def __init__(self, key):
        require_int_key(key)
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None
        self.size = 0

    @staticmethod
    def _height(node):
        return 0 if node is None else node.height

    def _update(self, node):
        node.height = 1 + max(self._height(node.left), self._height(node.right))

    def _balance(self, node):
        return self._height(node.left) - self._height(node.right)

    def _rotate_right(self, old_root):
        new_root = old_root.left
        middle = new_root.right

        new_root.right = old_root
        old_root.left = middle

        self._update(old_root)
        self._update(new_root)
        return new_root

    def _rotate_left(self, old_root):
        new_root = old_root.right
        middle = new_root.left

        new_root.left = old_root
        old_root.right = middle

        self._update(old_root)
        self._update(new_root)
        return new_root

    def _insert(self, node, key):
        if node is None:
            return AVLNode(key), True

        if key < node.key:
            node.left, inserted = self._insert(node.left, key)
        elif key > node.key:
            node.right, inserted = self._insert(node.right, key)
        else:
            return node, False

        self._update(node)
        balance = self._balance(node)

        if balance > 1:
            if key > node.left.key:              # LR
                node.left = self._rotate_left(node.left)
            return self._rotate_right(node), inserted    # LL / LR

        if balance < -1:
            if key < node.right.key:             # RL
                node.right = self._rotate_right(node.right)
            return self._rotate_left(node), inserted     # RR / RL

        return node, inserted

    def insert(self, key):
        require_int_key(key)
        self.root, inserted = self._insert(self.root, key)
        if inserted:
            self.size += 1
        return inserted

    def inorder(self):
        result = []

        def walk(node):
            if node is None:
                return
            walk(node.left)
            result.append(node.key)
            walk(node.right)

        walk(self.root)
        return result

    def height(self):
        return self._height(self.root)

    def is_valid(self):
        def check(node, low, high):
            if node is None:
                return True, 0
            if (low is not None and node.key <= low) or (
                high is not None and node.key >= high
            ):
                return False, 0

            left_ok, left_height = check(node.left, low, node.key)
            right_ok, right_height = check(node.right, node.key, high)
            expected = 1 + max(left_height, right_height)
            valid = (
                left_ok
                and right_ok
                and node.height == expected
                and abs(left_height - right_height) <= 1
            )
            return valid, expected

        valid, _ = check(self.root, None, None)
        return valid

rotation_cases = {
    "LL": [30, 20, 10],
    "RR": [10, 20, 30],
    "LR": [30, 10, 20],
    "RL": [10, 30, 20],
}

for name, values in rotation_cases.items():
    tree = AVLTree()
    for value in values:
        assert tree.insert(value)
    assert tree.root.key == 20, name
    assert tree.inorder() == [10, 20, 30], name
    assert tree.height() == 2, name
    assert tree.is_valid(), name

ordered = AVLTree()
for value in range(1, 101):
    ordered.insert(value)

assert ordered.inorder() == list(range(1, 101))
assert ordered.height() == 7
assert ordered.is_valid()
assert ordered.insert(50) is False
assert ordered.size == 100

6. Why Insertion Repairs Only One Unbalanced Ancestor

As recursive insertion works backward from leaf to root, it updates the height along the path. Upon encountering the first unbalanced ancestor, a single or double rotation restores that subtree segment to its pre-insertion height. Higher ancestors see no further increase in subtree height, so no additional rotations are needed.

So the behavior of AVL insertion is:

• Search and update along the path, O(h);
• Complete the repair at an unbalanced ancestor;
• A single rotation uses one basic rotation; a double rotation uses two.

Deletion cannot reuse insertion's repair range unchanged. A deletion can shorten a subtree, and its height may continue decreasing after one repair, unbalancing higher ancestors. AVL deletion may therefore rotate at multiple ancestors, although the total work remains O(log n). Amani, Lai, and Tarjan study this difference in rotation costs.

7. Validators Are More Reliable Than Just Looking at Pictures

A tree may appear symmetric, but that doesn't guarantee that the metadata and order are correct. is_valid() checks:

1. Each key is compared within the open interval inherited from ancestors, rather than against direct children alone.
2. The actual calculated height equals the height stored in the node.
3. The difference in height between the left and right subtrees of each node is at most 1.

Checking only the third item can miss stale stored heights. Comparing only parent and child keys can miss a deeper node that violates an ancestor bound.

The validator assumes that child links have no cycles or shared children; it does not handle an arbitrary damaged object graph. It also does not check size; verify that separately with len(tree.inorder()) == tree.size.

8. Common Failures

T2 Disappeared

Overwrite the child pointer during rotation without first saving the middle subtree. In-order traversal will miss a range of keys.

The update order is reversed

The new root depends on the height of the old root. Updating the new root first carries the old value into subsequent balance checks.

Use a new key to determine rotation after deletion

When inserting, you can use the direction of the new key to distinguish among the four shapes. After deletion, that key no longer exists, so you should instead check the balance factor of the higher child itself.

Repeat keys silently increment size

This chapter continues the set semantics from Chapter 5. After the recursive layer returns inserted=False, public methods cannot increment the counter.

9. Complexity Quick Reference

Operation	Time	Extra Space
Search	O(log n)	Iterate O(1); recurse O(log n)
Insert	O(log n)	This implementation uses a recursive stack O(log n)
One rotation	O(1)	O(1)
In-order traversal	O(n)	O(log(n+1)) auxiliary stack, plus a Θ(n) output list
Full verification	O(n)	O(h+1), using the actual height of the tree being checked

The table treats key comparisons as constant-cost; large integers also incur a cost based on bit length. A valid nonempty AVL tree has h=O(log(n+1)); empty-tree operations take constant time. When the validator receives an unbalanced tree, its stack can reach O(n). Validation cannot assume its own conclusion.

The example implements insertion, traversal, and validation. Search can reuse the BST path from Chapter 5. height() reads cached metadata in O(1). The deletion bound describes the complete AVL algorithm; deletion is not implemented here.

10. Check Rotations and Heights

1. Without looking at the table, draw the imbalance type and two rotations of [50, 30, 40].
2. Make T2 a single node with key 17, set x=15 and y=20 in the right-rotation diagram, and verify the order before and after rotation.
3. Manually increment the height at the root of the example tree and verify that is_valid() returns False.
4. Explain why AVL insertion fixes at most one unbalanced ancestor, while deletion might require continuing upward.

Move from Exact Height to Color Constraints

The next balanced tree does not store exact height; it constrains shape with color and black height. Continue to Red-Black Trees.