पाठ · #10 / 11

संतुलित पेड़ (Balanced Trees)

घुमाव (rotations) ऊँचाई को ≈ log n रखते हैं, चाहे insert क्रम कुछ भी हो

AVL tree · self-balancing rotations

size0

avl height0

naïve bst h.0

init

value

खुद आज़माएँ: एक पतित (degenerate) अनुक्रम पर मजबूर करने के लिए insert 1..15 दबाइए। भोले BST की ऊँचाई उछलकर 15 हो जाती है; AVL की ऊँचाई 4 पर ही टिकी रहती है — क्योंकि हर असंतुलन एक घुमाव छेड़ता है, जो canvas पर चमकता है।

यह क्यों मायने रखता है

आम BST बिगड़कर O(n) हो सकते हैं। संतुलित पेड़ डालने और हटाने के बाद अपने-आप पुनर्संतुलन करके O(log n) की गारंटी देते हैं। AVL और Red-Black पेड़ ज़्यादातर भाषाओं की मानक लाइब्रेरियों के पीछे का दमख़म हैं।

मूल विचार

याद है कैसे क्रमबद्ध डेटा डालने पर एक BST लिंक्ड लिस्ट बन सकता है? संतुलित पेड़ ऑपरेशनों के बाद ढाँचा फिर से गढ़कर इसे रोकते हैं।

AVL पेड़: हर insert/delete के बाद जाँचिए कि क्या किसी नोड के उपवृक्षों की ऊँचाई में 1 से ज़्यादा का फ़र्क़ है। अगर है, तो उसे ठीक करने के लिए घुमाइए (rotate)।

घुमाव (rotations) जादुई चाल हैं:

दायाँ घुमाव: जब बायाँ उपवृक्ष बहुत ऊँचा हो
बायाँ घुमाव: जब दायाँ उपवृक्ष बहुत ऊँचा हो
दोहरा घुमाव: टेढ़े-मेढ़े (zig-zag) मामलों के लिए

नतीजा: ऊँचाई हमेशा O(log n) रहती है, इसलिए सारे ऑपरेशन पक्के तौर पर O(log n) बने रहते हैं।

Red-Black पेड़ एक अलग तरकीब इस्तेमाल करते हैं: नोडों को लाल या काला रंग देते हैं, ऐसे नियमों के साथ जो सीमित करते हैं कि पेड़ कितना असंतुलित हो सकता है। AVL से कम सख़्ती से संतुलित, पर औसतन कम घुमाव।

मुख्य बातें

डालने के क्रम की परवाह किए बिना O(log n) ऑपरेशन की गारंटी
घुमाव O(1) ऑपरेशन हैं जो BST गुण को बनाए रखते हैं
AVL: सख़्त संतुलन (ऊँचाई-अंतर ≤ 1)
Red-Black: ढीला संतुलन, कम घुमाव

अपरिवर्तनी (Invariants)

ये पेड़ BST invariant को विरासत में लेते हैं और ऊपर एक संतुलन नियम जोड़ते हैं। यही संतुलन नियम O(log n) ऊँचाई की गारंटी देता है।

AVL invariant: हर नोड के लिए, |height(left) − height(right)| ≤ 1। हर insert और delete के बाद घुमावों के ज़रिए सख़्ती से लागू।; परिणाम: ऊँचाई h < 1.44 · log₂(n + 2) — सैद्धांतिक न्यूनतम के 44% के भीतर।
Red-Black invariants — चारों का टिकना ज़रूरी है: 1. हर नोड या तो लाल या काला रंगा होता है।; 2. root काला है। (कभी-कभी यूँ कहते हैं: पत्तियाँ — NULL sentinel — भी काली हैं।); 3. किसी लाल नोड के सिर्फ़ काले बच्चे होते हैं। (किसी भी root-से-पत्ती पथ पर लगातार दो लाल नहीं।); 4. हर root-से-NULL पथ एक ही संख्या में काले नोडों से गुज़रता है। यही black-height है; यही वह संरचनात्मक invariant है जो पेड़ की ऊँचाई को बाँधता है।; परिणाम: ऊँचाई h ≤ 2 · log₂(n + 1)। AVL से ढीला पर बनाए रखने में आसान।

और गहराई में

AVL बनाम Red-Black — किसे चुनें

| गुण | AVL | Red-Black | |---|---|---| | Worst-case ऊँचाई | ≤ 1.44 log₂ n | ≤ 2 log₂ n | | प्रति insert घुमाव | 2 तक | 2 तक | | प्रति delete घुमाव | O(log n) तक | 3 तक | | Lookup रफ़्तार | ज़रा तेज़ (ज़्यादा संतुलित) | ज़रा धीमी | | Insert/delete रफ़्तार | धीमी | तेज़ | | प्रति नोड मेमोरी | 1–2 बिट (balance factor) | 1 बिट (रंग) | | आम उपयोग | डेटाबेस, read-heavy | भाषा stdlib std::map, TreeMap, Linux कर्नेल rbtree.h |

