AVL rotations in Python: LL, RR, LR and RL

Why this matters

A plain binary search tree (BST) is fast only when it stays bushy. If you insert values that already come in sorted order, every new value lands at the bottom of one long chain. Search then has to walk the whole chain. The lesson on sorted input shows how this happens.

An AVL tree is a BST that fixes itself. After each insert or delete, it checks the nodes on the way back up to the root. When a node leans too far to one side, the tree rotates part of itself so the lean goes away. A rotation changes a few links and keeps the values in sorted order.

There are four ways a node can lean too far, and each has a name. The names describe the path from the bad node down to where the change happened:

• LL: the change is in the left child's left subtree.
• RR: the change is in the right child's right subtree.
• LR: the change is in the left child's right subtree.
• RL: the change is in the right child's left subtree.

This lesson walks through each case with real output from a Python program that does the same steps. The tree shapes are drawn as text.

Words used in this lesson

• The height of a node is the number of nodes on the longest path from that node down to a leaf. A leaf is a node with no children. A leaf has height 1, and an empty spot (None) has height 0.
• The balance factor of a node is the height of its left subtree minus the height of its right subtree. A plus sign means it leans left, a minus sign means it leans right. This lesson uses that order. Some books subtract in the other order and flip every sign. The four case names do not change, because they describe the path, not the number.
• An AVL tree is a BST where every node has a balance factor of -1, 0 or +1.
• A rotation is a local change of links. One node moves up and its child moves down, and the sorted order of the values stays the same.
• A single rotation moves one node up one level. A double rotation is two single rotations in a row.

Each drawing below shows the balance factor next to each node in brackets, like 30 (+2).

Balance factors on a small tree

Here is a tree after the values 20, 10, 30, 5 and 15 were inserted. The root 20 has a left subtree of height 2 (the node 10 has two children) and a right subtree of height 1 (the node 30 is a leaf). So the balance factor of 20 is 2 minus 1, which is +1. Node 10 has children of equal height, so its balance factor is 0.

          20 (+1)
         /      \
      10 (0)    30 (0)
     /    \
   5 (0)  15 (0)

This tree is a valid AVL tree, because every node has a balance factor of -1, 0 or +1.

The tree becomes invalid when a balance factor reaches +2 or -2. That is the signal to rotate. The node with the bad balance is the first place to fix. Its child on the heavy side (the taller side) decides which case it is.

The four insert cases

When you insert a value, the new node is a leaf. Walk up from it to the root and update each height. The first node you meet with a balance factor of +2 or -2 is the node to fix. After one rotation at that node, the subtree has the same height it had before the insert, so no other node above it can be out of balance.

The fix depends on the child on the heavy side:

• If the child leans the same way as its parent, the case is LL (for +2) or RR (for -2). Use one single rotation at the bad node.
• If the child leans the other way, the case is LR (for +2) or RL (for -2). Use a double rotation: first rotate the child, then rotate the bad node.

During an insert, the child on the heavy side always leans one way or the other, never 0. The reason is simple: that child just grew taller because the new node arrived below it, so one of its sides is taller than the other.

Here is the summary table:

Single right rotation: the LL case

Insert 30, then 20, then 10. Each new value goes left of the one before, so the tree becomes a chain.

      30 (+2)
     /
   20 (+1)
  /
10 (0)

Node 30 has a balance factor of +2, so it is out of balance. Its left child 20 leans left (+1), so this is the LL case. A single right rotation at 30 moves 20 up:

      20 (0)
     /    \
  10 (0)  30 (0)

The values are still in order: 10, 20, 30. The tree has height 2 after the fix, which is the height it had before the third value arrived. The program at the end of this lesson prints each insert in preorder, which means node first, then the left subtree, then the right subtree. A line that starts with at is the rotation the program chose:

== insert LL: 30, 20, 10 ==
insert 30 -> preorder: 30(+0)
insert 20 -> preorder: 30(+1) 20(+0)
insert 10 -> preorder: 20(+0) 10(+0) 30(+0)
    at 30 balance 2: LL, rotate right

