DSA AVL Trees

An AVL tree is a binary search tree that keeps itself balanced. Plain binary search trees can lean to one side and slow down to O(n) per search. An AVL tree repairs any lean immediately, so searches stay at O(log n). Two scientists, Adelson-Velsky and Landis, invented it, which explains the name.

Think of a seesaw in a playground. A balanced seesaw moves smoothly. When one child is much heavier, the seesaw tips and stops working well. An AVL tree acts like a helper who shifts the weight back to the center after every change.

Balance Factor

Each node carries a balance factor. The value equals the height of the left subtree minus the height of the right subtree. An AVL tree allows only the values -1, 0, and 1. Any other value triggers a repair.

Balanced                Unbalanced

     20                   10   (balance = -2)
    /  \                    \
  10    30                  20
                              \
                              30

The Node and Helper Functions

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

def height(node):
    return node.height if node else 0

def balance(node):
    return height(node.left) - height(node.right) if node else 0

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

Rotations

A rotation rearranges a few nodes to restore balance while keeping the search order intact.

Right Rotation

Use a right rotation when the left side grows too tall.

Before            After
    30              20
   /               /  \
  20             10    30
 /
10

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

Left Rotation

Use a left rotation when the right side grows too tall.

Before            After
10                  20
  \                /  \
   20            10    30
     \
      30

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

The Four Cases

• Left-Left: a new value lands in the left child's left side. One right rotation fixes it.
• Right-Right: a new value lands in the right child's right side. One left rotation fixes it.
• Left-Right: a new value lands in the left child's right side. Rotate the left child left, and rotate the node right.
• Right-Left: a new value lands in the right child's left side. Rotate the right child right, and rotate the node left.

Insert With Balancing

def insert(node, value):
    if node is None:
        return AVLNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    else:
        return node

    update(node)
    b = balance(node)

    if b > 1 and value < node.left.value:
        return rotate_right(node)
    if b < -1 and value > node.right.value:
        return rotate_left(node)
    if b > 1 and value > node.left.value:
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if b < -1 and value < node.right.value:
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

root = None
for v in [10, 20, 30]:
    root = insert(root, v)
print(root.value)   # 20

Inserting 10, 20, and 30 in order would build a straight chain in a plain tree. The AVL tree detects the lean at node 10 and rotates, so 20 becomes the root.

Why Balance Matters

A balanced tree with 1,000,000 nodes has a height near 20. A skewed tree with the same nodes has a height near 1,000,000. The AVL rules guarantee the first outcome for any insert order.

Real-Life Uses

Databases use balanced trees for indexes. Operating systems track memory regions with them. Ordered maps in several programming languages rely on balanced trees, such as red-black trees, a close relative of AVL trees. Any system that needs fast lookups and steady performance benefits from the guarantee.

AVL Trees vs Plain Binary Search Trees

A plain tree costs less per insert because it skips the balance checks. An AVL tree spends a little extra effort on each insert and saves far more on every search. Choose an AVL tree when the data arrives in unpredictable order or when searches happen often.

Common Mistakes

Forgetting to update heights after a rotation breaks later balance checks. Updating the lower node first and the upper node second matters, because the upper height depends on the lower one. Mixing up the four cases is easy, so sketch the three-node shape before choosing a rotation.

Complexity Summary

• Search, insert, delete: O(log n) in every case.
• Space: O(n) for the nodes.

Key Points

• An AVL tree stays balanced after every insert and delete.
• The balance factor must stay between -1 and 1.
• Rotations restore balance without breaking the search order.
• Four cases exist, and each needs one or two rotations.
• Operations stay at O(log n) even in the worst case.