AVL tree — balance factor, rotations (LL, RR, LR, RL), insert, delete

WHAT is an AVL tree?

WHY does $|BF|\le1$ guarantee $O(\log n)$ height?

Formula Minimum nodes of a height-

$h$ AVL tree — derived An AVL tree of height $h$ must have a root + two subtrees. To use the fewest nodes, make one subtree as short as allowed. The taller subtree has height $h-1$ ; the BF rule lets the other be $h-2$ . So: $N(h) = 1 + N(h-1) + N(h-2),\quad N(0)=1,\ N(-1)=0$ This is the Fibonacci recurrence shifted! In fact $N(h) = F_{h+3} - 1$ . Since $F_k \approx \phi^k/\sqrt5$ with $\phi=\frac{1+\sqrt5}{2}\approx1.618$ : $N(h) \sim \frac{\phi^{\,h+3}}{\sqrt5} \;\Rightarrow\; h \le \log_\phi N \approx 1.44\,\log_2 n$ WHY this matters: height is at most $\approx 1.44\log_2 n$ , so search/insert/delete are $O(\log n)$ . Done.

HOW: the four rotations

A rotation is a local re-pointering of 3 nodes that preserves the BST in-order ordering while reducing height. The shape of the imbalance tells you which one.

Let $z$ = first unbalanced node going up, $y$ = its taller child, $x$ = $y$ 's taller child.

Case	Shape	Fix
LL	$z$ left-heavy, inserted in $y$ 's left	one right rotation at $z$
RR	$z$ right-heavy, inserted in $y$ 's right	one left rotation at $z$
LR	$z$ left-heavy, inserted in $y$ 's right	left at $y$ , then right at $z$
RL	$z$ right-heavy, inserted in $y$ 's left	right at $y$ , then left at $z$

Figure — AVL tree — balance factor, rotations (LL, RR, LR, RL), insert, delete

Formula Right rotation (fixes LL) — pointer surgery

Node $z$ with left child $y$ , $y$ 's right subtree $T_2$ :

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

def rotateRight(z):
    y = z.left
    T2 = y.right
    y.right = z          # z becomes right child of y
    z.left  = T2         # z adopts y's old right subtree
    update_height(z)     # update LOWER node first
    update_height(y)
    return y             # y is the new subtree root

WHY in-order is preserved: in-order of original = $[\,x,\,T_2,\,z,\,T_3]$ ... wait, $=[T_1(x),\,y,\,T_2,\,z,\,T_3]$ . After rotation it's the same sequence. BST property intact. Left rotation (RR) is the mirror image: swap left↔right.

Insert algorithm

Definition AVL insert (recursive)

Do a normal BST insert (recurse, place leaf).
On the way back up, update_height(node).
Compute BF. If |BF|>1, identify case using BF and the key, rotate.

def insert(node, key):
    if node is None: return Node(key)
    if key < node.key:  node.left  = insert(node.left, key)
    elif key > node.key: node.right = insert(node.right, key)
    else: return node                      # no duplicates
    update_height(node)
    bf = balance(node)
    # LL
    if bf > 1 and key < node.left.key:  return rotateRight(node)
    # RR
    if bf < -1 and key > node.right.key: return rotateLeft(node)
    # LR
    if bf > 1 and key > node.left.key:
        node.left = rotateLeft(node.left); return rotateRight(node)
    # RL
    if bf < -1 and key < node.right.key:
        node.right = rotateRight(node.right); return rotateLeft(node)
    return node

Key fact: an insert needs at most ONE rotation (single or double) to restore balance everywhere.

Delete algorithm

Definition AVL delete

Standard BST delete (leaf → remove; one child → splice; two children → replace with in-order successor, then delete that successor).
Walk back up, update heights.
Rebalance using BF — but here decide the case from the children's BF, not from a key:

    bf = balance(node)
    if bf > 1:
        if balance(node.left) >= 0: return rotateRight(node)     # LL
        else: node.left = rotateLeft(node.left); return rotateRight(node)  # LR
    if bf < -1:
        if balance(node.right) <= 0: return rotateLeft(node)     # RR
        else: node.right = rotateRight(node.right); return rotateLeft(node) # RL