The line for insert 10 shows the tree after the rotation. The balance factor of 30 was +2 before the fix, and the log line records it.

Single left rotation: the RR case

Insert 10, then 20, then 30. This is the mirror image of the LL case.

  10 (-2)
    \
    20 (-1)
       \
       30 (0)

Node 10 has a balance factor of -2. Its right child 20 leans right (-1), so this is the RR case. A single left rotation at 10 moves 20 up, and the tree becomes 20 with children 10 and 30.

== insert RR: 10, 20, 30 ==
insert 10 -> preorder: 10(+0)
insert 20 -> preorder: 10(-1) 20(+0)
insert 30 -> preorder: 20(+0) 10(+0) 30(+0)
    at 10 balance -2: RR, rotate left

Double rotation: the LR case

Insert 30, then 10, then 20. The value 10 goes left of 30, and 20 goes right of 10. This is a zig-zag, and a single rotation will not fix it.

    30 (+2)
   /
 10 (-1)
    \
    20 (0)

Node 30 has a balance factor of +2, and its left child 10 leans right (-1). That is the LR case. A single right rotation at 30 would make 10 the top, with 30 on its right and 20 on the left of 30. The tree would still lean right at 10, with balance -2. The fix is two steps.

Step 1, rotate the child left. The node 20 moves above 10:

    30 (+2)
   /
  20 (+1)
 /
10 (0)

Step 2, rotate the bad node right. Node 30 now has a left child that leans left (+1), so the tree is an ordinary LL shape, and one right rotation puts 20 at the top:

      20 (0)
     /    \
  10 (0)  30 (0)

The real output shows both steps in one log line:

== insert LR: 30, 10, 20 ==
insert 30 -> preorder: 30(+0)
insert 10 -> preorder: 30(+1) 10(+0)
insert 20 -> preorder: 20(+0) 10(+0) 30(+0)
    at 30 balance 2: LR, rotate left at 10 then right at 30

Double rotation: the RL case

Insert 10, then 30, then 20. This is the mirror image of the LR case.

  10 (-2)
    \
    30 (+1)
    /
  20 (0)

Node 10 has a balance factor of -2, and its right child 30 leans left (+1). That is the RL case. Rotate the child right, so 20 moves above 30. Then rotate the bad node left, so 20 moves above 10.

== insert RL: 10, 30, 20 ==
insert 10 -> preorder: 10(+0)
insert 30 -> preorder: 10(-1) 30(+0)
insert 20 -> preorder: 20(+0) 10(+0) 30(+0)
    at 10 balance -2: RL, rotate right at 30 then left at 10

The rotation code

Each node stores its key, its height and its two children. The program also keeps a list of log lines, which the traces print. A Node class holds those four fields.

class Node:
    def __init__(self, key):
        self.key = key
        self.height = 1
        self.left = None
        self.right = None
 
 
log = []

A rotation has to update the heights of the two nodes it moved. The lower node must be updated first, because the height of the new top depends on the height of its child.

def rotate_right(y):
    x = y.left
    t2 = x.right
    x.right = y
    y.left = t2
    update(y)
    update(x)
    return x
 
 
def rotate_left(x):
    y = x.right
    t2 = y.left
    y.left = x
    x.right = t2
    update(x)
    update(y)
    return y

The variable t2 is the subtree that moves from one side to the other. It stays between the two moved nodes, which keeps the values in sorted order. Here update sets the height of a node to 1 plus the larger of its two child heights, and height treats None as 0.

The same file contains the helper functions used by the traces:

def height(n):
    return 0 if n is None else n.height
 
 
def update(n):
    n.height = 1 + max(height(n.left), height(n.right))
 
 
def balance(n):
    return 0 if n is None else height(n.left) - height(n.right)

The rebalance function looks at the balance of a node and picks the case. The insert and delete functions both call it on the way back up.

