BST — worst case O(n) — motivation for balancing

3.4.6 · Coding › Trees

WHAT is the problem?

"Kya BST fast hai?" ki poori kahaani ek sawaal par aati hai: $h$ kitna bada ho sakta hai?

WHY does height vary so wildly?

Same set of keys bahut alag tree shapes produce kar sakti hain, depending on insertion order.

Worked example Insert

$1, 2, 3, 4, 5$ in increasing order Har nayi key ab tak ki sabse badi hoti hai → woh hamesha right mein jaati hai.

Yeh step kyun? Har insert current node se compare karta hai; kyunki key hamesha badi hoti hai, woh hamesha right jaati hai aur kabhi branch nahi karti. Tree ek linked list mein degenerate ho jaati hai. Yahan $h = n - 1 = 4$ .

Worked example Insert

$3, 1, 4, 2, 5$ (ek "balanced-ish" order)

Yeh step kyun? Inserts ab left aur right dono taraf jaate hain, isliye tree choti rehti hai. Yahan $h = 2$ hai, same keys ke liye $4$ se kaafi chhota.

Toh keys identical hain, lekin performance mein $n$ ka factor ka difference hai — sirf shape ki wajah se.

HOW bad / good can it get? (Derive the bounds)

Worst case height — derive $h = n - 1$

$h_{m a x} (n)$ ko maximum possible height maano. Ek path jo har node ko use kare, ek per level:

level $0$ : root (1 node)
level $1$ : 1 node
...
level $n - 1$ : 1 node

$h_{m a x} (n) = n - 1 \Rightarrow worst-case op cost = O (n)$

Kyun? $n$ nodes aur ek node per level ke saath, aapko $n$ levels chahiye, level $0$ se $n - 1$ tak, isliye sabse lamba path $n - 1$ edges ka hoga. Koi bhi valid tree isse zyada oochi nahi ho sakti, kyunki height $\geq n$ wali tree ko $\geq n + 1$ nodes chahiye honge.

Best case height — derive $h = ⌊ lo g_{2} n ⌋$

Ek binary tree mein level $i$ mein zyada se zyada $2^{i}$ nodes ho sakte hain (har node ke $\leq 2$ children, har level par doubling). Saare $n$ nodes ko $h + 1$ full levels mein rakhne ke liye:

$n \leq 2^{0} + 2^{1} + \dots + 2^{h} = 2^{h + 1} - 1$

Yeh geometric sum kyun? Level $0$ mein $1 = 2^{0}$ , level $1$ mein $2 = 2^{1}$ , ..., level $h$ mein zyada se zyada $2^{h}$ hain. Ratio 2 wali geometric series ka sum: $\sum_{i = 0}^{h} 2^{i} = 2^{h + 1} - 1$ .

$h$ ke liye solve karte hain:

$n \leq 2^{h + 1} - 1 \Rightarrow n + 1 \leq 2^{h + 1} \Rightarrow h \geq lo g_{2} (n + 1) - 1$

Figure — BST — worst case O(n) — motivation for balancing

WHY this motivates balancing

Ek plain BST koi guarantee nahi deta. Agar aapka data sorted aata hai (bahut common — logs, IDs, time series!), aap silently $O (n)$ trap mein gir jaate ho aur aapka "fast" tree ek slow linked list hai extra pointers ke saath.

Common Mistakes

Active Recall

BST mein search/insert/delete ki cost kya determine karta hai?

Tree ki height

h

; teeno

O (h)

hain.

n

nodes wale BST ki worst-case height kya hai, aur kaun sa insertion order yeh cause karta hai?

h = n - 1

(yaani

O (n)

); sorted (increasing ya decreasing) order mein keys insert karne se hota hai, ek degenerate "stick" banta hai.

n

nodes wale BST ki best-case (minimum) height kya hai?

⌊ lo g_{2} n ⌋

, tab achieve hoti hai jab har level filled ho (perfectly/completely balanced).

Level

i

par maximum

2^{i}

nodes kyun hote hain?

Har node ke zyada se zyada 2 children hote hain, isliye node count har level par at most double hota hai:

2^{0}, 2^{1}, \dots, 2^{i}

Height

h

wale binary tree mein max nodes derive karo.

\sum_{i = 0}^{h} 2^{i} = 2^{h + 1} - 1

, ek geometric series.

Plain BST

O (lo g n)

guarantee kyun NAHI karta?

Uski height insertion order par depend karti hai; sorted input use linked list mein degenerate karta hai jahan

h = n - 1

Self-balancing BSTs (AVL, Red-Black) kya guarantee karte hain, aur kaise?

Yeh

h = O (lo g n)

hamesha maintain karte hain insert/delete par restructuring (rotations) karke, input order se regardless.

Ek degenerate BST kaunsi simpler data structure ki tarah behave karta hai?

Ek linked list (

O (n)

search).

Recall Feynman: explain to a 12-year-old

Socho tum ek phone book mein koi naam dhundh rahe ho. Agar book sorted hai, tum beech mein flip karo aur turant aadha phenk do — yeh super fast hai. BST usi tarah kaam karna chahta hai: har step tree ka aadha phenk deta hai. Lekin agar tum tree aise naam add karke banate ho jo already order mein hain (Anna, Bob, Carl, Dan...), toh tree ek lambi seedhi ladder ki tarah badhti hai, ek step at a time — kuch bhi nahi phenkta! Ab koi naam dhundhna matlab poori ladder chadhna, ek rung at a time. Yeh slow hai. Isliye smart logon ne "balancing" invent ki: jab bhi ladder lean karna shuru kare, tree khud ko wapas ek acchi bushy shape mein shuffle kar leti hai, taaki tum hamesha aadha phenk sako. Hamesha fast!

Connections

Binary Search Tree — definition and property
Tree height and depth
Binary Search — divide and conquer
AVL Trees — rotations and balance factor
Red-Black Trees
Linked List — O(n) search
Big-O notation
Geometric series