data structures · first self-balancing tree · guarantees O(log n)

AVL Tree

The binary search tree promised O(log n) search, insertion, and deletion — with one silent condition: if the tree stays balanced. Insert already-sorted data into a plain BST and every node becomes the last one's only child; the "tree" is a straight line and every operation degrades to O(n), exactly as bad as a linked list. An AVL tree closes that gap. It's the same binary search tree, plus one rule enforced after every insert: for every node, the heights of its left and right subtrees differ by at most 1. Whenever an insertion would break that rule, the tree repairs itself on the way back up by rotating a small number of nodes — a local, O(1) restructuring — and the height-balance guarantee turns back into a real O(log n) bound on every operation, no matter what order the data arrives in.

Try it

Insert a number and watch it walk down like a normal BST insert, then watch the tree repair itself if a rotation fires — the nodes involved light up and the log names the case. The tree below was built by inserting 1 through 7 in ascending order — precisely the sequence that turns a plain BST into a straight line. Try typing 8, 9, 10 to keep extending it in sorted order and watch it stay bushy instead of growing into a line. Search works exactly like a BST search — there's no rebalancing to watch, since search never changes the tree, so a found or missed value just lights up the path. Delete does a normal BST delete (leaf, one child, or two children via in-order successor — same three cases as a plain binary search tree) and then rebalances at every level on the way back up, not just the lowest one — unlike insert, a single delete can trigger more than one rotation. Delete a few values out of the sorted tree above and watch the log report every rotation that fired, not just the first.

value

Loaded by inserting 1 through 7 in ascending order. Hover a node for its height/balance factor.

Core operations

insert(x) — a normal BST insert (walk left/right by comparison until you fall off the tree, attach a new node there), then unwind back up the recursion: at each ancestor, recompute its height and balance factor (left subtree height minus right subtree height), and if the magnitude exceeds 1, rotate to fix it. O(log n), guaranteed — not just on average, since the tree can never become unbalanced enough to degrade.
search(x) — identical to a plain BST search: compare and go left or right until you find x or fall off the tree. Nothing about AVL changes this step; it's the height guarantee that makes its cost reliably O(log n) rather than a hopeful average.
delete(x) — same idea as insert in reverse: do a normal BST delete, then rebalance on the way back up. The wrinkle (see Pitfalls) is that a single delete can require rebalancing at multiple levels, not just one, unlike insert — the reference implementation below handles this by calling the same rebalance step at every ancestor as the recursion unwinds, rather than stopping at the first fix.

Rotations

A node's balance factor is height(left) − height(right). In a valid AVL tree every node's balance factor is -1, 0, or 1. An insert can only ever push one node's balance factor to +2 or -2 — and it's always the lowest node on the insertion path where that happens. Which of four cases applies depends on which side is heavy and which side of that side the new node landed on:

Left-Left (balance +2, left child also left-heavy or balanced): single right rotation

      z                     y
     / \                   /   \
    y   T4     ---->      x     z
   / \                    / \   / \
  x  T3                 T1 T2 T3 T4
 / \
T1 T2

Right-Right (balance -2, right child also right-heavy or balanced): single left rotation,
the mirror image of the above.

Left-Right (balance +2, but left child is right-heavy): rotate the left child left first,
which turns it into the Left-Left shape above, then rotate the whole subtree right.

      z                    z                       x
     / \                  / \                     /   \
    y   T4    ---->      x   T4     ---->        y     z
   / \                  / \                      / \   / \
  T1  x                y  T3                   T1  T2 T3 T4
     / \               / \
    T2 T3             T1 T2

Right-Left (balance -2, but right child is left-heavy): the mirror image — rotate the right
child right first, then rotate the whole subtree left.

Every rotation is a constant number of pointer swaps — it doesn't walk any subtree, it just reattaches a handful of pointers and recomputes a couple of heights. And because the rebalanced subtree's height afterward is exactly what it was before the insertion that triggered it, fixing the lowest unbalanced node is always enough: no ancestor further up can have become unbalanced by an insert that didn't change the subtree's height. That's why insert needs at most one rotation (single or double) per call, ever.

Reference implementation

class AVLTree {
  #root = null;

  insert(x) {
    this.#root = this.#insertNode(this.#root, x);
  }

