उन्नत वृक्ष: AVL, B-वृक्ष, B+/B* वृक्ष व थ्रेडेड द्विआधारी वृक्ष

GATE के उधार लिए प्रोग्रामिंग व आँकड़ा संरचना अध्याय द्विआधारी खोज वृक्ष व ढेर को GATE की अपनी गहराई पर ढकते हैं, पर NET की इकाई 7 उस गहराई से आगे कई वृक्ष-संरचनाएँ स्पष्ट रूप से नामित करती है — AVL वृक्ष, B/B+/B* वृक्ष व थ्रेडेड द्विआधारी वृक्ष — जिन्हें GATE CS इस नामित विवरण के स्तर तक नहीं परखता। यह अध्याय इन सभी को ढकता है, साथ ही वन, जो इस इकाई द्वारा नामित वृक्ष-शब्दावली को पूर्ण करते हैं।

AVL वृक्ष: घूर्णनों से स्व-संतुलन

सादे द्विआधारी खोज वृक्ष की ऊँचाई, व अतः उसका खोज/प्रविष्टि/विलोपन समय, निकृष्टतम स्थिति में O(n) है (पहले से क्रमित आँकड़े प्रविष्ट करने से अपकर्षित, सूची-सदृश वृक्ष)। AVL वृक्ष (एडेल्सन-वेल्स्की व लैंडिस) हर नोड का संतुलन-गुणक — ऊँचाई(बायाँ उपवृक्ष) − ऊँचाई(दायाँ उपवृक्ष) — सर्वदा {−1, 0, +1} में बनाए रखता है, जो सिद्ध रूप से वृक्ष की ऊँचाई O(log n) रखता है, निकृष्टतम स्थिति में भी O(log n) खोज/प्रविष्टि/विलोपन की गारंटी देते हुए। प्रविष्टि या विलोपन के बाद घूर्णनों से संतुलन पुनर्स्थापित होता है: एकल घूर्णन (LL या RR स्थिति) एक तरफ़ की असंतुलन ठीक करता है, व द्वि-घूर्णन (LR या RL स्थिति) पहले संतति फिर स्वयं नोड को घुमाकर टेढ़ी-मेढ़ी असंतुलन ठीक करता है।

🧠 स्थिति का नाम इस बात से रखें कि कौन तरफ़ 'भारी' है व नया नोड कहाँ पड़ता है
LL का अर्थ है असंतुलन बाएँ उपवृक्ष के बाएँ उपवृक्ष पर है — असंतुलित नोड पर एकल दायाँ घूर्णन उसे ठीक करता है। RR दर्पण-छवि है, एकल बायाँ घूर्णन से ठीक। LR का अर्थ है असंतुलन बाएँ उपवृक्ष के दाएँ उपवृक्ष पर है (टेढ़ी-मेढ़ी) — पहले बाएँ संतति को बाएँ घुमाएँ, फिर नोड को दाएँ घुमाएँ। RL दर्पण-छवि है। कौन दो दिशाएँ नामित हैं यह पढ़ना सीधे बताता है कि एक या दो घूर्णन चाहिए व किस क्रम में — चार पृथक प्रक्रियाएँ नए सिरे से याद करने की आवश्यकता नहीं।

B-वृक्ष, B+ वृक्ष व B* वृक्ष