def rebalance(n):
    bf = balance(n)
    if bf > 1:
        if balance(n.left) >= 0:
            log.append(f"at {n.key} balance {bf}: LL, rotate right")
            return rotate_right(n)
        log.append(f"at {n.key} balance {bf}: LR, rotate left at {n.left.key} then right at {n.key}")
        n.left = rotate_left(n.left)
        return rotate_right(n)
    if bf < -1:
        if balance(n.right) <= 0:
            log.append(f"at {n.key} balance {bf}: RR, rotate left")
            return rotate_left(n)
        log.append(f"at {n.key} balance {bf}: RL, rotate right at {n.right.key} then left at {n.key}")
        n.right = rotate_right(n.right)
        return rotate_left(n)
    return n

Look at the condition balance(n.left) >= 0. A child with balance +1 gives LL. A child with balance -1 gives LR. The code also accepts 0 as LL, because a delete can leave a child with balance 0. For inserts, the 0 case never happens, so the same code serves both.

Delete: the same four names, a new rule for 0

Deleting a node makes one side of the tree shorter. Here is the delete code:

def delete(n, key):
    if n is None:
        return None
    if key < n.key:
        n.left = delete(n.left, key)
    elif key > n.key:
        n.right = delete(n.right, key)
    else:
        if n.left is None:
            return n.right
        if n.right is None:
            return n.left
        s = n.right
        while s.left is not None:
            s = s.left
        n.key = s.key
        n.right = delete(n.right, s.key)
    update(n)
    return rebalance(n)

When the node to delete has two children, the code copies in the smallest value from its right subtree, which is the next value in sorted order, and then deletes that value from the right side. This keeps the BST order.

There are two differences from insert:

1. A rotation can happen at more than one ancestor. An insert creates one imbalance, and one rotation fixes it. A delete can leave an imbalance at several levels on the way up, and each one must be checked. The recursive calls do this, because rebalance runs on every node the call returns through.
2. The heavy child can have a balance of 0. When both sides of the child are the same height, a single rotation is correct. A balance of 0 is a single-rotation case, not a double one.

So the rule for delete is: if the heavy child leans toward the same side as its parent, or has balance 0, use a single rotation. If it leans toward the opposite side, use a double rotation.

Delete case A: LL with a child of balance 0

Insert 20, 10, 30, 5 and 15, then delete 30. The tree before the delete is the one from the earlier section, with root 20 at +1. After deleting 30, the root has a left subtree of height 2 and no right subtree, so its balance is +2. Its left child 10 has two children of equal height, so its balance is 0.

          20 (+2)
         /
      10 (0)
     /    \
   5 (0)  15 (0)

The heavy child has balance 0, so the case is LL with a single right rotation at 20. Node 10 moves up, and 20 moves down to the right of 10, with 15 as its left child.

        10 (-1)
       /     \
    5 (0)    20 (+1)
            /
         15 (0)

The real output confirms it:

== delete with left child balance 0 (single right rotation) ==
insert 20 -> preorder: 20(+0)
insert 10 -> preorder: 20(+1) 10(+0)
insert 30 -> preorder: 20(+0) 10(+0) 30(+0)
insert 5 -> preorder: 20(+1) 10(+1) 5(+0) 30(+0)
insert 15 -> preorder: 20(+1) 10(+0) 5(+0) 15(+0) 30(+0)
delete 30 -> preorder: 10(-1) 5(+0) 20(+1) 15(+0)
    at 20 balance 2: LL, rotate right

Check the new balances by hand. Node 10 has a left subtree of height 1 (node 5) and a right subtree of height 2 (node 20 with child 15). So its balance is 1 minus 2, which is -1. Node 20 has a left child 15 of height 1 and no right child, so its balance is +1. Both are in the allowed range.

Delete case B: LR

Insert 20, 10, 30 and 15, then delete 30. Before the delete, node 10 has a right child 15, so it leans right with balance -1.

        20 (+1)
       /    \
    10 (-1)  30 (0)
        \
       15 (0)

After the delete, node 20 has balance +2 and its left child 10 has balance -1. The heavy child leans the opposite way, so the case is LR. Rotate 10 left, which moves 15 up. Then rotate 20 right, which moves 15 to the top.

        15 (0)
       /    \
    10 (0)  20 (0)