  #insertNode(node, x) {
    if (node === null) return { value: x, left: null, right: null, height: 1 };
    if (x === node.value) return node; // duplicates ignored
    if (x < node.value) node.left = this.#insertNode(node.left, x);
    else node.right = this.#insertNode(node.right, x);
    return this.#rebalance(node);
  }

  #height(node) { return node === null ? 0 : node.height; }
  #balanceFactor(node) { return this.#height(node.left) - this.#height(node.right); }
  #updateHeight(node) { node.height = 1 + Math.max(this.#height(node.left), this.#height(node.right)); }

  #rotateRight(node) {
    const newRoot = node.left;
    node.left = newRoot.right;
    newRoot.right = node;
    this.#updateHeight(node);
    this.#updateHeight(newRoot);
    return newRoot;
  }

  #rotateLeft(node) {
    const newRoot = node.right;
    node.right = newRoot.left;
    newRoot.left = node;
    this.#updateHeight(node);
    this.#updateHeight(newRoot);
    return newRoot;
  }

  #rebalance(node) {
    this.#updateHeight(node);
    const balance = this.#balanceFactor(node);
    if (balance > 1) {
      if (this.#balanceFactor(node.left) < 0) node.left = this.#rotateLeft(node.left); // Left-Right
      return this.#rotateRight(node); // Left-Left (or Left-Right, after the fix above)
    }
    if (balance < -1) {
      if (this.#balanceFactor(node.right) > 0) node.right = this.#rotateRight(node.right); // Right-Left
      return this.#rotateLeft(node); // Right-Right (or Right-Left, after the fix above)
    }
    return node;
  }

  delete(x) {
    this.#root = this.#deleteNode(this.#root, x);
  }

  #deleteNode(node, x) {
    if (node === null) return null; // not found, nothing to do
    if (x < node.value) { node.left = this.#deleteNode(node.left, x); return this.#rebalance(node); }
    if (x > node.value) { node.right = this.#deleteNode(node.right, x); return this.#rebalance(node); }
    // x === node.value: this is the node to remove
    if (node.left === null) return node.right;  // leaf or one-child(right) — already a valid AVL subtree
    if (node.right === null) return node.left;  // one-child(left) — same
    let succ = node.right;                       // two children: find in-order successor
    while (succ.left !== null) succ = succ.left;
    node.right = this.#deleteNode(node.right, succ.value);
    node.value = succ.value;
    return this.#rebalance(node);
  }

  contains(x) {
    let curr = this.#root;
    while (curr !== null) {
      if (x === curr.value) return true;
      curr = x < curr.value ? curr.left : curr.right;
    }
    return false;
  }

  inorder() {
    const out = [];
    const walk = (node) => {
      if (node === null) return;
      walk(node.left);
      out.push(node.value);
      walk(node.right);
    };
    walk(this.#root);
    return out;
  }
}

The rotation direction is decided purely from balance factors — this.#balanceFactor(node.left) < 0 means the left child leans right, so a straight right rotation on node alone wouldn't fix things; rotating the left child left first turns it into a plain left-heavy shape that the following right rotation on node resolves. No value comparisons are needed to pick the case, only the shape of the subtree. delete reuses that same #rebalance helper at every ancestor on the way back up the recursion, which is the whole trick to handling the multi-level case: insert only ever needs one rebalance call because it stops as soon as it makes one, but delete's recursive unwind calls #rebalance unconditionally at every level, so however many rotations are actually needed just happen, without any special-cased "keep going" logic. The interactive demo above uses an equivalent recursive insert/search/delete with extra bookkeeping to record the comparison path and which rotation(s) fired, purely to drive the highlighting and log text — the algorithm is identical. Verified with 3,000 randomized insert sequences (checking the AVL balance-factor invariant holds at every node after every single insert, not just at the end; that inorder() stays sorted; and that contains agrees with a plain JavaScript Set built from the same insertions), plus explicit ascending- and descending-sorted-insert runs up to 2,000 elements confirming the tree's height stays within the AVL worst-case bound (roughly 1.45 log₂(n)) rather than growing to n, plus edge cases (empty tree, single node, all-duplicate inserts). delete got its own pass: 8,000 randomized sequences of 120 interleaved insert/delete operations each against a plain JavaScript Set model, checking the balance invariant, inorder() sortedness, size, and contains agreement after every single operation (not just at the end), plus explicit edge cases (delete from an empty tree, delete the only node, delete an absent value, a deterministic tree exercising all three delete cases by hand, repeatedly deleting the root until empty, and a 500-element ascending-insert-then-descending-delete run). Both were re-verified by extracting the exact shipped insertAVL/searchAVL/ deleteAVL functions out of the HTML and re-running an equivalent pass directly against them. See /tmp/avl_test.js, /tmp/avl_delete_test.js, and /tmp/avl_page_verify.js, scratch, not committed.

Pitfalls

Delete can unbalance more than one ancestor; insert never can. A BST delete followed by rebalancing sounds like the same recipe as insert, but there's a real asymmetry. Insert can only ever unbalance the single lowest node on its path, because a rotation there restores that subtree's height to exactly what it was before the insert — so no ancestor further up ever sees a height change and needs fixing. Delete breaks that: removing a node can shorten a subtree, which can unbalance its parent; the rotation that fixes the parent can itself shorten that subtree further, unbalancing the parent's parent, and so on — potentially all the way to the root. The fix isn't more code, just less stopping: the reference implementation's #deleteNode calls #rebalance at every ancestor on the way back up unconditionally, rather than returning early after the first fix the way it would be tempting to write if you assumed (wrongly, for delete) that one rotation is always enough.

Balance factor by height, not by node count. A tree can hold 1 node on one side and 1,000 on the other and still be "balanced" by the AVL rule, if the 1,000-node side happens to be a bushy subtree of height 10 while the 1-node side is trivially height 1 — no, that example is already outside the rule (10 vs 1 fails), but the point generalizes: AVL guarantees balanced height, which bounds every operation's cost, but says nothing about how evenly values or node counts are split. That's fine — height is exactly the quantity that determines O(log n) vs O(n) — but it's easy to mentally conflate "balanced" with "even split" when they're not the same claim.

Rotations preserve the BST property — that's not an accident to re-verify by hand. A right rotation moves y up and z down, and reattaches y's old right subtree (T3 in the diagram above) as z's new left subtree. That's safe only because every value in T3 was already between y and z in sorted order — which is guaranteed by the BST invariant the tree already satisfied before the rotation. Rotations are a mechanical, invariant-preserving pointer shuffle; the reason they're safe is worth understanding once, not something to re-check per rotation.

Where AVL trees show up

Anywhere a BST's worst case is unacceptable. Sorted or near-sorted input is common in practice (imported data, timestamps, IDs), and a plain BST silently degrading to a linked list under exactly that input is the failure mode AVL trees exist to close off.
Red-black trees, the more common alternative. Most language standard libraries that offer an ordered map/set (balanced-tree variants of what binary-search-tree.html introduced) use red-black trees rather than AVL trees — they rebalance less aggressively (looser balance, cheaper deletes) at the cost of slightly deeper trees. Same underlying bet — bound the height to bound the cost — different tuning of how strict "balanced" needs to be.
Anywhere height, not just balance, matters directly. AVL's stricter balance (height factor within 1, vs red-black's looser bound) means faster lookups at the cost of more rotations per write — a reasonable choice specifically when reads dominate writes.
Skip lists, a non-tree alternative. Same bet — bound the expected cost of a search — reached without a tree or a rebalancing rule at all: elements flip coins to pick their own height across several linked lists instead. The trade runs the opposite direction from red-black's: no guaranteed worst case at all, only an expected one, in exchange for a genuinely simpler implementation.

Complexity

Time: insert, search/contains, and delete are all O(log n) — guaranteed, not just on average, since the height-balance invariant bounds the tree's height to O(log n) at all times. This is the entire improvement over a plain binary search tree, which has the same average case but degrades to O(n) in the worst case. Each rotation itself is O(1) — a fixed number of pointer reassignments — so rebalancing adds only a constant factor to the O(log n) walk back up to the root. Space: O(n) for n nodes, the same two child pointers per node as a plain BST plus one integer (the cached height) — a small, fixed overhead in exchange for a worst-case guarantee instead of a hopeful average.

See Choosing a Search Tree for how this stacks up against red-black, splay, and B-tree — including the measured height difference between AVL and red-black on the same input.