AVL tree

An AVL tree is a self-balancing Binary search tree. After every insertion or deletion, every node’s left and right subtrees have heights differing by at most 1. This guarantees the tree’s height stays at $O(\log n)$, so search/insert/delete all run in $O(\log n)$ regardless of input order.

Named for its inventors Adelson-Velsky and Landis (1962). The first self-balancing BST data structure.

Why balance matters

A plain BST built by inserting sorted data degenerates to a chain — every operation becomes $O(n)$ instead of $O(\log n)$. AVL fixes this by forcing the tree to stay roughly balanced via rotations whenever an insert or delete would push it out of balance.

Balance factor

For each node, define the balance factor:

$\text{BF}(T)=\text{height}(T.\text{left})-\text{height}(T.\text{right})$

(Some texts use $\text{height}(T.\text{right})-\text{height}(T.\text{left})$; either works as long as you’re consistent.)

• BF = +1 → left subtree is one taller.
• BF = 0 → equal heights.
• BF = −1 → right subtree is one taller.

A node is AVL-balanced when $|\text{BF}|\le 1$. The whole tree is AVL-balanced when every node is.

If an insertion or deletion makes some node’s BF reach $\pm 2$, that node is now imbalanced and needs fixing — via a rotation.

Heights

For computing balance factors:

int height(struct Node *N) {
    if (N == NULL) return -1;
    return 1 + max(height(N->left), height(N->right));
}
 
int getBalance(struct Node *t) {
    if (t == NULL) return 0;
    return height(t->left) - height(t->right);
}

Convention: a NULL node has height $-1$. A leaf has height $0$.

To avoid recomputing heights every time, store the height as a field in each node and update on insertion/deletion:

struct AVLNode {
    int data;
    int height;
    struct AVLNode *left;
    struct AVLNode *right;
};

Imbalance cases

When a node $z$ becomes imbalanced ($|\text{BF}(z)|=2$), the imbalance falls into one of four shapes based on where the inserted node is relative to $z$:

• Left-Left (LL): inserted into the left subtree’s left child.
• Right-Right (RR): inserted into the right subtree’s right child.
• Left-Right (LR): inserted into the left subtree’s right child.
• Right-Left (RL): inserted into the right subtree’s left child.

LL and RR are mirror images of each other; LR and RL are mirror images. So really there are two cases.

Case 1: single rotation (LL or RR)

For LL: rotate right at $z$. The left child becomes the new root of this subtree; $z$ becomes its right child.

In code:

struct Node *rightRotate(struct Node *y) {
    struct Node *x  = y->left;
    struct Node *T2 = x->right;
    
    // perform rotation
    x->right = y;
    y->left  = T2;
    
    // update heights
    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));
    
    return x;   // new root of this subtree
}

Mirror image for RR (left-rotate). The “T2” subtree (the right child of the new root) gets reattached as the left child of $y$ to preserve the BST ordering.

Case 2: double rotation (LR or RL)

LR can’t be fixed by a single right rotation — that would just shift the imbalance. Instead, do two rotations:

For LR:

1. Left-rotate the left child of $z$. This converts LR into LL.
2. Right-rotate $z$. This is the LL fix.

For RL: right-rotate the right child, then left-rotate $z$.

The double rotation looks complex but is just two single rotations applied in sequence.

Insert algorithm

After inserting like a regular BST:

1. Walk back up the path from the inserted node toward the root.
2. At each ancestor, recompute its balance factor.
3. If BF reaches $\pm 2$, identify which case (LL, RR, LR, RL) and perform the appropriate rotation.

After at most one rebalancing operation — either a single rotation (LL / RR) or a double rotation (LR / RL, which is two literal rotations performed in sequence) — the height of this subtree returns to what it was before the insert, so no further imbalances can arise above. So AVL insertion does at most one rebalancing event, which means at most 2 rotations counted literally (the two rotations of an LR or RL fix). Calling it “one rotation” is shorthand for one rebalancing event.

Delete algorithm

Similar, but rebalancing might propagate further up. After deleting, walk back up checking balance factors. A rotation may reduce a subtree’s height, which can cause a new imbalance at the ancestor — so rebalancing might continue all the way to the root.

In the worst case, AVL deletion does $O(\log n)$ rotations.

Big O

Operation	Average	Worst
Search	$O(\log n)$	$O(\log n)$
Insert	$O(\log n)$	$O(\log n)$
Delete	$O(\log n)$	$O(\log n)$

The worst case is also $O(\log n)$ — the whole point of AVL is that it never degrades to chain behavior.

The AVL property guarantees the tree’s height is at most about $1.44{\log }_{2}n$ — slightly worse than perfectly balanced (${\log }_{2}n$) but still asymptotically logarithmic.

AVL vs red-black

Both are self-balancing BSTs. AVL trees are more balanced (stricter invariant), so:

• AVL has slightly faster searches.
• AVL has slightly slower insertions/deletions (more rebalancing work).

Red-black trees use a looser invariant and are often preferred in practice (e.g., the C++ std::map and the Linux kernel’s process scheduler use red-black trees). Both achieve $O(\log n)$ for all operations.

For the alternative invariant, see Red-black tree. For the unbalanced base case, see Binary search tree.