अनुभवसिद्ध नियम: अगर आप लिखने से कहीं ज़्यादा पढ़ते हैं, तो AVL। अगर आपका काम मिला-जुला या write-heavy है, तो Red-Black। C++ का std::map, Java का TreeMap, और Linux कर्नेल का प्रोसेस शेड्यूलर सभी इसी वजह से Red-Black इस्तेमाल करते हैं।

B-tree — डिस्क-पेज वाला सामान्यीकरण

एक B-tree BST को एक दिशा में सामान्यीकृत करता है: हर नोड कई key रखता है (मान लीजिए 100 से 1000), सिर्फ़ एक नहीं। अगर किसी नोड की k key हों तो उसके k + 1 बच्चे होते हैं, और बच्चों की key-रेंज माता-पिता की key के साथ गुँथी रहती हैं (key₀ के बाएँ → child₀, key₀ और key₁ के बीच → child₁, …)।

प्रति नोड इतनी key क्यों? डिस्क seek। घूमती डिस्क पर, 1 बाइट पढ़ना और 16 KB पढ़ना मूलतः एक ही समय लेते हैं — क़ीमत head के हिलने की है, हस्तांतरित बाइटों की नहीं। डेटाबेस इंजन हर B-tree नोड को ठीक एक डिस्क पेज (आम तौर पर 4 KB या 16 KB) में फ़िट करने के लिए भर देते हैं। एक डिस्क पठन एक बार में ~256–1024 key ले आता है, इसलिए अरबों पंक्तियों के डेटाबेस में navigate करने में सिर्फ़ 3–4 पेज पठन लगते हैं। यही तर्क SSD पर भी लागू होता है (जहाँ seek लागत page-aligned I/O से तय होती है) और फ़ाइलसिस्टम inode पर भी।

हर रिलेशनल डेटाबेस इंडेक्स, हर आधुनिक फ़ाइलसिस्टम (ext4, NTFS, APFS, XFS), और ज़्यादातर key-value भंडार (RocksDB, LevelDB) B-tree या उसके क़रीबी चचेरे भाई B+-tree का इस्तेमाल करते हैं (जहाँ तेज़ रेंज स्कैन के लिए पत्ती-नोड एक लिंक्ड लिस्ट बनाते हैं)। B-tree ही वजह हैं कि एक अरब-पंक्ति टेबल पर SELECT * WHERE id BETWEEN 1000 AND 2000 एक मिलीसेकंड से भी कम में होता है।

असल दुनिया के लागत आँकड़े

n = 1,000,000 key वाले एक संतुलित पेड़ के लिए:

Lookup: ~20 तुलनाएँ (log₂ 1M ≈ 20)
मेमोरी: ~24 MB (प्रति नोड 24 B मानते हुए — 3 पॉइंटर + 4-बाइट key)

key से क्रमबद्ध एक ऐरे से तुलना कीजिए:

Lookup: ~20 तुलनाएँ (binary search, वही log₂ n)
मेमोरी: ~4 MB (बस key, कोई पॉइंटर नहीं)
Insert: O(n) — ऐरे का खिसकाव

तो अगर आपका डेटासेट read-only है और मेमोरी में अँट जाता है, तो एक क्रमबद्ध ऐरे रफ़्तार (कैश लोकैलिटी) और मेमोरी दोनों में एक संतुलित पेड़ को मात देता है। संतुलित पेड़ अपना बोझ O(log n) insert बनाए रखने के लिए चुकाते हैं।

गणितीय ब्यौरा

AVL Balance Factor: BF(n) = height(n.left) - height(n.right); Must be in 1
Time Complexity (guaranteed): Search: O(log n); Insert: O(log n); Delete: O(log n)
Height bounds: AVL: h < 1.44 log_2(n+2); Red-Black: h leq 2 log_2(n+1)

क्रियान्वयन (Implementation)

घुमाव की अवधारणा

// Right rotation when left subtree too tall
//       y                x
//      / \              / \
//     x   C   --->     A   y
//    / \                  / \
//   A   B                B   C

fn rotate_right(y: Node) -> Node {
    let x = y.left.take();
    y.left = x.right;
    x.right = Some(y);
    x
}

कब इस्तेमाल करें

पक्की O(log n) कार्यक्षमता चाहिए
डेटा क्रमबद्ध/लगभग-क्रमबद्ध क्रम में आता है
map, set, priority queue बनाना
डेटाबेस इंडेक्स

अभ्यास

हर स्व-संतुलित पेड़ इम्प्लीमेंटेशन के साथ चलने वाली जाँच:

Is Binary Tree Height-Balanced? — आसान · sentinel-आधारित early-exit वाला O(n) post-order पास; वही जो आप हर AVL / Red-Black घुमाव के बाद दावे के तौर पर जाँचते हैं

→ सभी अभ्यास सवाल देखें

⚖️ संतुलित पेड़ (Balanced Trees)