Red-Black tree — properties, rotations + recoloring (conceptual understanding)

3.4.8 · Coding › Trees

5 Properties (RULES kya hain)

Formula Height bound — derived, memorized nahi

Claim: $n$ internal nodes wale ek Red-Black tree ki height $h \leq 2 lo g_{2} (n + 1)$ hoti hai.

Step 1 — nodes ko black-height se count karo. Maano $bh$ = root ki black-height. Induction se prove karo ki $x$ par rooted subtree mein kam se kam $2^{bh (x)} - 1$ internal nodes hote hain.

Base: agar $x$ NIL hai, $bh = 0$ , aur $2^{0} - 1 = 0$ nodes. ✓
Step: har child ki black-height $\geq bh (x) - 1$ hoti hai (ek child tab black-count hota hai jab woh black ho). Induction se har child ke subtree mein $\geq 2^{bh (x) - 1} - 1$ nodes hain. Toh $n \geq 2 (2^{bh (x) - 1} - 1) + 1 = 2^{bh (x)} - 1.$ Yeh step kyun? Hum lower-bound kar rahe hain ki ek given black-height ke liye tree kitna mota hona chahiye — ek lamba tree wide hone ke liye forced bhi hai.

Step 2 — $bh$ ko real height $h$ se relate karo. Property 4 se, kisi bhi root path ke kam se kam aadhe nodes black hain, toh $bh (root) \geq h /2$ .

Step 3 — combine karo. $n \geq 2^{bh} - 1 \geq 2^{h /2} - 1 \Rightarrow n + 1 \geq 2^{h /2} \Rightarrow h \leq 2 lo g_{2} (n + 1) .$ Toh height $O (lo g n)$ hai. ∎

Do repair tools: rotation & recoloring

Figure — Red-Black tree — properties, rotations + recoloring (conceptual understanding)

Definition Rotation (ek

structural fix) Ek rotation teen nodes ko rearrange karta hai taaki height change ho sake jabki BST order preserve ho. $x$ par ek left rotation uske right child $y$ ko upar kheenchta hai:

    x                 y
   / \               / \
  a   y    ==>      x   c
     / \           / \
    b   c         a   b

$b$ , $y$ ke left se $x$ ke right par move ho jaata hai. Order valid rehti hai kyunki $a < x < b < y < c$ pehle bhi tha aur baad mein bhi. Rotation $O (1)$ pointer surgery hai.

Formula Insertion fixup KAISE kaam karta hai (red parent ke liye 3 cases)

Maano $z$ = naya red node, $p$ = parent, $g$ = grandparent, $u$ = uncle. Hum loop karte hain jab tak $p$ red hai.

Case 1 — uncle $u$ RED hai: $p$ → black, $u$ → black, $g$ → red color karo. $z = g$ set karo aur repeat karo. Kyun? $p, u$ ko black karna red-red remove karta hai aur har path ka black count equal rakhta hai (humne $g$ ke dono taraf ek black add kiya, aur $g$ se ek hata diya). Naya red $g$ uske parent se clash kar sakta hai, toh hum re-loop karte hain.

Case 2 — uncle BLACK, $z$ "inner" hai (zig-zag): $p$ par rotate karo taaki Case 3 mein convert ho jaye (line seedhi ho jaye). Kyun? Rotations seedhi line $g$ – $p$ – $z$ par hi clean kaam karti hain.

Case 3 — uncle BLACK, $z$ "outer" hai (seedhi line): $p$ → black, $g$ → red recolor karo, phir $g$ par rotate karo. Kyun? Yeh black $p$ ko upar lift karta hai taaki dono children paths equal black-height regain kar sakein, aur red-red disappear ho jaaye. Terminate ho jaata hai.

Aakhir mein, root ko black color karo (property 2 restore karta hai).

Worked example 1 — Recoloring (red uncle)

Worked example Us tree mein insert karo jahan uncle red hai

Start: $g = 10$ (black), $p = 5$ (red, left child), $u = 15$ (red, right child). $3$ insert karo.

Step 1: $3 < 10 <$ left jaao; $3 < 5$ left jaao → $3$ ko $5$ ka red left-child ki jagah rakho. Yeh step kyun? Pehle BST insert, default mein red color karo.

Step 2: Ab $5$ (red) ka red child $3$ hai → red-red violation. Uncle $u = 15$ dekho: red. Uncle kyun dekhte hain? Uncle ka color decide karta hai recolor vs rotate.

Step 3: Case 1 → recolor: $p = 5$ →black, $u = 15$ →black, $g = 10$ →red. $z = 10$ set karo. Kyun? Koi rotation nahi chahiye; black counts balanced rehte hain, problem upar float karti hai.

