AVL Tree

A binary search tree that keeps the left/right height difference at most 1 at every node, rebalancing itself with rotations.

Worth knowing first

Binary Search Tree (BST)

#How does it work?

The AVL tree is the first self-balancing binary search tree (Adelson-Velsky and Landis, 1962). Insert sorted values such as 10, 20, 30, 40 into a plain BST and it turns into a chain, making search O(n). An AVL tree doesn't allow that.

For each node, balance factor = height of the left subtree − height of the right subtree. The AVL rule: it must be −1, 0 or +1 at every node.

After an insert, if a node on the path from the root to the new node reaches ±2, one or two rotations fix it. A rotation moves one node up and another down without breaking the BST order.

There are four cases: LL (left-left) takes a single right rotation, RR a single left rotation; LR and RL take a double rotation, first at the child and then at the unbalanced node.

#Try it yourself

$ avl_tree --interactive

-1

Insert a value and watch the balance: the number next to each node is its balance factor (left height − right height). At ±2 a rotation fixes it.

ValueSpeed

Elements: 6/12VisitingNewRemovingFound / read

#Basic operations

insert(x): Inserts like a BST, then checks balance factors on the way up and rotates when needed.
search(x): A plain BST search; because the tree is balanced it takes at most O(log n) steps.
delete(x): Deletes like a BST, then fixes unbalanced nodes up to the root with rotations (more than one may be needed).
rotateLeft / rotateRight: Lifts a node's right (or left) child into its place; the in-order sequence stays the same, only heights change.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from typing import Optional


class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Optional["Node"] = None
        self.right: Optional["Node"] = None
        self.height = 1  # height of the subtree rooted here


def height(node: Optional[Node]) -> int:
    return node.height if node else 0


def update(node: Node) -> None:
    node.height = 1 + max(height(node.left), height(node.right))


def balance(node: Node) -> int:
    return height(node.left) - height(node.right)


def rotate_right(y: Node) -> Node:
    x = y.left
    y.left = x.right
    x.right = y
    update(y)
    update(x)
    return x  # new root of this subtree


def rotate_left(x: Node) -> Node:
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y


def insert(node: Optional[Node], value: int) -> Node:
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    else:
        return node  # no duplicates
    update(node)
    b = balance(node)
    if b > 1 and value < node.left.value:  # LL
        return rotate_right(node)
    if b > 1:  # LR
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if b < -1 and value > node.right.value:  # RR
        return rotate_left(node)
    if b < -1:  # RL
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node


def inorder(node: Optional[Node], out: list) -> list:
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)
    return out


root = None
for v in [10, 20, 30, 40, 50, 25]:
    root = insert(root, v)

print(" ".join(map(str, inorder(root, []))))  # 10 20 25 30 40 50
print(root.value)                             # 30: rotations moved it up
print(root.height)                            # 3, not 6 like a plain BST

#Complexity

Operation	Time
search	O(log n)
insert	O(log n)
delete	O(log n)
One rotation	O(1)
Memory	O(n)

An AVL tree's height is at most about 1.44 · log2(n), so every operation is O(log n) even in the worst case. It is more strictly balanced than a red-black tree: lookups are slightly faster, inserts need slightly more rotations. Real implementations store the height in each node; the animation recomputes it at every step.

#When to use it?

AVL fits when reads far outnumber writes and lookups must be fast even in the worst case: in-memory indexes, dictionaries, ordered sets and maps. With frequent inserts and deletes a red-black tree usually does less work.

#Practice

Easy

1/3

How is a node's balance factor computed in an AVL tree?

1Left subtree height − right subtree height
2Left child value − right child value
3The node's depth
4The number of nodes below it

1–4 pick · ← → move · enter continue

Medium

1/1

Inserting 10, 20, 30 into an empty AVL tree causes which case, and what becomes the root?

1The RR case; root 20
2The LL case; root 10
3The LR case; root 30
4No rotation; root 10

1–4 pick · ← → move · enter continue

Hard

1/1

Inserting 30, 10, 20 (the LR case) takes which rotations?

1Left around 10, then right around 30
2Only right around 30
3Left around 30, then right around 10
4Only left around 10

1–4 pick · ← → move · enter continue

#Up next

Lessons that build on this one:

Red-Black Tree