The Four Rotations

All four, run, with the inorder checked

class ANode:
    __slots__ = ("data", "left", "right", "height")

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        self.height = 0


def height(node):
    return -1 if node is None else node.height


def update(node):
    node.height = 1 + max(height(node.left), height(node.right))
    return node


def balance_factor(node):
    return 0 if node is None else height(node.left) - height(node.right)


def rotate_right(z):
    y = z.left
    z.left = y.right
    y.right = z
    update(z)
    update(y)
    return y


def rotate_left(z):
    y = z.right
    z.right = y.left
    y.left = z
    update(z)
    update(y)
    return y


def rebalance(node):
    """Apply whichever of the four cases is needed. Returns the new subtree root."""
    update(node)
    bf = balance_factor(node)
    if bf > 1:                                  # left heavy
        if balance_factor(node.left) < 0:       # left child right heavy: LR
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1:                                 # right heavy
        if balance_factor(node.right) > 0:      # right child left heavy: RL
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node


def shape(node):
    if node is None:
        return "."
    if node.left is None and node.right is None:
        return str(node.data)
    return "%s(%s, %s)" % (node.data, shape(node.left), shape(node.right))


def inorder(node, out=None):
    out = [] if out is None else out
    if node is not None:
        inorder(node.left, out)
        out.append(node.data)
        inorder(node.right, out)
    return out


def leaf(v):
    return ANode(v)


def built(node):
    """Set heights bottom up on a hand built tree."""
    if node is None:
        return None
    built(node.left)
    built(node.right)
    update(node)
    return node


cases = []

# Left Left: 30 is left heavy, its left child 20 is left heavy
cases.append(("Left Left  ", built(ANode(30, ANode(20, leaf(10), None), None))))
# Right Right
cases.append(("Right Right", built(ANode(10, None, ANode(20, None, leaf(30))))))
# Left Right: 30 left heavy, its left child 10 is RIGHT heavy
cases.append(("Left Right ", built(ANode(30, ANode(10, None, leaf(20)), None))))
# Right Left: 10 right heavy, its right child 30 is LEFT heavy
cases.append(("Right Left ", built(ANode(10, None, ANode(30, leaf(20), None)))))

print("%-12s %-22s %-22s %s" % ("case", "before", "after", "inorder unchanged"))
for name, tree in cases:
    before_shape, before_inorder = shape(tree), inorder(tree)
    fixed = rebalance(tree)
    print("%-12s %-22s %-22s %s"
          % (name, before_shape, shape(fixed),
             inorder(fixed) == before_inorder))

print()
print("every case became the same balanced shape 20(10, 30),")
print("and in every case the inorder was unchanged, so the search property survived.")

case         before                 after                  inorder unchanged
Left Left    30(20(10, .), .)       20(10, 30)             True
Right Right  10(., 20(., 30))       20(10, 30)             True
Left Right   30(10(., 20), .)       20(10, 30)             True
Right Left   10(., 30(20, .))       20(10, 30)             True

every case became the same balanced shape 20(10, 30),
and in every case the inorder was unchanged, so the search property survived.

Four different broken shapes, four different repairs, and all four produce the same balanced tree. In every case the inorder is unchanged, which is the proof that the search property survives.

Why a single rotation fails on the Left Right case

Worth seeing, because the table is otherwise just four lines to memorise.

Take 30(10(., 20), .), a Left Right violation. Apply a single right rotation: 10 comes up, 30 goes right, and 10's right child 20 becomes 30's left child.

The result is 10(., 30(20, .)), which is a Right Left violation: still height 2, still unbalanced, just leaning the other way. The single rotation moved the problem instead of fixing it.

The double rotation works because the first rotation turns the Left Right shape into a Left Left shape, which the second then fixes.

The cost

A rotation is O(1): three pointer assignments and two height updates, regardless of the size of the subtrees hanging below. That is what makes AVL insertion O(log n) overall: the walk down is the height, and the repair is constant.

Quick revision

• A rotation lifts a node from the tall side into the parent's place and pushes the parent down the short

side.

• It does not change the inorder traversal, which is why the search property survives.
• Four cases: Left Left needs one right rotation; Right Right one left rotation; Left Right a left on the

child then a right on the node; Right Left a right on the child then a left on the node.

• The name says where the problem is; the rotation goes the opposite way.
• A single rotation on a Left Right case moves the problem to the other side rather than fixing it.
• All four cases on three nodes produce the same balanced result.
• A rotation is O(1): three pointer assignments and two height updates.

Test yourself

1. What property makes rotations safe to use on a search tree? A rotation does not change the inorder traversal, so the ordering of the values is preserved even though the shape changes.

2. Give the four cases and their fixes. Left Left: one right rotation. Right Right: one left rotation. Left Right: left rotate the child, then right rotate the node. Right Left: right rotate the child, then left rotate the node.

3. How do you tell which case applies? By the node's balance factor and its heavy child's. +2 with the left child not right heavy is Left Left; +2 with the left child right heavy is Left Right; and the mirrors for -2.

4. Why does a single rotation not fix a Left Right violation? Because it turns the shape into a Right Left violation of the same height: the problem moves to the other side rather than going away.

5. What is the cost of a rotation, and why does that matter? O(1): three pointer assignments and two height updates, whatever hangs below. It is what keeps AVL insertion at O(log n), since the walk down costs the height and the repair costs nothing extra.

6. A node has balance factor -2 and its right child has +1. Which case is it and what is the fix? Right Left. Right rotate the right child, then left rotate the node.