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

3.4.7 · Coding › Trees

$∣ B F ∣ \leq 1$ $O (lo g n)$ height guarantee kyun karta hai?

HOW: char rotations

Ek rotation ek local re-pointering of 3 nodes hai jo BST in-order ordering preserve karti hai jabki height reduce karti hai. Imbalance ki shape batati hai kaun si rotation lagani hai.

Maano $z$ = upar jaate waqt pehla unbalanced node, $y$ = uska taller child, $x$ = $y$ ka taller child.

Case	Shape	Fix
LL	$z$ left-heavy, $y$ ke left mein insert hua	$z$ par ek right rotation
RR	$z$ right-heavy, $y$ ke right mein insert hua	$z$ par ek left rotation
LR	$z$ left-heavy, $y$ ke right mein insert hua	$y$ par left, phir $z$ par right
RL	$z$ right-heavy, $y$ ke left mein insert hua	$y$ par right, phir $z$ par left

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

Formula Right rotation (LL fix karta hai) — pointer surgery

Node $z$ jiska left child $y$ hai, $y$ ka 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

In-order preserved kyun hota hai: original ka in-order = $[x, T_{2}, z, T_{3}]$ ... wait, $= [T_{1} (x), y, T_{2}, z, T_{3}]$ . Rotation ke baad yeh same sequence hai. BST property intact. Left rotation (RR) mirror image hai: left↔right swap karo.

Insert algorithm

Definition AVL insert (recursive)

Normal BST insert karo (recurse, leaf place karo).
Wapas upar jaate waqt, update_height(node).
BF compute karo. Agar |BF|>1, toh BF aur key se case identify karo, rotate karo.

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: ek insert ko har jagah balance restore karne ke liye at most EK rotation (single ya double) chahiye.

Delete algorithm

Definition AVL delete

Standard BST delete (leaf → remove; ek child → splice; do children → in-order successor se replace karo, phir woh successor delete karo).
Wapas upar walk karo, heights update karo.
BF se rebalance karo — lekin yahan case decide karo children ke BF se, key se nahi:

    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

Insert se difference: ek delete multiple levels par rotations trigger kar sakta hai (up to $O (lo g n)$ tak), kyunki ek node ko fix karna subtree ko chhota kar sakta hai aur ancestor ko unbalance kar sakta hai.

Worked examples

Common mistakes

Recall Feynman: 12 saal ke bachche ko explain karo

Socho blocks ka ek tower jisme har block ke left aur right stack almost same height hone chahiye — kabhi bhi ek se zyada off nahi. Jab bhi koi block add ya remove karo, us jagah se upar tak check karo: agar ek side bahut zyada lamba ho gaya, toh tower ko thoda tilt karo (ek rotation) taaki woh wapas balanced ho jaye. Kyunki yeh kabhi zyada nahi jhukata, tum hamesha koi bhi block sirf kuch levels neeche jaake dhundh sakte ho — fast! "Tilt" 4 tarah ke aate hain depending on kaun si side bahut lamba hua aur kya seedha jhukav hai ya zig-zag jhukav hai.

Flashcards

Kisi node ka balance factor kya hota hai?

h e i g h t (l e f t) - h e i g h t (r i g h t)

, allowed values

- 1, 0, + 1

Empty subtree ko kaunsi height assign ki jaati hai?

- 1

(isliye ek leaf ki height

0

hoti hai).

LL imbalance kaun si rotation fix karti hai?

Unbalanced node par ek single right rotation.

LR case fix?

rotateLeft(child) phir rotateRight(node).

RL case fix?

rotateRight(child) phir rotateLeft(node).

Insert par LL aur LR mein fark kaise pehchante hain?

Dono left-heavy hain (

B F = + 2

); key ko left child ki key se compare karo — chhota=LL, bada=LR.

Ek AVL insert ke baad max kitni rotations chahiyen?

Ek (single ya double).

Delete ko kaafi rotations kyun chahiyen?

Ek rotation subtree ko chhota kar sakti hai, ancestor ko unbalance kar sakti hai, isliye root tak rebalance karo.

Height-

h

AVL tree ke minimum nodes kaunsa recurrence deta hai?

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

— ek shifted Fibonacci,

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

n

ke terms mein worst-case AVL height?

\approx 1.44 lo g_{2} n = O (lo g n)

Rotation par kaunse node ki height pehle update karo?

Lower (child) node ki, phir parent ki.

AVL mein search/insert/delete ki time complexity?

O (lo g n)

har ek.

Connections

Binary Search Tree — AVL ek BST hai plus balance invariant.
Tree Rotations — woh shared primitive jo AVL aur Red-Black Tree dono use karte hain.
Red-Black Tree — looser balancing (height $\leq 2 lo g n$ ), delete par kam rotations.
Fibonacci Numbers — minimum node count / height ko bound karta hai.
Big-O Notation — $O (lo g n)$ height kyun matter karti hai.
Heap vs AVL — dono balanced hain, lekin heaps sirf parent-child order karte hain, full in-order nahi.

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

AVL tree KYA hota hai?

$∣ B F ∣ \leq 1$ $O (lo g n)$ height guarantee kyun karta hai?

HOW: char rotations

Insert algorithm

Delete algorithm

Worked examples

Common mistakes

Flashcards

Connections

Concept Map