== delete with left child balance -1 (LR) ==
insert 20 -> preorder: 20(+0)
insert 10 -> preorder: 20(+1) 10(+0)
insert 30 -> preorder: 20(+0) 10(+0) 30(+0)
insert 15 -> preorder: 20(+1) 10(-1) 15(+0) 30(+0)
delete 30 -> preorder: 15(+0) 10(+0) 20(+0)
    at 20 balance 2: LR, rotate left at 10 then right at 20

Delete case C: RR

Insert 20, 10, 30 and 35. Node 30 leans right with balance -1, so the tree is 20 with balance -1, and it has a right subtree of height 2.

        20 (-1)
       /     \
    10 (0)    30 (-1)
                 \
                 35 (0)

Delete 10. Node 20 now has no left child and a right subtree of height 2, so its balance is -2. Its right child 30 leans right with balance -1, which is the same side. The case is RR, and one left rotation at 20 moves 30 to the top.

       30 (0)
      /    \
   20 (0)  35 (0)

== delete with right child balance -1 (RR) ==
insert 20 -> preorder: 20(+0)
insert 10 -> preorder: 20(+1) 10(+0)
insert 30 -> preorder: 20(+0) 10(+0) 30(+0)
insert 35 -> preorder: 20(-1) 10(+0) 30(-1) 35(+0)
delete 10 -> preorder: 30(+0) 20(+0) 35(+0)
    at 20 balance -2: RR, rotate left

Delete case D: RL

Insert 20, 10, 30 and 25. Node 30 has a left child 25, so it leans left with balance +1.

        20 (-1)
       /     \
    10 (0)    30 (+1)
              /
           25 (0)

Delete 10. Node 20 has balance -2. Its right child 30 leans left (+1), the opposite side, so the case is RL. Rotate 30 right, which moves 25 up. Then rotate 20 left, which moves 25 to the top.

        25 (0)
       /    \
    20 (0)  30 (0)

== delete with right child balance +1 (RL) ==
insert 20 -> preorder: 20(+0)
insert 10 -> preorder: 20(+1) 10(+0)
insert 30 -> preorder: 20(+0) 10(+0) 30(+0)
insert 25 -> preorder: 20(-1) 10(+0) 30(+1) 25(+0)
delete 10 -> preorder: 25(+0) 20(+0) 30(+0)
    at 20 balance -2: RL, rotate right at 30 then left at 20

Common mistakes

Forgetting to update heights

If insert forgets to call update on a node, the stored heights never change. The balance factors then use old numbers. Here is an insert that skips update, run on 10, 20 and 30 (tree_text is the printing helper in the full program at the end of this lesson):

def insert_no_update(n, key):
    if n is None:
        return Node(key)
    if key < n.key:
        n.left = insert_no_update(n.left, key)
    elif key > n.key:
        n.right = insert_no_update(n.right, key)
    else:
        return n
    return rebalance(n)
 
 
root = None
for k in [10, 20, 30]:
    root = insert_no_update(root, k)
print("after 10, 20, 30: preorder:", tree_text(root))
print("root balance now:", balance(root))

The output is:

after 10, 20, 30: preorder: 10(-1) 20(-1) 30(+0)
root balance now: -1

The real balance of the root 10 is -2, because its right subtree has height 2. The program shows -1, because the stored height of 20 is still 1, so it never rotates. The tree stays out of balance. The fix is to call update(n) before rebalance(n) in every recursive step.

The same trap appears when you write a checker. This function looks right, but it trusts the stored heights:

def is_balanced(n):
    if n is None:
        return True
    if abs(balance(n)) > 1:
        return False
    return is_balanced(n.left) and is_balanced(n.right)

On the tree with stale heights above, it returns True, which is wrong. A checker that reads stored values can only be as correct as the code that stores them.

Rotating from a missing child

A rotation reads a child of the node it is given, so a missing node fails at once. Calling rotate_right with None gives this error:

AttributeError: 'NoneType' object has no attribute 'left'