Step 4: $z = 10$ ab root hai → property 2 kehti hai root black hona chahiye → $10$ →black recolor karo. Ho gaya. Kyun? Root ko black force karna hamesha safe hai (har path mein equally 1 black add karta hai).

Worked example 2 — Rotation + recoloring (black uncle, seedhi line)

Worked example Ek empty RB tree mein

$1, 2, 3$ insert karo

$1$ insert karo: root, black color kiya.
$2$ insert karo: red, $1$ ka right child. Koi red-red nahi (parent black hai). OK.
$3$ insert karo: red, $2$ ka right child. Ab $2$ (red) ka red child $3$ hai → red-red. $3$ ka uncle = $1$ ka left child = NIL → black. Line $1$ – $2$ – $3$ seedhi hai (sab right) → Case 3.

Step 1: $p = 2$ →black, $g = 1$ →red recolor karo. Kyun? $2$ ko new black subtree root ki tarah lift karne ki taiyaari.

Step 2: $g = 1$ par left-rotate karo. Kyun? $2$ ko upar laata hai taaki woh $1$ aur $3$ dono ka parent ban sake.

Result: $2$ (black) children $1$ (red), $3$ (red) ke saath. Balanced, height 2, koi violations nahi. Kyun correct hai: Dono paths mein exactly ek black node ( $2$ ) hai → property 5 hold karta hai; koi red-red nahi → property 4 hold karta hai.

Common mistakes (Steel-manned)

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho ek family tree jahan har insaan red ya black shirt pehanta hai. Rule: red-shirt wala insaan apne red-shirt wale bachche nahi rakh sakta (do reds touch nahi ho sakte). Aur chahe tum kisi bhi path se neeche chalo, tumhe utni hi black shirts pass karni padti hain. Yeh rules secretly tree ko bahut lamba aur ek taraf jhukne se rokti hain. Jab ek naya baccha join karta hai (hamesha red shirt mein) aur kisi doosre red shirt wale ke paas khada hota hai, toh family ek quick fix karti hai: ya toh sab shirts swap karte hain (recoloring) ya kuch log seats swap karte hain (rotation) taaki rules hold ho sakein. Woh tidying tree ko chota rakhti hai, isliye kisi ko bhi dhundhna super fast rehta hai.

Active-recall flashcards

Naya RB node kis color ka hota hai, aur kyun?

Red — yeh sirf property 4 (red-red) violate kar sakta hai, jo fix karna aasaan hai, aur kabhi property-5 black-height balance nahi tootne deta.

Ek Red-Black tree ki property 4 batao.

Kisi red node ka red child nahi hota (do reds adjacent nahi hote).

Ek Red-Black tree ki property 5 batao.

Har root-to-NIL path mein same number of black nodes hote hain (equal black-height).

RB height

O (lo g n)

kyun hai?

Black-height

bh

wale ek subtree mein

\geq 2^{bh} - 1

nodes hote hain, aur

bh \geq h /2

hai, jo deta hai

h \leq 2 lo g_{2} (n + 1)

Insert fixup ke dauran rotate ki jagah recolor kab karte ho?

Jab uncle RED ho — parent & uncle black karo, grandparent red karo, phir upar move karo.

Insert fixup ke dauran rotate kab karte ho?

Jab uncle BLACK ho (ya NIL) — locally rotate + recolor karo; yeh terminate ho jaata hai.

Left rotation kya preserve karta hai?

BST in-order ordering (

a < x < b < y < c

pehle aur baad mein), jabki

O (1)

mein structure/height change karta hai.

Fixup ke end mein root ko black kyun recolor karna padta hai?

Recoloring loop ka last step hai; root ko black force karna har path mein equally ek black add karta hai, property 2 restore karta hai bina property 5 toode.

RB tree vs AVL tree balance guarantee?

RB: longest path

\leq 2 \times

shortest (looser, fewer rotations). AVL: subtree heights

\leq 1

differ karte hain (tighter, more rotations).

Kya NIL leaves black nodes mane jaate hain?

Haan — NIL sentinels real black leaves hain jo black-height count karne ke liye use hoti hain.

Insertion per rotations ki maximum kitni hoti hai?

Zyada se zyada 2 (constant) — yeh ek key reason hai ki RB updates saste hain.

Connections

Binary Search Tree — RB ek BST hai extra coloring invariants ke saath.
AVL Tree — tighter balance, more rotations; contrast trade-off.
Tree Rotations — shared $O (1)$ restructuring primitive.
Big-O Analysis — $O (lo g n)$ height proof.
2-3-4 Tree — RB trees 2-3-4 B-trees ki isometry hain (har black node + uske red children = ek B-tree node).
std::map / TreeMap internals — real-world implementations.