AVL Tree Visualizer

How it works

1. Insert or delete the key exactly as in an ordinary binary search tree.
2. Walk back up from the changed spot towards the root, recomputing each ancestor's height = 1 + max(height(left), height(right)).
3. Compute its balance factor bf = height(left) − height(right).
4. If bf is +2 or −2 the node is unbalanced: name the case — LL, RR, LR or RL — from the direction of its taller child and grandchild.
5. Fix it with a single rotation (LL, RR) or a double rotation (LR, RL); the subtree is balanced again.
6. After an insert one fix is enough and the walk stops; after a delete keep walking up while the subtree got shorter, because more ancestors may need rotations.

Height and balance factor

The height of a node is the number of nodes on the longest path from it down to a leaf. This visualizer counts a leaf as height 1 and an empty subtree as 0; many textbooks count edges instead (0 and −1), but the differences — and so the balance factors — come out the same. The balance factor is height(left) − height(right), and in an AVL tree it is −1, 0 or +1 at every node. Switch on Height & balance to see both numbers on each node.

Storing the height in each node is what makes the check cheap: after an update only the nodes on the path back to the root can change, so the repair walk costs O(log n).

Worked example: inserting sorted keys

Insert 1, 2, 3, 4, 5, 6, 7 into a plain BST and you get a chain seven levels tall. In an AVL tree:

• Inserting 3 makes node 1 right-heavy (bf −2) along a straight line, so a left rotation at 1 lifts 2 to the root.
• Inserting 5 unbalances 3 the same way: left rotation at 3.
• Inserting 6 unbalances the root 2: left rotation at 2, and 4 becomes the root.
• Inserting 7 unbalances 5: left rotation at 5.

After four rotations the tree is perfect: 4 at the root, 2 and 6 below it, and 1, 3, 5, 7 as leaves — height 3 instead of 7. The Sorted 10…70 preset replays the same thing with every retrace and rotation animated.

Why the height stays logarithmic

Picture the sparsest AVL tree of height h: a root whose subtrees are the sparsest trees of heights h − 1 and h − 2. Its node count follows N(h) = N(h − 1) + N(h − 2) + 1, a Fibonacci-style recurrence, so N(h) grows like φʰ with φ ≈ 1.618. Turned around, a tree with n nodes has height at most about 1.44·log₂(n + 2). A perfectly balanced tree needs log₂ n levels, so even the worst AVL tree is only about 44% taller — and every operation stays O(log n).

AVL vs red-black tree vs plain BST

• Plain BST: no balance information; height anywhere between log₂ n and n, depending on insertion order.
• AVL tree: strict balance (height ≤ about 1.44·log₂ n), so lookups touch the fewest nodes. The price is a height or balance field per node and more rebalancing work — a delete may rotate at every level.
• Red-black tree: looser balance (height ≤ 2·log₂(n + 1)) but cheaper updates: at most two rotations per insert and three per delete. That is why Java's TreeMap, C++'s std::map and the Linux kernel's CPU scheduler use red-black trees.
• B-tree: many keys per node and every leaf at the same depth — the choice for disks and databases.

Pick an AVL tree when lookups dominate (an index built once and queried often); pick a red-black tree when inserts and deletes are frequent.

Common mistakes

• Updating heights in the wrong order after a rotation. Recompute the node that moved down (z) before the node that moved up (y), because y's height depends on z's.
• Choosing a double rotation when the taller child is even. After a delete, the taller child can have balance factor 0; a single rotation is correct then.
• Stopping too early after a delete. An insert needs at most one single or double rotation, but a delete can need one at every level up to the root.
• Forgetting to reconnect the rotated subtree to its parent, or to update the root pointer when the root itself rotates.

Time and space complexity

AVL Tree in Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1                # a leaf has height 1
        self.bf = 0                    # balance factor h(left) - h(right)


def h(n):
    return n.height if n else 0        # an empty subtree has height 0


def update(n):
    n.height = 1 + max(h(n.left), h(n.right))
    n.bf = h(n.left) - h(n.right)


def replace(root, parent, old, new):
    """Put `new` where `old` hangs under `parent`; returns the root."""
    if parent is None:
        return new                     # old was the root
    if parent.left is old:
        parent.left = new
    else:
        parent.right = new
    return root


def insert(root, key):
    if root is None:
        return Node(key)
    path = []                          # root ... parent, for the walk back up
    cur = root
    while cur is not None:
        if key == cur.key:
            return root                # duplicate
        parent = cur
        path.append(parent)
        if key < cur.key:
            cur = cur.left
        else:
            cur = cur.right
    if key < parent.key:
        parent.left = Node(key)
    else:
        parent.right = Node(key)
    return retrace(root, path)         # for n <- parent ... root


def retrace(root, path):
    """Walk back up path (root first): refresh heights, rotate where |bf| > 1."""
    for i in range(len(path) - 1, -1, -1):
        n = path[i]
        old_height = n.height
        hL, hR = h(n.left), h(n.right)
        n.height = 1 + max(hL, hR)
        n.bf = hL - hR
        if abs(n.bf) > 1:
            top = rebalance(n)         # see rebalance()
            root = replace(root, path[i - 1] if i > 0 else None, n, top)
            n = top
        if n.height == old_height:
            break                      # height unchanged: ancestors are fine
    return root


def rebalance(z):
    if z.bf > 1:                       # left-heavy
        if z.left.bf < 0:              # LR zig-zag
            z.left = rotate_left(z.left)
        return rotate_right(z)         # LL
    if z.bf < -1:                      # right-heavy
        if z.right.bf > 0:             # RL zig-zag
            z.right = rotate_right(z.right)
        return rotate_left(z)          # RR
    return z                           # balanced


def rotate_right(z):
    y = z.left                         # pivot
    T2 = y.right                       # moves over to z
    y.right = z                        # z goes down
    z.left = T2
    update(z)                          # z first: it is now below y
    update(y)
    return y                           # new root of this subtree


def rotate_left(z):
    y = z.right                        # pivot
    T2 = y.left                        # moves over to z
    y.left = z                         # z goes down
    z.right = T2
    update(z)                          # z first: it is now below y
    update(y)
    return y                           # new root of this subtree

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• AVL Rotations — LL, RR, LR, RLAVL tree rotations explained: spot the LL, RR, LR and RL cases from balance factors and fix each with a single or double rotation — animated step by step.
• Binary Search Tree VisualizerBinary search tree visualizer: insert, search and delete keys step by step, see why every operation costs O(h), and compare a plain BST with AVL and B-trees.
• BST Deletion — All Three CasesHow to delete a node from a binary search tree: the leaf, one-child and two-children cases, in-order successor or predecessor, with an animated example.
• Tree Traversal Visualizer — Inorder, Preorder, Postorder, Level OrderVisualize inorder, preorder, postorder and level-order tree traversal on one tree: the visit order, the call stack or queue, the code, and when to use each.
• B-Tree VisualizerB-tree visualizer: insert, search and delete keys in a B-tree of order 3 to 7, watch nodes split, borrow and merge, and see why databases are built on B-trees.