In an AVL tree this usually means a balance factor was wrong, so the code chose a case that needs a child that is not there. Look for the stale height first, then the balance.

Rotating the parent before the child's height is correct

In rotate_right, the lower node y must be updated before the new top x. Here x.height is computed from y.height. If the code updates x first, the new top gets a height that was computed from an old value of y, and every balance factor above it is off by that amount.

Checking only one ancestor on delete

After an insert, one rotation is enough. After a delete, the walk back to the root may find more than one bad node. Code that rebalances only the first one it meets will leave the others out of balance. The recursive delete avoids this by calling rebalance on every node it returns through.

Practice

Exercise 1: insert case

Insert 10, 30, then 15 into an empty AVL tree. Which case happens, at which node, and what is the root after the fix?

Show the answer

The case is RL at node 10. After inserting 30, node 10 has balance -1. After inserting 15 under 30's left side, node 10 has balance -2, and its right child 30 leans left. The fix rotates 30 right and then rotates 10 left. The root becomes 15, with 10 on the left and 30 on the right. The same code prints 15(+0) 10(+0) 30(+0) and the log line at 10 balance -2: RL, rotate right at 30 then left at 10.

Exercise 2: delete with no rotation

Insert 20, 10, 30, 5 and 15 (the tree from the balance factor section). Then delete 5. Does any node need a rotation? Give the balance factor of 10 and 20 after the delete.

Show the answer

No rotation is needed. Node 10 loses its left child, so its left subtree has height 0 and its right subtree (15) has height 1. Its balance is -1. Node 20 keeps a left subtree of height 2 and a right subtree of height 1, so its balance stays +1. The same code prints 20(+1) 10(-1) 15(+0) 30(+0) and no at line.

Exercise 3: which node rotates

Insert 20, 10, 30, 25, 35 and then 40. Which node is rebalanced when 40 goes in, and which case is it?

Show the answer

Node 20 is rebalanced, with case RR. After 40 goes in, node 20 has a left subtree of height 1 (just 10) and a right subtree of height 3 (30, then 35, then 40), so its balance is -2. Its right child 30 has balance -1, because its right side (35 and 40) is taller than its left side (25). One left rotation at 20 moves 30 to the top. The same code prints at 20 balance -2: RR, rotate left and then the tree 30(+0) 20(+0) 10(+0) 25(+0) 35(-1) 40(+0).

Exercise 4: delete with the LR case

Insert 20, 10, 30 and 15. Then delete 30. Which case happens, and what is the new root?

Show the answer

The case is LR. Node 20 has balance +2 after the delete, and its left child 10 has balance -1, because its right child 15 is the only child. Rotate 10 left, then rotate 20 right. The new root is 15, with 10 on the left and 20 on the right. The same code prints 15(+0) 10(+0) 20(+0).

Exercise 5: write the balance check

Write a function is_balanced(n) that returns True when every node in the tree has a balance factor of -1, 0 or +1. Assume the heights are kept correct.

Show the answer

def is_balanced(n):
    if n is None:
        return True
    if abs(balance(n)) > 1:
        return False
    return is_balanced(n.left) and is_balanced(n.right)

It returns True for the tree built from 20, 10, 30, 25, 35 and 40. Because it trusts stored heights, it returns True for the stale tree from the mistakes section, which is wrong. Keeping heights correct is the job of update.

The full trace program

The program below contains everything the traces above used. It runs the four insert cases and the four delete cases, and it prints the same lines as the excerpts in this lesson.

The output of this program is the eight traces shown in the sections above. The output contains no random values, so it is the same on every run.

Summary

• An AVL node is out of balance when its balance factor is +2 or -2. The fix is a rotation at that node.
• The child on the heavy side picks the case: same side means a single rotation (LL or RR), opposite side means a double rotation (LR or RL).
• After an insert, the child on the heavy side always has balance +1 or -1. After a delete, it can also have balance 0, which is a single-rotation case.
• A delete can need rotations at several ancestors on the way up, so every node on that path must be checked.
• Rotations keep the values in sorted order, and each one updates the heights of the two moved nodes, lower node first.