B-वृक्ष परिवार, सादे B-वृक्ष से भिन्नता के क्रम में
संरचनामुख्य गुण
कोटि m का B-वृक्षहर नोड (मूल को छोड़कर) के ⌈m/2⌉ से m संतति हैं; सभी पत्तियाँ समान गहराई पर बैठती हैं; कुंजियाँ व आँकड़ा/अभिलेख दोनों आंतरिक नोड व पत्तियों में रह सकते हैं।
B+ वृक्षसभी वास्तविक आँकड़ा/अभिलेख केवल पत्ती-स्तर पर रहते हैं; आंतरिक नोड केवल खोज-मार्गदर्शन हेतु प्रयुक्त कुंजियाँ रखते हैं; पत्तियाँ अतिरिक्त रूप से क्रमिक शृंखला में जुड़ी होती हैं, जो ठीक वही है जो परास-प्रश्न (या पूर्ण क्रमित स्कैन) को बार-बार वृक्ष में ऊपर लौटे बिना तेज़ बनाता है।
B* वृक्षएक कड़ा B-वृक्ष रूपांतर जो विभाजन से पहले नोडों को कम-से-कम 2/3 भरा होने की माँग करता है (B-वृक्ष के आधा भरे के बजाय) — पहले पड़ोसी के साथ कुंजियाँ पुनर्वितरित करने का प्रयास कर व केवल दोनों भरे होने पर विभाजन कर प्राप्त, अधिक जटिल प्रविष्टि-तर्क की कीमत पर सघनतर नोड व छिछले वृक्ष देते हुए।
🎯 डिस्क-समर्थित अनुक्रमणिकाओं हेतु B-वृक्ष (द्विआधारी खोज वृक्ष नहीं) मानक क्यों हैं
डिस्क-पहुँच स्मृति-अंतर्गत तुलना से कई कोटि धीमी है, अतः महत्वपूर्ण मापक तुलनाओं की संख्या नहीं, पढ़े गए डिस्क-खंडों की संख्या है। B-वृक्ष का उच्च शाखन-गुणक (हर नोड कई कुंजियाँ रखता है, एक डिस्क-खंड भरने योग्य आकार का) का अर्थ है कि विशाल संख्या के अभिलेखों तक पहुँचने हेतु भी केवल कुछ स्तर चाहिए — तीन या चार स्तर लाखों अभिलेख अनुक्रमित कर सकते हैं — जबकि द्विआधारी खोज वृक्ष के 2 के शाखन-गुणक को उतने ही अभिलेखों हेतु कहीं अधिक स्तर व अतः कहीं अधिक डिस्क-वाचन चाहिए होंगे। यही ठीक वह कारण है कि उधार लिए GATE आँकड़ाकोश अध्याय की अपनी B+ वृक्ष अनुक्रमण-सामग्री व इस अध्याय की B-वृक्ष/B*-वृक्ष सामग्री उसी परिवार के विषय में दो भिन्न कोणों से बात कर रही हैं: DBMS अध्याय B+ वृक्षों को अनुक्रमण संरचना मानता है, व यह अध्याय पूरे परिवार को अपने आप में एक आँकड़ा संरचना मानता है।

थ्रेडेड द्विआधारी वृक्ष व वन

सामान्य द्विआधारी वृक्ष में, अधिकांश नोडों के बाएँ/दाएँ संकेतक जो अन्यथा NULL होते (पत्तियों के दो होते हैं, व अधिकांश आंतरिक नोडों का कम-से-कम एक) बस व्यर्थ स्थान हैं। थ्रेडेड द्विआधारी वृक्ष इन NULL संकेतकों का पुनः प्रयोग नोड के मध्यक्रम पूर्ववर्ती (अन्यथा-null बाएँ संकेतक हेतु) या परवर्ती (अन्यथा-null दाएँ संकेतक हेतु) की ओर इंगित करती थ्रेड के रूप में करता है — प्रति-पक्ष एक बूलियन ध्वजा अभिलिखित करती है कि वह संकेतक वास्तविक संतति-कड़ी है या थ्रेड, अतः वृक्ष को बिना स्टैक या पुनरावर्तन के मध्यक्रम अनुक्रम में भ्रमित किया जा सकता है, प्रति-नोड लेखा-जोखा की छोटी मात्रा का व्यापार वास्तव में O(1) अतिरिक्त-स्थान भ्रमण से करते हुए।

  • वन असंयुक्त वृक्षों का (सामान्यतः क्रमित) समुच्चय है — कोई एकल मूल उन्हें साथ नहीं बाँधता। किसी भी वन को मानक रूपांतरण ('बायाँ संतति, दायाँ सहोदर') से एकल द्विआधारी वृक्ष में बदला जा सकता है: नोड की पहली संतति उसकी द्विआधारी-वृक्ष बायाँ संतति बन जाती है, व उसका अगला सहोदर उसकी द्विआधारी-वृक्ष दायाँ संतति — यही ठीक वह कारण है कि वन व सामान्य (गैर-द्विआधारी) वृक्ष कलनविधियाँ इतनी प्रायः द्विआधारी-वृक्ष कलनविधियों में न्यून की जाती हैं, पृथक स्थिति के रूप में व्यवहृत होने के बजाय।

