AVL Tree Rotations: Self-Balancing BST Explained

A regular BST has a fatal flaw: if you insert sorted data, it degrades into a linked list with O(n) operations. AVL trees solve this by maintaining balance after every insertion and deletion. Named after Adelson-Velsky and Landis (1962), they were the first self-balancing BST.

Why BSTs degrade

Insert the values 1, 2, 3, 4, 5 into a regular BST:

1
 \
  2
   \
    3
     \
      4
       \
        5

Height = 4 (should be ~2 for 5 nodes)
Search for 5: 5 comparisons instead of ~3

Every operation becomes O(n). An AVL tree prevents this by enforcing that the heights of the left and right subtrees differ by at most 1.

Balance factor

The balance factor of a node is:

balance_factor(node) = height(left subtree) - height(right subtree)

An AVL tree requires that every node has a balance factor of -1, 0, or 1. If any node’s balance factor becomes -2 or 2, we must rebalance with rotations.

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # new nodes are leaves with height 1

def get_height(node):
    if node is None:
        return 0
    return node.height

def get_balance(node):
    if node is None:
        return 0
    return get_height(node.left) - get_height(node.right)

def update_height(node):
    node.height = 1 + max(get_height(node.left), get_height(node.right))

The four rotation types

When balance is violated, exactly one of four rotation patterns fixes it. Each rotation is O(1) — it only rearranges a constant number of pointers.

Right Rotation (for LL imbalance)

When a node becomes left-heavy (balance factor = 2) and its left child is left-heavy or balanced (balance factor >= 0):

Before:           After:
    z                 y
   / \              /   \
  y   T4    →      x     z
 / \              / \   / \
x   T3           T1 T2 T3 T4
/ \
T1 T2

def right_rotate(z):
    """Perform right rotation on node z."""
    y = z.left
    T3 = y.right

    # Rotate
    y.right = z
    z.left = T3

    # Update heights (z first, then y — order matters)
    update_height(z)
    update_height(y)

    return y  # y is the new root of this subtree

Left Rotation (for RR imbalance)

Mirror of right rotation. When a node becomes right-heavy (balance factor = -2) and its right child is right-heavy or balanced (balance factor <= 0):

Before:         After:
  z                y
 / \             /   \
T1  y    →      z     x
   / \         / \   / \
  T2  x       T1 T2 T3 T4
     / \
    T3 T4

def left_rotate(z):
    """Perform left rotation on node z."""
    y = z.right
    T2 = y.left

    # Rotate
    y.left = z
    z.right = T2

    # Update heights
    update_height(z)
    update_height(y)

    return y

Left-Right Rotation (for LR imbalance)

When a node is left-heavy (balance factor = 2) but its left child is right-heavy (balance factor < 0). A single right rotation will not fix this — we need a double rotation.

Before:          Step 1 (Left):    Step 2 (Right):
    z                z                  x
   / \              / \               /   \
  y   T4    →      x   T4    →      y     z
 / \              / \               / \   / \
T1  x            y   T3           T1  T2 T3 T4
   / \          / \
  T2  T3       T1  T2

First, left-rotate y, then right-rotate z.

Right-Left Rotation (for RL imbalance)

When a node is right-heavy (balance factor = -2) but its right child is left-heavy (balance factor > 0).

Before:          Step 1 (Right):    Step 2 (Left):
  z                  z                   x
 / \                / \                /   \
T1  y       →      T1  x      →      z     y
   / \                 / \           / \   / \
  x   T4             T2   y        T1 T2 T3 T4
 / \                      / \
T2  T3                   T3  T4

First, right-rotate y, then left-rotate z.

Choosing the right rotation

The decision depends on two balance factors:

Node BF	Child BF	Rotation	Case
+2	+1 or 0	Right	LL
-2	-1 or 0	Left	RR
+2	-1	Left-Right	LR
-2	+1	Right-Left	RL

Think of it this way: the letters tell you the path of imbalance.

• LL: went left, then left (fix with right rotation)
• RR: went right, then right (fix with left rotation)
• LR: went left, then right (fix with left-right double rotation)
• RL: went right, then left (fix with right-left double rotation)

AVL insertion

Insert like a regular BST, then walk back up updating heights and rebalancing:

def insert(node, val):
    """Insert val into AVL tree rooted at node. Return new root."""
    # Step 1: Standard BST insert
    if node is None:
        return AVLNode(val)

    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    else:
        return node  # no duplicates

    # Step 2: Update height of this node
    update_height(node)

    # Step 3: Get balance factor
    balance = get_balance(node)

    # Step 4: Rebalance if needed (4 cases)

    # LL Case
    if balance > 1 and val < node.left.val:
        return right_rotate(node)

    # RR Case
    if balance < -1 and val > node.right.val:
        return left_rotate(node)

    # LR Case
    if balance > 1 and val > node.left.val:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # RL Case
    if balance < -1 and val < node.right.val:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

Insertion walkthrough

Insert 1, 2, 3 into an AVL tree:

# Insert 1:  Just a single node
#   1

# Insert 2:  No rebalance needed (BF of 1 is -1)
#   1
#    \
#     2

