AVL rotations drawn one pointer at a time
Repair AVL imbalance with rotations that preserve in-order keys, follow the transferred middle subtree, and update stored heights in the right order.

An AVL rotation changes a small part of a binary search tree while preserving its in-order sequence. It repairs a height imbalance by moving a child above its parent and transferring the subtree between their keys. For a student who understands basic tree search, following that transferred subtree is more useful than memorizing diagrams labeled LL, RR, LR, and RL.
Use height zero for an empty subtree and height one for a leaf. An AVL node requires its left and right subtree heights to differ by at most one. Its balance factor is left height minus right height. The stored height must agree with the actual children after every structural change.
A right rotation keeps the middle subtree reachable
Suppose node four has left child two, and two has children one and three. Four has no right child. The subtree rooted at four is too heavy on the left. A right rotation promotes two, makes four its right child, and moves three to become four’s left child.
Before the rotation, the in-order sequence is one, two, three, four. Afterward it is still one, two, three, four. Three cannot stay as two’s right child because that slot is needed for four, and it cannot move to four’s right because three is smaller than four.
The same argument works for whole subtrees. If the promoted key is y and the old root is x, every key in y.right lies between y and x. That subtree becomes x.left. No key ordering changes, even though parent-child relationships do.
Update the lower node before the new root
The old root’s children change first, so recalculate its height before recalculating the promoted root. The promoted root’s height depends on the repaired height of the old root now below it.
def height(node):
return node.height if node else 0
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
self.height = 1 + max(height(left), height(right))
def refresh(node):
node.height = 1 + max(height(node.left), height(node.right))
def rotate_right(x):
y = x.left
x.left = y.right
y.right = x
refresh(x)
refresh(y)
return y
def rotate_left(x):
y = x.right
x.right = y.left
y.left = x
refresh(x)
refresh(y)
return y
def rebalance(node):
refresh(node)
balance = height(node.left) - height(node.right)
if balance > 1:
if height(node.left.left) < height(node.left.right):
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1:
if height(node.right.right) < height(node.right.left):
node.right = rotate_right(node.right)
return rotate_left(node)
return node
root = Node(4, Node(2, Node(1), Node(3)))
root = rebalance(root)
assert root.key == 2 and root.right.key == 4
assert root.right.left.key == 3
assert root.height == 3 and root.right.height == 2
These helpers assume a valid binary search tree whose child subtrees are already balanced with correct heights, and whose current node has the local imbalance produced by an AVL update. They are not a repair procedure for an arbitrary badly skewed tree. An insertion or deletion routine calls them while returning along the modified search path.
Returning the new subtree root is part of the interface. The caller must assign it into the corresponding parent link, or into the overall tree root. Ignoring the return value can leave the old root visible while the promoted node and part of the structure become disconnected from the caller’s view.
The double cases rotate the child first
For insertion order three, one, two, the root is left heavy but its left child is right heavy. A direct right rotation would still leave the shape unbalanced. Rotate the left child left to bring two above one, then rotate the root right. The result has two at the root, one on the left, and three on the right.
The mirror case is insertion order one, three, two. Rotate the right child right, then rotate the root left. For the straight patterns three, two, one and one, two, three, a single outer rotation is enough. These are the four common cases, derived from which side is heavy at the node and at its child.
Cornell’s AVL lecture develops the balance requirement and these repairs. The more general rotation discussion in Open Data Structures shows why rotations preserve binary-search order independently of the balancing scheme that chooses them.
Local work supports a global height bound
A rotation changes a constant number of links and height fields. Finding the update location and revisiting its ancestors still takes time proportional to tree height. AVL balance bounds that height logarithmically because a tall valid subtree must contain enough nodes in both branches.
If N(h) is the smallest node count for AVL height h, its two child heights must be at least h - 1 and h - 2 in the minimum-size case. Thus N(h) = 1 + N(h - 1) + N(h - 2), with empty and leaf base cases. This Fibonacci-like growth makes height O(log n). The balancing guarantee supplies the search bound that an ordinary binary search tree lacks.
Deletion may reduce subtree height and require repairs at multiple ancestors. The child-height comparisons in the helper include the equal-height case, which matters during deletion. A complete AVL implementation must also update parent pointers, subtree sizes, or other metadata if it stores them; refreshing height alone is insufficient for an augmented tree.
Test all four three-key insertion shapes, then test the four-key rotation shown in the figure to catch a lost middle subtree. After a repair, check in-order keys, every balance factor, and every stored height. A correct root key by itself does not prove that all descendants survived or that later updates will read accurate metadata.
Reconnect every changed subtree during insertion
A short insertion routine shows how the rotation helpers fit into a full update. Descend according to the binary-search-tree rule, create one leaf if the key is absent, then rebalance on the way back. Each recursive call returns the root of the subtree after its repair, so the parent assigns that result into the same child link it followed downward.
def avl_insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = avl_insert(node.left, key)
elif key > node.key:
node.right = avl_insert(node.right, key)
else:
return node
return rebalance(node)
for insertion_order in ([3, 2, 1], [1, 2, 3], [3, 1, 2], [1, 3, 2]):
tree = None
for key in insertion_order:
tree = avl_insert(tree, key)
assert tree.key == 2
assert tree.left.key == 1 and tree.right.key == 3
assert tree.height == 2
old_root = Node(30, Node(10, None, Node(20)))
new_root = rebalance(old_root)
assert new_root.key == 20 and new_root.right is old_root
assert old_root.key == 30 and old_root.left is None and old_root.right is None
The loop’s assignment to tree is essential at the overall root, just as the child assignments are essential inside the function. In the thirty-ten-twenty example, the old root object survives as the right child of twenty. A caller that ignored the return value would still point at thirty and see only that leaf, losing access to ten and twenty from its supposed tree root.
The intermediate stage matters. First the left rotation inside the child subtree returns twenty, which must replace thirty’s left link. Only then can the right rotation at thirty promote that updated child. Applying the outer rotation to the stale child reference performs a different transformation and may disconnect nodes. Treat each returned root as part of the mutation, not an optional convenience for the caller.
This insertion policy keeps one copy of each integer key. Encountering a duplicate returns the existing node and does not allocate another leaf. The routine mutates existing nodes; it is not a persistent tree that leaves an earlier version intact. External references to node objects remain references to those objects, but the objects can acquire different parents after rotations.
Starting from a valid AVL tree, the recursive child update establishes the precondition needed by rebalance: its child subtrees have correct heights and satisfy the balance rule. A single insertion increases the modified child’s height by at most one, so the parent’s imbalance is local and can be handled by these cases. This argument does not justify calling the routine on an arbitrary preexisting skewed tree and expecting every old defect to disappear.
Insertion follows O(log n) ancestors under the maintained height invariant, with constant local rotation and height work per ancestor. The recursive implementation also uses O(log n) active calls, and a successful new-key insertion allocates one node. These are different storage contributions. Deletion needs its own search, removal and upward-repair logic; the insertion example does not implement it.
For an exercise, insert a sequence of distinct keys and retain each created node’s identity. After every insertion, independently recompute heights from the children, check all balance factors and verify the in-order sequence. Then insert duplicates and confirm both the node count and existing node identities remain unchanged. Those checks catch a correct-looking top-level shape that hides lost descendants or stale height fields.