आँकड़ा-संरचनाओं के रूप में समुच्चय, व वृक्ष-परिवार में से चुनाव

  • आँकड़ा-संरचना के रूप में समुच्चय सामान्यतः हैश-सारणी (औसत O(1) सदस्यता/प्रविष्टि/विलोपन, कोई क्रम नहीं), AVL या लाल-काला वृक्ष जैसा संतुलित BST (तीनों हेतु O(log n), पर क्रमित क्रम बना रहता है व परास-प्रश्न समर्थित होते हैं), या बिट-सदिश (जब संभावित अवयवों का जगत् छोटा व ज्ञात हो, बहुत निम्न स्थिरांक-गुणक सहित O(1), पर जगत् बड़ा व समुच्चय स्वयं विरल होने पर अपव्ययी) के रूप में कार्यान्वित होता है।
  • वृक्ष-परिवार में से चुनाव व्यापार का प्रश्न है, 'कौन सर्वोत्तम है' का प्रश्न नहीं: AVL वृक्ष स्मृति-अंतर्गत, तुलना-भारी कार्यभार हेतु उपयुक्त हैं जहाँ अद्यतनों की तुलना में खोज बारंबार हो (उनकी कड़ी संतुलन-प्रक्रिया प्रति अद्यतन अधिक लेती है पर गारंटीशुदा O(log n) खोज में चुकती है); B/B+ वृक्ष डिस्क-समर्थित कार्यभार हेतु उपयुक्त हैं जहाँ खंड-वाचन की संख्या न्यूनतम करना प्रमुख हो; थ्रेडेड वृक्ष स्मृति-सीमित परिवेश हेतु उपयुक्त हैं जहाँ पुनरावर्तन/स्टैक-भार के बिना बारंबार मध्यक्रम भ्रमण चाहिए।