# Insert 3:  Node 1 has BF = -2 (RR case → left rotate)
#   1              2
#    \     →      / \
#     2          1   3
#      \
#       3

# Without AVL, we'd have a skewed line.
# With AVL, we get a balanced tree of height 1.

AVL deletion

Deletion is similar to BST deletion, but we must rebalance on the way back up:

def delete(node, val):
    """Delete val from AVL tree rooted at node. Return new root."""
    # Step 1: Standard BST delete
    if node is None:
        return None

    if val < node.val:
        node.left = delete(node.left, val)
    elif val > node.val:
        node.right = delete(node.right, val)
    else:
        # Node to delete found
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        else:
            # Two children: get in-order successor
            successor = find_min(node.right)
            node.val = successor.val
            node.right = delete(node.right, successor.val)

    # Step 2: Update height
    update_height(node)

    # Step 3: Rebalance
    balance = get_balance(node)

    # LL Case
    if balance > 1 and get_balance(node.left) >= 0:
        return right_rotate(node)

    # LR Case
    if balance > 1 and get_balance(node.left) < 0:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # RR Case
    if balance < -1 and get_balance(node.right) <= 0:
        return left_rotate(node)

    # RL Case
    if balance < -1 and get_balance(node.right) > 0:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

def find_min(node):
    while node.left:
        node = node.left
    return node

Note: For deletion, we check the child’s balance factor directly (not by comparing the value), because the imbalance may come from the opposite subtree losing a node.

Complete AVL tree class

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

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return AVLNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        else:
            return node

        update_height(node)
        return self._rebalance(node)

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if not node:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            if not node.left:
                return node.right
            if not node.right:
                return node.left
            successor = find_min(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)

        update_height(node)
        return self._rebalance(node)

    def _rebalance(self, node):
        balance = get_balance(node)

        if balance > 1:
            if get_balance(node.left) < 0:
                node.left = left_rotate(node.left)
            return right_rotate(node)

        if balance < -1:
            if get_balance(node.right) > 0:
                node.right = right_rotate(node.right)
            return left_rotate(node)

        return node

    def search(self, val):
        node = self.root
        while node:
            if val == node.val:
                return True
            elif val < node.val:
                node = node.left
            else:
                node = node.right
        return False

    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)

    def get_height(self):
        return get_height(self.root)

Usage example

avl = AVLTree()

# Insert sorted data — would kill a regular BST
for i in range(1, 16):
    avl.insert(i)

print(avl.inorder())       # [1, 2, 3, ..., 15]
print(avl.get_height())    # 4 (log2(15) ≈ 4, not 14!)
print(avl.search(10))      # True
print(avl.search(20))      # False

avl.delete(8)
print(avl.inorder())       # [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]
print(avl.get_height())    # Still 4 — stays balanced

Time complexity

Operation	AVL Tree	Regular BST (worst)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Space	O(n)	O(n)

AVL trees guarantee O(log n) for all operations because the height is always bounded by approximately 1.44 * log2(n).

Rotation cost

Each insertion triggers at most 2 rotations (one double rotation). Each deletion can trigger at most O(log n) rotations (one per ancestor). But each individual rotation is O(1), so the overall operation stays O(log n).

AVL vs Red-Black trees

Feature	AVL	Red-Black
Balance strictness	height diff <= 1	roughly balanced
Max height	1.44 log n	2 log n
Search speed	Slightly faster	Slightly slower
Insert rotations	Up to 2	Up to 2
Delete rotations	Up to O(log n)	Up to 3
Use case	Read-heavy	Write-heavy

Use AVL when: Lookups vastly outnumber insertions/deletions (databases indexes, dictionaries).

Use Red-Black when: Insertions and deletions are frequent (language standard libraries — Java TreeMap, C++ std::map, Linux kernel).

Verifying AVL property

A helper to verify that a tree maintains the AVL invariant:

def is_avl(node):
    """Check if tree rooted at node is a valid AVL tree."""
    if node is None:
        return True, 0

    left_avl, left_h = is_avl(node.left)
    right_avl, right_h = is_avl(node.right)

    balanced = abs(left_h - right_h) <= 1
    height = 1 + max(left_h, right_h)

    return left_avl and right_avl and balanced, height

# Usage:
valid, _ = is_avl(avl.root)
print(valid)  # True

Practice problems

1. Insert into AVL — Build the full insert with rotations
2. Delete from AVL — Handle rebalancing after delete
3. Convert Sorted Array to Balanced BST (LeetCode 108) — Already balanced, no rotations needed
4. Balance a BST (LeetCode 1382) — In-order then rebuild
5. Count nodes with balance factor 0 — Practice height calculations
6. Print AVL tree level by level showing balance factors — Debugging tool

Key takeaways

• AVL trees maintain balance factor in {-1, 0, 1} for every node
• Four rotation types handle all imbalance cases: LL, RR, LR, RL
• Height is always O(log n), guaranteeing O(log n) operations
• Slightly more overhead than Red-Black trees on writes, but faster reads
• The recursion naturally handles rebalancing as it unwinds up the tree