Data Structures

AVL Trees

● Advanced ⏱ 12 min read trees

An AVL tree (Adelson-Velsky and Landis, 1962) is a self-balancing BST that guarantees O(log n) height by restoring balance after every insertion or deletion using rotations. It was the first self-balancing BST ever invented.

Balance Factor

Every node stores its height. The balance factor is height(left) − height(right). A node is balanced if its balance factor is −1, 0, or +1. A balance factor of ±2 requires a rotation.

Python

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

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

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

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

LL Case — Right Rotation

The left subtree is too tall and the imbalance is in the left-left direction. Fix: rotate the unbalanced node rightward.

Python

#  Before         After right-rotate(z)
#      z               y
#     / \             / \
#    y   T4          x   z
#   / \             / \ / \
#  x   T3          T1 T2 T3 T4

def rotate_right(z):
    y  = z.left
    T3 = y.right
    y.right = z
    z.left  = T3
    update_height(z)
    update_height(y)
    return y                 # y is the new root of this subtree

RR Case — Left Rotation

The right subtree is too tall and the imbalance is in the right-right direction. Fix: rotate the unbalanced node leftward.

Python

#  Before         After left-rotate(z)
#    z                 y
#   / \               / \
#  T1   y            z   x
#      / \          / \ / \
#     T2   x       T1 T2 T3 T4

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

LR Case — Left-Right Rotation

The left subtree is too tall but the imbalance is in the left-right direction. Fix: left-rotate the left child, then right-rotate the original node.

Python

#  Step 1: left-rotate z.left
#      z               z
#     / \             / \
#    x   T4   →      y   T4
#   / \             / \
#  T1   y          x   T3
#      / \        / \
#     T2  T3     T1  T2
#
#  Step 2: right-rotate z  (same as LL case)
# Combined:
def lr_case(node):
    node.left = rotate_left(node.left)
    return rotate_right(node)

RL Case — Right-Left Rotation

The right subtree is too tall but the imbalance is in the right-left direction. Fix: right-rotate the right child, then left-rotate the original node.

Python

def rl_case(node):
    node.right = rotate_right(node.right)
    return rotate_left(node)

AVL Insertion

Insert exactly like a plain BST, then walk back up the call stack updating heights and applying whichever rotation (if any) is needed at each ancestor.

Python

def avl_insert(node, val):
    # 1. Standard BST insert
    if node is None:
        return AVLNode(val)
    if val < node.val:
        node.left  = avl_insert(node.left, val)
    elif val > node.val:
        node.right = avl_insert(node.right, val)
    else:
        return node             # duplicate — ignore

    # 2. Update height of current node
    update_height(node)

    # 3. Get balance factor
    bf = balance_factor(node)

    # 4. Apply rotation if unbalanced
    # LL case
    if bf > 1 and val < node.left.val:
        return rotate_right(node)
    # RR case
    if bf < -1 and val > node.right.val:
        return rotate_left(node)
    # LR case
    if bf > 1 and val > node.left.val:
        return lr_case(node)
    # RL case
    if bf < -1 and val < node.right.val:
        return rl_case(node)

    return node

# Usage
root = None
for v in [10, 20, 30, 40, 50, 25]:
    root = avl_insert(root, v)
# Without AVL: inserting 10,20,30,40,50 makes a degenerate right-skewed tree.
# With AVL: tree stays balanced, height ≈ log₂(6) ≈ 2–3.

💡

AVL vs Red-Black Trees

AVL trees are more strictly balanced (height at most 1.44 log n) so lookups are slightly faster. Red-Black trees allow slightly more imbalance but require fewer rotations on insert/delete, making them faster in write-heavy workloads. Python’s sortedcontainers.SortedList uses a different approach (B-tree like) rather than either.

Complexity Table

Operation	Time	Note
Search	O(log n)	Guaranteed balanced height
Insert	O(log n)	BST insert + at most 2 rotations
Delete	O(log n)	May need O(log n) rotations up the path
Rotation	O(1)	Just pointer reassignment
Space	O(n)	One height field per node