मुख्य बिंदु

  • AVL वृक्ष हर नोड का संतुलन-गुणक {−1, 0, +1} में रखता है, निकृष्टतम स्थिति में भी O(log n) ऊँचाई व अतः O(log n) संक्रियाएँ गारंटीशुदा, एकल (LL/RR) या द्वि (LR/RL) घूर्णनों से पुनर्स्थापित।
  • B-वृक्ष सभी पत्तियाँ समान गहराई पर रखता है; B+ वृक्ष सभी अभिलेख पत्ती-स्तर तक धकेलता है, तेज़ परास-स्कैन हेतु जुड़ी पत्तियों सहित; B* वृक्ष विभाजन से पहले नोडों को कम-से-कम 2/3 भरा होने की माँग करता है।
  • B-वृक्ष डिस्क-समर्थित अनुक्रमणिकाओं हेतु मानक हैं क्योंकि उनका उच्च शाखन-गुणक खंड-वाचन न्यूनतम करता है, जो एक बार डिस्क I/O प्रधान हो जाए तो तुलना-गिनती से कहीं अधिक महत्व रखता है।
  • थ्रेडेड द्विआधारी वृक्ष null संकेतकों का पुनः प्रयोग मध्यक्रम पूर्ववर्ती/परवर्ती थ्रेड के रूप में करता है, बिना स्टैक या पुनरावर्तन के O(1)-अतिरिक्त-स्थान भ्रमण सक्षम करते हुए।
  • वन बायाँ-संतति/दायाँ-सहोदर रूपांतरण से एकल द्विआधारी वृक्ष में बदल जाता है, वन-कलनविधियों को द्विआधारी-वृक्ष कलनविधियों में न्यून करते हुए।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. AVL वृक्ष निकृष्टतम स्थिति में भी O(log n) खोज मुख्यतः इसलिए गारंटी देता है:

    1. हर नोड का संतुलन-गुणक {−1, 0, +1} में रखा जाता है, वृक्ष की ऊँचाई O(log n) पर परिबद्ध करते हुए
    2. यह एक से अधिक अवयव कभी संचित नहीं करता
    3. यह रचना से सदा पूर्ण द्विआधारी वृक्ष है
    4. यह बिल्कुल कोई तुलना प्रयोग नहीं करता
    उत्तर देखें

    उत्तर: A — हर नोड का संतुलन-गुणक {−1, 0, +1} में रखा जाता है, वृक्ष की ऊँचाई O(log n) पर परिबद्ध करते हुए

    हर नोड पर संतुलन-गुणक परिबद्ध करना सिद्ध रूप से समग्र ऊँचाई O(log n) पर परिबद्ध करता है, जो सादा (असंतुलित) द्विआधारी खोज वृक्ष गारंटी नहीं दे सकता — उसकी निकृष्टतम स्थिति O(n) में अपकर्षित होती है।

  2. सादे B-वृक्ष की तुलना में, B+ वृक्ष मुख्यतः इस प्रकार भिन्न है:

    1. सभी वास्तविक अभिलेख केवल पत्ती-स्तर पर रहते हैं, व पत्तियाँ तेज़ क्रमिक/परास पहुँच हेतु जुड़ी होती हैं
    2. इसे अनुक्रमण हेतु बिल्कुल प्रयोग नहीं किया जा सकता
    3. इसका कोई आंतरिक नोड नहीं होता
    4. इसकी पत्तियाँ कभी समान गहराई पर नहीं होतीं
    उत्तर देखें

    उत्तर: A — सभी वास्तविक अभिलेख केवल पत्ती-स्तर पर रहते हैं, व पत्तियाँ तेज़ क्रमिक/परास पहुँच हेतु जुड़ी होती हैं

    आँकड़ा केवल पत्तियों पर रखकर व पत्तियों को शृंखलाबद्ध कर, B+ वृक्ष परास-प्रश्न व पूर्ण क्रमित स्कैन को बार-बार वृक्ष में ऊपर चढ़े बिना तेज़ बनाता है, यही ठीक वह कारण है कि सादे B-वृक्ष के बजाय यही मानक DBMS अनुक्रमण संरचना है।

  3. सादे B-वृक्ष की तुलना में, B* वृक्ष नोडों को कम-से-कम इतना भरा होने की माँग करता है:

    1. विभाजन से पहले 2/3 भरा
    2. पूर्णतः रिक्त
    3. ठीक आधा भरा, B-वृक्ष के समान
    4. केवल मूल पर भरा
    उत्तर देखें

    उत्तर: A — विभाजन से पहले 2/3 भरा

    B* वृक्ष पहले पड़ोसी के साथ कुंजियाँ पुनर्वितरित करने का प्रयास करता है व केवल दोनों भरे होने पर विभाजित करता है, सादे B-वृक्ष की ½-भरी न्यूनतम की तुलना में कड़ी 2/3-भरी आवश्यकता व सघनतर, छिछले वृक्ष प्राप्त करते हुए।

  4. डिस्क-समर्थित आँकड़ाकोश अनुक्रमणिकाओं हेतु B-वृक्ष द्विआधारी खोज वृक्षों पर मुख्यतः इसलिए वरीयता पाते हैं:

    1. उनका उच्च शाखन-गुणक आवश्यक डिस्क-खंड वाचनों की संख्या न्यूनतम करता है
    2. वे किसी भी अन्य संरचना से प्रति कुंजी कम स्मृति प्रयोग करते हैं
    3. द्विआधारी खोज वृक्ष 100 से अधिक अवयव संचित नहीं कर सकते
    4. B-वृक्षों को बिल्कुल कोई तुलना नहीं चाहिए
    उत्तर देखें

    उत्तर: A — उनका उच्च शाखन-गुणक आवश्यक डिस्क-खंड वाचनों की संख्या न्यूनतम करता है

    चूँकि डिस्क-पहुँच स्मृति-अंतर्गत तुलना से कहीं धीमी है, महत्वपूर्ण मापक पढ़े गए खंडों की संख्या है, और B-वृक्ष का उच्च शाखन-गुणक (प्रति नोड एक खंड भरने योग्य आकार का) उसी संख्या के अभिलेखों हेतु द्विआधारी वृक्ष के 2 के शाखन-गुणक से कहीं कम स्तर — अतः कहीं कम वाचन — चाहता है।

  5. थ्रेडेड द्विआधारी वृक्ष की थ्रेड मुख्यतः इसके लिए प्रयुक्त होती हैं:

    1. अन्यथा-null संकेतकों का पुनः प्रयोग कर, बिना स्टैक या पुनरावर्तन के मध्यक्रम भ्रमण सक्षम करने हेतु
    2. हर कुंजी की दूसरी प्रति संचित करने हेतु
    3. वृक्ष को कभी खोजे जाने से रोकने हेतु
    4. वृक्ष को जान-बूझकर असंतुलित बनाने हेतु
    उत्तर देखें

    उत्तर: A — अन्यथा-null संकेतकों का पुनः प्रयोग कर, बिना स्टैक या पुनरावर्तन के मध्यक्रम भ्रमण सक्षम करने हेतु

    अन्यथा-null संतति-संकेतकों का पुनः प्रयोग सीधे मध्यक्रम पूर्ववर्ती/परवर्ती की ओर इंगित करने हेतु होता है, जो भ्रमण को बिना स्पष्ट स्टैक या पुनरावर्ती कॉल-स्टैक के वृक्ष से होकर चलने देता है।

  6. वन को एकल द्विआधारी वृक्ष में बदलने हेतु मानक 'बायाँ संतति, दायाँ सहोदर' रूपांतरण के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. नोड की पहली संतति उसकी द्विआधारी-वृक्ष बायाँ संतति बन जाती है
    2. नोड का अगला सहोदर उसकी द्विआधारी-वृक्ष दायाँ संतति बन जाता है
    3. यह केवल तभी काम करता है जब वन में ठीक एक वृक्ष हो
    4. यह सामान्य (गैर-द्विआधारी) वृक्ष कलनविधियों को द्विआधारी-वृक्ष कलनविधियों के रूप में व्यक्त होने देता है
    उत्तर देखें

    उत्तर: A — नोड की पहली संतति उसकी द्विआधारी-वृक्ष बायाँ संतति बन जाती है; B — नोड का अगला सहोदर उसकी द्विआधारी-वृक्ष दायाँ संतति बन जाता है; D — यह सामान्य (गैर-द्विआधारी) वृक्ष कलनविधियों को द्विआधारी-वृक्ष कलनविधियों के रूप में व्यक्त होने देता है

    यह रूपांतरण किसी भी वन हेतु काम करता है, कई पृथक वृक्षों सहित — पहले वृक्ष की मूल द्विआधारी वृक्ष की मूल बनती है, व बाद के वृक्षों की मूलें दायें-सहोदर संकेतकों के अनुदिश शृंखलाबद्ध होती हैं, यही ठीक वह है जो न्यूनन को सामान्य बनाता है।

  7. AVL वृक्ष में, किसी नोड के बाएँ उपवृक्ष के दाएँ उपवृक्ष पर स्थित असंतुलन (टेढ़ी-मेढ़ी असंतुलन) को किस नामित घूर्णन-स्थिति की आवश्यकता है?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: LR

    LR स्थिति पहले बाएँ संतति को बाएँ घुमाकर फिर असंतुलित नोड को दाएँ घुमाकर ठीक होती है — शुद्ध LL या RR स्थितियाँ ठीक करने वाले एकल घूर्णन के विपरीत, एक द्वि-घूर्णन।

  8. किसी तंत्र की अनुक्रमणिका-संरचना हेतु B+ वृक्ष पर AVL वृक्ष चुनना तब सर्वाधिक न्यायोचित है जब:

    1. आँकड़ा व अनुक्रमणिका पूर्णतः स्मृति में रहते हों, अद्यतनों की तुलना में बारंबार खोज सहित
    2. आँकड़ा डिस्क पर रहता हो व खंड-वाचन न्यूनतम करना प्राथमिकता हो
    3. क्रमित/तुलना-आधारित खोज की बिल्कुल कोई आवश्यकता न हो
    4. तंत्र के पास बिल्कुल कोई स्मृति उपलब्ध न हो
    उत्तर देखें

    उत्तर: A — आँकड़ा व अनुक्रमणिका पूर्णतः स्मृति में रहते हों, अद्यतनों की तुलना में बारंबार खोज सहित

    AVL वृक्ष की कड़ी, तुलना-आधारित संतुलन-प्रक्रिया स्मृति-अंतर्गत कार्यभार हेतु सुयोग्य है जहाँ गारंटीशुदा O(log n) खोज महत्व रखे; एक बार आँकड़ा डिस्क पर हो, खंड-वाचन न्यूनतम करना प्रमुख हो जाता है व B/B+ वृक्ष का उच्च शाखन-गुणक बेहतर मेल है।