Data Structures
पाठ · #6 / 11

बाइनरी सर्च पेड़ (Binary Search Trees)

क्रम अंदर, log-समय बाहर

Binary search tree · path-walking search

size0
height0
compares0
init

खुद आज़माएँ: key insert कीजिए; search तुलना का रास्ता उजागर करता है। फिर break it दबाइए: क्रमबद्ध मानों को डालने से पेड़ ढहकर एक लिंक्ड लिस्ट बन जाता है — ऊँचाई log n से उछलकर n हो जाती है।

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

BST ऐरे की तेज़ खोज को लिंक्ड लिस्ट के लचीले डालने के साथ जोड़ देते हैं। ये set, map और डेटाबेस की बुनियाद हैं। BST को समझना संतुलित पेड़ों और कुशल खोज को समझने की कुंजी है।

मूल विचार

वह संख्या-अनुमान का खेल याद है? "यह बड़ा है या छोटा?" हर जवाब आधी संभावनाओं को छाँट देता है।

BST उसी खेल का पेड़-रूप है। हर नोड एक नियम मानता है: बाएँ बच्चे छोटे, दाएँ बच्चे बड़े।

किसी मान को ढूँढने के लिए:

  1. root से शुरू कीजिए
  2. अगर मान < नोड, तो बाएँ जाइए। अगर मान > नोड, तो दाएँ जाइए।
  3. तब तक दोहराइए जब तक मिल न जाए या null तक न पहुँच जाएँ।

हर क़दम आधा पेड़ छाँट देता है — यह O(log n) है... अगर पेड़ संतुलित हो। अगर आप क्रमबद्ध डेटा डालते हैं, तो आपको एक लिंक्ड लिस्ट मिलती है और O(n)। यही वजह है कि संतुलित पेड़ मौजूद हैं।

मुख्य बातें

BST अपरिवर्तनी (invariant)

BST पर हर ऑपरेशन को एक नियम बनाए रखना ही पड़ता है। इसे एक बार बता दीजिए, और हर एल्गोरिथ्म की शुद्धता आप यह जाँचकर सिद्ध कर सकते हैं कि नियम पहले और बाद में टिका रहता है या नहीं:

BST invariant
हर नोड n के लिए: n.left के उपवृक्ष की हर key n.key से सख़्ती से कम है, और n.right के उपवृक्ष की हर key सख़्ती से ज़्यादा।
उपपत्ति — in-order traversal क्रमबद्ध क्रम देता है
पहले left को रिकर्सिव रूप से देखिए, फिर self, फिर right को रिकर्सिव रूप से। left पर रिकर्सिव कॉल वे सारी key लौटाती है जो self.key से कम हैं; right पर कॉल वे लौटाती है जो ज़्यादा हैं। तो जोड़ा हुआ क्रम क्रमबद्ध रहता है।
व्यवहार में "बनाए रखना" का मतलब
हर insert/delete को इस तरह ख़त्म होना चाहिए कि invariant हर जगह अब भी सच हो। Insert आसान है — आप सिर्फ़ किसी पत्ती पर जोड़ते हैं, इसलिए नियम पहले से ही टिका रहता है। Delete मुश्किल मामला है; नीचे देखिए।

और गहराई में

Deletion — तीनों मामले, क़दम-दर-क़दम

यही वह ऑपरेशन है जिसकी वजह से इंजीनियर AVL या Red-Black पेड़ों की तरफ़ हाथ बढ़ाते हैं। invariant बनाए रखते हुए किसी नोड को हटाने में सावधानी लगती है।

मामला 1 — पत्ती। बस उसे उसके माता-पिता से अलग कर दीजिए। invariant बिना किसी मेहनत के बना रहता है क्योंकि किसी और नोड का इस पर भरोसा नहीं था।

    5                5
   / \              / \
  3   8     →      3
     /
    6           (delete 6 from right of 3)

रुकिए, वह उदाहरण 8 के बाएँ से 6 हटा रहा है — कहने का मतलब है, पत्तियाँ मुफ़्त हैं।

मामला 2 — एक बच्चा। बच्चे को ऊपर हटाए गए नोड की जगह में splice कर दीजिए। हटाए गए नोड का माता-पिता अब बच्चे की ओर इशारा करता है; बच्चे का उपवृक्ष पहले से ही invariant के अनुरूप था, इसलिए नई जगह में भी अनुरूप ही रहता है।

      5                5
     / \              / \
    3   8     →      3   6
        /
       6           (delete 8: it had only a left child, 6)

मामला 3 — दो बच्चे। आप किसी भी एक बच्चे को सीधे ऊपर नहीं ला सकते — दोनों के अपने उपवृक्ष हैं जिन्हें आपको किसी तरह जोड़ना पड़ता। तरकीब: in-order उत्तराधिकारी (successor) ढूँढिए — दाएँ उपवृक्ष की सबसे छोटी key (समतुल्य रूप से, right की सबसे बाईं पत्ती)। उसके मान को हटाए गए नोड में कॉपी कीजिए, फिर उस successor को दाएँ उपवृक्ष से हटाइए (रिकर्सिव कॉल, पर successor के ख़ुद अधिक से अधिक एक ही बच्चा होता है, इसलिए रिकर्शन मामला 1 या 2 पर जाकर थम जाता है)।

      5                6
     / \              / \
    3   8     →      3   8
       / \              / \
      6   9            7   9
       \
        7              (delete 5: successor is 6;
                       copy 6 up, then delete the
                       original 6 — case 2 with right
                       child 7)

successor क्यों, predecessor क्यों नहीं? दोनों चलते हैं — predecessor बाएँ उपवृक्ष की सबसे बड़ी key है। ज़्यादातर इम्प्लीमेंटेशन या तो बारी-बारी इस्तेमाल करते हैं या एक को चुनकर उसी पर टिके रहते हैं। invariant बना रहता है क्योंकि successor बाएँ उपवृक्ष की हर चीज़ से सख़्ती से बड़ा था (इसलिए ऊपर लाने के बाद भी बड़ा ही है) और दाएँ उपवृक्ष की बाक़ी हर चीज़ से सख़्ती से छोटा (इसलिए दायाँ उपवृक्ष अब भी मान्य है)।

संतुलन के बिना यह सब क्यों ढह जाता है

डेमो का break it बटन पहले से क्रमबद्ध मान डालता है। हर नया नोड सबसे दाईं जगह पर जाता है — पेड़ एक लिंक्ड लिस्ट बन जाता है, ऊँचाई चढ़कर n हो जाती है, और खोज बिगड़कर O(n) हो जाती है। यही संतुलित पेड़ों वाले पाठ की प्रेरणा है: वहाँ के एल्गोरिथ्म हर insert और delete के बाद पुनर्संतुलन करते हैं, ताकि इनपुट चाहे किसी भी क्रम में आएँ, ऊँचाई O(log n) बनी रहे।

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

Time Complexity (height h)
Search: O(h)
Insert: O(h)
Delete: O(h)
Min/Max: O(h)
Height bounds
Balanced: h = O(log n)
Unbalanced: h = O(n)

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

fn search(node: Option<&Box<BstNode>>, key: i32)
    -> bool
{
    match node {
        None => false,
        Some(n) => {
            if key < n.data {
                search(n.left.as_ref(), key)
            } else if key > n.data {
                search(n.right.as_ref(), key)
            } else {
                true  // Found!
            }
        }
    }
}

Deletion के मामले

अभ्यास

BST invariant पर बने तीन सवाल:

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