Difference from insert: a delete may trigger rotations at multiple levels (up to $O(\log n)$ of them), because fixing one node can shorten the subtree and unbalance an ancestor.

Worked examples

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine a tower of blocks where each block must have its left and right stacks almost the same height — never off by more than one. Every time you add or remove a block, you check from the spot upward: if one side got too tall, you tip the tower a little (a rotation) so it leans back to balanced. Because it never leans much, you can always find any block by going down only a few levels — fast! The "tip" comes in 4 flavors depending on which side got too tall and whether it's a straight lean or a zig-zag lean.

Flashcards

What is the balance factor of a node?

height(left) - height(right)

, allowed values

-1,0,+1

What height is assigned to an empty subtree?

-1

(so a leaf has height

0

Which rotation fixes an LL imbalance?

A single right rotation at the unbalanced node.

LR case fix?

rotateLeft(child) then rotateRight(node).

RL case fix?

rotateRight(child) then rotateLeft(node).

How do you tell LL from LR on insert?

Both are left-heavy (

BF=+2

); compare key with left child's key — smaller=LL, larger=LR.

Max rotations needed after one AVL insert?

One (single or double).

Why can delete need many rotations?

A rotation can shorten the subtree, unbalancing an ancestor, so you rebalance up to the root.

What recurrence gives the minimum nodes of a height-

h

AVL tree?

N(h)=1+N(h-1)+N(h-2)

— a shifted Fibonacci,

N(h)=F_{h+3}-1

Worst-case AVL height in terms of

n

\approx 1.44\log_2 n = O(\log n)

On rotation, update which node's height first?

The lower (child) node, then the parent.

Time complexity of search/insert/delete in AVL?

O(\log n)

each.

Connections

Binary Search Tree — AVL is a BST plus the balance invariant.
Tree Rotations — the shared primitive used by AVL and Red-Black Tree.
Red-Black Tree — looser balancing (height $\le 2\log n$ ), fewer rotations on delete.
Fibonacci Numbers — bounds the minimum node count / height.
Big-O Notation — why $O(\log n)$ height matters.
Heap vs AVL — both balanced, but heaps only order parent-child, not full in-order.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, normal BST ka problem ye hai ki agar tum sorted order me values insert karo (1,2,3,4,5), to tree ek seedhi line ban jaata hai — linked list jaisa — aur search $O(n)$ ho jaata hai. AVL tree isi problem ko solve karta hai: ye har node pe balance factor maintain karta hai, jo hai $height(left) - height(right)$ , aur ye sirf $-1, 0, +1$ ho sakta hai. Agar kisi node ka BF $+2$ ya $-2$ ho gaya, matlab tree imbalance ho gaya, to ek rotation karke usse seedha kar dete hain.

Char cases hote hain: LL (left side ke left me daala) → ek right rotation. RR (right ke right) → ek left rotation. LR (left ke right, zig-zag) → pehle child pe left, phir parent pe right. RL (right ke left) → pehle child pe right, phir parent pe left. Trick yaad rakho: same letters = single rotation, mixed letters = double rotation, aur hamesha heavy side ke opposite rotate karo.

Insert me ek important baat — ek insert ke baad maximum ek hi rotation lagti hai. Lekin delete me kayi levels pe rotation lag sakti hai, kyunki ek subtree chhota hone se uska ancestor imbalance ho sakta hai, isliye root tak rebalance karte raho. Rotation karte waqt hamesha neeche wale node ka height pehle update karo, phir upar wale ka.

Kyun important hai? Kyunki AVL ki height kabhi $\approx 1.44\log_2 n$ se zyada nahi hoti (Fibonacci se prove hota hai), isliye search, insert, delete sab guaranteed $O(\log n)$ . Interviews aur database indexing me ye concept bahut kaam aata hai.

AVL tree — balance factor, rotations (LL, RR, LR, RL), insert, delete

WHAT is an AVL tree?

WHY does $|BF|\le1$ guarantee $O(\log n)$ height?

HOW: the four rotations

Insert algorithm

Delete algorithm

Worked examples

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections