वृक्ष, द्विआधारी खोज वृक्ष, ढेर व ग्राफ निरूपण

इस अध्याय में लगभग सब कुछ गणना है, और सर्वप्रथम तय करने योग्य बात ऊँचाई की परिपाटी है, क्योंकि उसके बिना प्रश्न अनुत्तरणीय है और अधिकांश स्रोत उसे बताते नहीं। यह अध्याय ऊँचाई कोरों में गिनता है, अतः एकल शीर्ष की ऊँचाई 0 है और ऊँचाई h के द्विआधारी वृक्ष में अधिकतम 2h+1 − 1 शीर्ष व न्यूनतम h + 1 होते हैं। यदि किसी प्रश्न की संख्याएँ एक की चूक दें, तो देखें कि वह शीर्ष गिन रहा है या नहीं। वह तय होने पर तीन गणना-परिणाम अधिकांश अंक उठाते हैं। किसी भी द्विआधारी वृक्ष में पत्तियों की संख्या दो संतान वाले शीर्षों की संख्या से एक अधिक होती है — n₀ = n₂ + 1 — आकृति चाहे कोई हो, जो बहुत से प्रश्नों को एक घटाव बना देता है। n भिन्न कुंजियों पर भिन्न द्विआधारी खोज वृक्षों की संख्या n-वीं कैटलन संख्या है: तीन कुंजियों हेतु 5, चार हेतु 14, पाँच हेतु 42, और वह आकृतियाँ भी गिनती है, क्योंकि BST की आकृति उसकी कुंजी-स्थापना पूर्णतः तय कर देती है। तथा n अवयवों के सरणी-आधारित ढेर में पत्तियाँ अंतिम ⌈n/2⌉ स्थान हैं और आंतरिक शीर्ष प्रथम ⌊n/2⌋, अतः 100-अवयवी ढेर में ठीक 50-50 और ऊँचाई ⌊log₂100⌋ = 6 होती है। मोटे तौर पर के बजाय यथार्थ रूप से जानने योग्य एक अनंतस्पर्शी परिणाम यह है कि अवर्गीकृत सरणी से ढेर बनाना O(n) है, O(n log n) नहीं — परिबंध शिथिल है क्योंकि अधिकांश शीर्ष तल के निकट हैं और केवल एक-दो कदम नीचे छनते हैं। तत्पश्चात् ग्राफ निरूपण अध्याय समाप्त करते हैं, और धारण करने योग्य एकमात्र बात सौदा है: सन्निकटता आव्यूह “कोर है क्या?” का उत्तर O(1) में देता है और कोर कितने ही कम हों O(V²) स्थान लेता है, जबकि सन्निकटता सूची O(V + E) लेती है और वही प्रश्न O(कोटि) में उत्तरित करती है।

शीर्ष, पत्तियाँ व आकृतियाँ गिनना

द्विआधारी वृक्ष, ऊँचाई कोरों में गिनी गई
राशिसूत्रउदाहरण
ऊँचाई h पर अधिकतम शीर्ष2h+1 − 1h = 3 → 15
ऊँचाई h पर न्यूनतम शीर्षh + 1h = 3 → 4 (एक पथ)
n शीर्षों के पूर्ण वृक्ष की ऊँचाई⌊log₂n⌋n = 100 → 6
पत्तियाँ बनाम दो-संतान शीर्षn₀ = n₂ + 1प्रत्येक आकृति पर लागू
n भिन्न कुंजियों पर भिन्न BSTकैटलन Cₙn = 5 → 42
🎯 n₀ = n₂ + 1 क्यों, और वह आकृति पर निर्भर क्यों नहीं
कोर दो प्रकार से गिनें। n शीर्षों के वृक्ष में n − 1 कोर होते हैं। प्रत्येक शीर्ष अपनी संतानों की संख्या के बराबर कोर देता है, अतः कुल 0·n₀ + 1·n₁ + 2·n₂ है। उन्हें बराबर रखकर तथा n = n₀ + n₁ + n₂ रखने पर तुरंत n₀ = n₂ + 1 मिलता है, n₁ के कट जाने सहित — और ठीक इसीलिए आकृति अप्रासंगिक है तथा एक-संतान शीर्ष उस संबंध में कभी नहीं आते। व्यावहारिक उपयोग यह है कि तीनों गणनाओं में कोई दो देता प्रश्न आपको तीसरी निःशुल्क दे देता है: 20 पत्तियों वाले वृक्ष में दो संतान वाले 19 शीर्ष हैं, वह दिखे कैसा भी। यहाँ इसकी जाँच केवल व्युत्पत्ति से नहीं, सभी 42 पाँच-शीर्षी आकृतियों पर पूर्ण-गणना से की गई।
⚠️ पूर्वक्रम व मध्यक्रम वृक्ष तय करते हैं; पूर्वक्रम व पश्चक्रम नहीं
मध्यक्रम वही भ्रमण है जो बताता है कि विभाजन कहाँ है: मूल पूर्वक्रम में स्थित होता है, और मध्यक्रम में उसका स्थान बाएँ उपवृक्ष को दाएँ से पृथक् करता है। उसे हटा दें और सूचना चली जाती है — पूर्वक्रम व पश्चक्रम मिलकर केवल बाईं संतान वाले शीर्ष को उसी शीर्ष से केवल दाईं संतान सहित पृथक् नहीं कर सकते, अतः दो भिन्न वृक्ष दोनों भ्रमण साझा करते हैं। याद रखने योग्य अपवाद यह है कि पूर्ण द्विआधारी वृक्ष हेतु, जहाँ प्रत्येक शीर्ष की शून्य या दो संतानें हों, पूर्वक्रम व पश्चक्रम पर्याप्त हैं, क्योंकि अस्पष्ट एक-संतान स्थिति उत्पन्न ही नहीं हो सकती। दो भ्रमण देता प्रश्न प्रायः ठीक यही जाँच रहा है, और उत्तर इस पर घूमता है कि मध्यक्रम उनमें है या नहीं।

सरणी में ढेर, तथा उसे बनाना रैखिक क्यों है

सरणी में n अवयवों का द्विआधारी ढेर
राशिमानn = 100 हेतु
पत्तियाँ⌈n/2⌉ — अंतिम आधा50
आंतरिक शीर्ष⌊n/2⌋ — प्रथम आधा50
ऊँचाई⌊log₂n⌋6
अवर्गीकृत सरणी से निर्माणO(n)O(n log n) नहीं
n क्रमागत सम्मिलनO(n log n)भिन्न संक्रिया
🎯 प्रत्येक छनन O(log n) होते हुए भी heapify, O(n) क्यों
शिथिल परिबंध n शीर्षों को प्रत्येक के log n काम से गुणा कर O(n log n) पाता है। तंग परिबंध यह देखता है कि अधिकांश शीर्ष तल के निकट हैं और उनके पास छानने योग्य लगभग कुछ नहीं: आधे शीर्ष पत्तियाँ हैं और लागत 0, चौथाई एक स्तर ऊपर और लागत अधिकतम 1, आठवाँ भाग अधिकतम 2। सभी स्तरों पर n/2k+1 शीर्षों का प्रत्येक k काम जोड़ने पर वह श्रेणी मिलती है जो लगभग 2n पर अभिसरित होती है, अतः O(n)। n अवयव एक-एक सम्मिलित करके ढेर बनाना वस्तुतः O(n log n) है, क्योंकि प्रत्येक सम्मिलन पत्ती से ऊपर छनता है और गहरे स्थान ही सामान्य हैं — उसी तर्क का दर्पण-प्रतिबिंब। दो संक्रियाएँ जो समान लगती हैं और log गुणक से भिन्न हैं, और प्रश्न पूछते हैं कि कौन-सी की जा रही है।

एक और ढेर-तथ्य पर्याप्त बार पूछा जाता है कि कहने योग्य है: अधिकतम-ढेर का न्यूनतम पत्ती ही होगा, क्योंकि कोई भी आंतरिक शीर्ष अपनी संतानों से बड़ा है। अतः उसे ढूँढ़ने हेतु सभी ⌈n/2⌉ पत्तियाँ देखनी पड़ती हैं — 100-अवयवी ढेर हेतु 50 तुलनाएँ — और कोई लघु-मार्ग नहीं, और यही कीमत ढेर पूर्ण क्रम के बजाय आंशिक क्रम होने की चुकाता है।

ग्राफ संचित करने के दो तरीके

सन्निकटता आव्यूह बनाम सन्निकटता सूची
संक्रियाआव्यूहसूची
स्थानसदा O(V²)O(V + E)
कोर (u, v) है क्या?O(1)O(u की कोटि)
u के सभी पड़ोसी सूचीबद्ध करनाO(V)O(u की कोटि)
कोर जोड़नाO(1)शीर्ष पर O(1)
उपयुक्तघने ग्राफ, E ≈ V²विरल ग्राफ, E ≪ V²

चुनाव घनत्व से तय होता है, और संक्रमण-बिंदु सूक्ष्म नहीं है: दस लाख शीर्षों व बीस लाख कोरों वाले ग्राफ को लगभग तीस लाख सूची-प्रविष्टियाँ चाहिए और दस खरब आव्यूह-कोष्ठ चाहिए होते। इसीलिए प्रत्येक व्यावहारिक ग्राफ कलनविधि सन्निकटता सूचियों के विरुद्ध लिखी जाती है, और इसीलिए भ्रमण को O(V²) के बजाय O(V + E) कहा जाता है — परिबंध कलनविधि के विषय में जितना है उतना ही निरूपण के विषय में कथन है।

मुख्य बिंदु

  • ऊँचाई की परिपाटी पहले तय करें: कोरों में गिनने पर एकल शीर्ष की ऊँचाई 0 है।
  • ऊँचाई h के द्विआधारी वृक्ष में अधिकतम 2h+1 − 1 शीर्ष व न्यूनतम h + 1 होते हैं।
  • प्रत्येक द्विआधारी वृक्ष में n₀ = n₂ + 1 — पत्तियाँ दो-संतान शीर्षों से एक अधिक, आकृति चाहे कोई।
  • n भिन्न कुंजियों पर भिन्न BST n-वीं कैटलन संख्या है: n = 3, 4, 5 हेतु 5, 14, 42।
  • पूर्वक्रम व मध्यक्रम वृक्ष तय करते हैं; पूर्वक्रम व पश्चक्रम नहीं, सिवाय पूर्ण द्विआधारी वृक्ष के।
  • n के सरणी-ढेर में पत्तियाँ अंतिम ⌈n/2⌉ हैं और आंतरिक शीर्ष प्रथम ⌊n/2⌋।
  • Heapify, O(n) है; n अवयव एक-एक सम्मिलित करना O(n log n) — दो भिन्न संक्रियाएँ।
  • अधिकतम-ढेर का न्यूनतम पत्ती है, अतः उसे ढूँढ़ने की लागत ⌈n/2⌉ तुलनाएँ हैं।
  • आव्यूह: O(V²) स्थान, O(1) कोर-परीक्षण। सूची: O(V + E) स्थान, O(कोटि) कोर-परीक्षण।

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

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

  1. 5 भिन्न कुंजियों से कितने भिन्न द्विआधारी खोज वृक्ष बनाए जा सकते हैं?

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

    उत्तर देखें

    उत्तर: 42

    गणना पाँचवीं कैटलन संख्या है, 42। पुनरावृत्ति कारण है: किसी भी कुंजी को मूल चुनें, और यदि i कुंजियाँ उसके बाएँ पड़ें तो Cᵢ × C₄₋ᵢ वृक्ष निकलते हैं, मूल के सभी पाँच चुनावों पर योग। अनुक्रम 1, 2, 5, 14, 42, 132 चलता है। ध्यान दें कि यह 5-शीर्षी द्विआधारी वृक्ष की भिन्न आकृतियाँ भी गिनता है — वही 42 — क्योंकि आकृति तय होने पर BST गुण तय कर देता है कि कौन-सी कुंजी कहाँ जाएगी, कोई स्वतंत्रता शेष नहीं। अंकित द्विआधारी वृक्षों की गणना भिन्न प्रश्न है: 42 × 5! = 5040, और "अंकित" कहता प्रश्न उसे ही पूछ रहा है।

  2. किसी द्विआधारी वृक्ष में 20 पत्तियाँ हैं। उसके कितने शीर्षों की ठीक दो संतानें हैं?

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

    उत्तर देखें

    उत्तर: 19

    प्रत्येक द्विआधारी वृक्ष में n₀ = n₂ + 1, अतः n₂ = 20 − 1 = 19। संबंध कोरों को दो बार गिनने से आता है: n शीर्षों के वृक्ष में n − 1 कोर होते हैं, और कोरों का योग n₁ + 2n₂ भी है, तथा n हटाने पर n₁ के लुप्त होने सहित परिणाम मिलता है। वही लोप कारण है कि उत्तर को आकृति या एक-संतान शीर्षों की संख्या की कोई सूचना नहीं चाहिए — विश्वास योग्य तथ्य, क्योंकि प्रश्न जान-बूझकर दोनों रोक लेता है। कुल शीर्ष-संख्या तय नहीं होती: कोई भी n₁ ≥ 0, 20 पत्तियों के अनुरूप है।

  3. मानक नीचे-से-ऊपर heapify से n अवयवों की अवर्गीकृत सरणी से द्विआधारी ढेर बनाने में लगता है:

    1. O(n log n)
    2. O(n)
    3. O(log n)
    4. O(n²)
    उत्तर देखें

    उत्तर: B — O(n)

    O(n)। शिथिल विश्लेषण n शीर्षों को प्रति छनन O(log n) से गुणा कर O(n log n) तक पहुँचता है, पर वह बहुत अधिक गिनता है: आधे शीर्ष पत्तियाँ हैं और कुछ नहीं छनते, चौथाई अधिकतम एक स्तर, आठवाँ भाग अधिकतम दो। स्तरों पर (n/2k+1) × k जोड़ने पर वह लगभग 2n पर अभिसरित होता है। विकल्प A भिन्न संक्रिया का सही उत्तर है — n अवयवों को एक-एक सम्मिलित करना, जहाँ प्रत्येक नया अवयव पत्ती से ऊपर छनता है और गहरे स्थान सामान्य स्थिति हैं, जो वास्तविक O(n log n) देता है। दोनों ढेर बनाते हैं और log गुणक से भिन्न हैं, अतः प्रश्न के शब्द उत्तर तय करते हैं।

  4. एक अधिकतम-ढेर सरणी में 100 अवयव रखता है। निकृष्टतम स्थिति में न्यूनतम ढूँढ़ने हेतु कितने अवयव देखने पड़ेंगे?

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

    उत्तर देखें

    उत्तर: 50

    अधिकतम-ढेर का न्यूनतम पत्ती ही होगा, क्योंकि प्रत्येक आंतरिक शीर्ष अपनी संतानों से बड़ा है। n के सरणी-ढेर में पत्तियाँ अंतिम ⌈n/2⌉ स्थान हैं, अतः n = 100 हेतु उनमें 50 हैं और सभी की तुलना करनी होगी — पत्तियों के बीच दोहन योग्य कोई क्रम नहीं। यह ढेर के आंशिक क्रम होने की लागत है: वह अधिकतम तक O(1) पहुँच देता है और दूसरे सिरे पर कुछ नहीं, इसीलिए दोनों सिरे चाहती संरचना दो ढेर या पूर्णतः भिन्न अभिकल्प प्रयोग करती है। 1 या log n उत्तर देना ढेर को वर्गीकृत मानता है, जो वह नहीं है।

  5. भ्रमणों का कौन-सा युग्म द्विआधारी वृक्ष को सदा अद्वितीय रूप से तय करता है?

    1. पूर्वक्रम व पश्चक्रम
    2. पूर्वक्रम व मध्यक्रम
    3. केवल स्तर-क्रम
    4. केवल पश्चक्रम
    उत्तर देखें

    उत्तर: B — पूर्वक्रम व मध्यक्रम

    पूर्वक्रम व मध्यक्रम। पूर्वक्रम मूल बताता है; मध्यक्रम बताता है कि उसके बाएँ कितनी कुंजियाँ हैं, जो शेष अनुक्रम को दो उपवृक्षों में बाँटता है, और तर्क पुनरावर्ती होता है। मध्यक्रम ही वह एकमात्र भ्रमण है जो वह विभाजन-सूचना वहन करता है, इसीलिए प्रत्येक कार्यशील युग्म में वह सम्मिलित है — पश्चक्रम व मध्यक्रम भी काम करते हैं। पूर्वक्रम व पश्चक्रम नहीं करते: केवल बाईं संतान वाला मूल तथा वही मूल केवल दाईं संतान सहित दोनों में समान अनुक्रम देते हैं, अतः दो भिन्न वृक्ष उन्हें साझा करते हैं। अपवाद पूर्ण द्विआधारी वृक्ष है, जहाँ किसी शीर्ष की ठीक एक संतान नहीं होती और अस्पष्टता उत्पन्न ही नहीं हो सकती — "पूर्ण" शब्द जोड़ता प्रश्न उत्तर को A कर देता है।

  6. सन्निकटता आव्यूह की तुलना में सन्निकटता सूची के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक सही हो सकते हैं।)

    1. वह O(V²) के बजाय O(V + E) स्थान प्रयोग करती है
    2. कोई विशिष्ट कोर विद्यमान है या नहीं यह जाँचना धीमा है
    3. विरल ग्राफ हेतु किसी शीर्ष के पड़ोसी सूचीबद्ध करना तेज़ है
    4. वह दिष्ट ग्राफ निरूपित नहीं कर सकती
    उत्तर देखें

    उत्तर: A — वह O(V²) के बजाय O(V + E) स्थान प्रयोग करती है; B — कोई विशिष्ट कोर विद्यमान है या नहीं यह जाँचना धीमा है; C — विरल ग्राफ हेतु किसी शीर्ष के पड़ोसी सूचीबद्ध करना तेज़ है

    A, B व C, जो मिलकर सम्पूर्ण सौदा हैं। सूची केवल विद्यमान कोर संचित करती है, अतः स्थान O(V + E) है (A) और एक शीर्ष के पड़ोसियों पर चलने की लागत V कोष्ठों की पूरी पंक्ति देखने के बजाय O(कोटि) है (C)। कीमत यह है कि "(u, v) कोर है क्या?" का उत्तर देने का अर्थ u की सूची खोजना है, O(कोटि), जहाँ आव्यूह O(1) में उत्तर देता है (B)। D असत्य है — दिष्ट ग्राफ सूची में यदि कुछ हो तो अधिक स्वाभाविक है, क्योंकि कोर केवल एक बार, केवल u की सूची में संचित होता है। उनमें चुनाव घनत्व है: दस लाख शीर्षों व बीस लाख कोरों वाला ग्राफ आव्यूह के रूप में अनिरूपणीय और सूची के रूप में साधारण है।

  7. ऊँचाई कोरों में गिनने पर, ऊँचाई 4 के द्विआधारी वृक्ष में शीर्षों की अधिकतम संख्या है:

    1. 15
    2. 31
    3. 16
    4. 32
    उत्तर देखें

    उत्तर: B — 31

    स्तर 0 से 4 अधिकतम 1, 2, 4, 8 व 16 शीर्ष रखते हैं, कुल 2⁵ − 1 = 31। सूत्र 2h+1 − 1 है, ऊँचाई कोरों में। विकल्प A ऊँचाई 3 का उत्तर है, और वही उसी सूत्र से दूसरी परिपाटी में मिलता है, जहाँ ऊँचाई शीर्ष गिनती है और एकल शीर्ष की ऊँचाई 1 होती है — ठीक इसीलिए प्रश्न का उत्तर देने से पूर्व परिपाटी बतानी पड़ती है। विकल्प D, −1 छोड़ देता है, यह भूलकर कि 16 का पूरा स्तर पहले से विद्यमान 15 के ऊपर बैठता है।

  8. निकृष्टतम स्थिति में n शीर्षों के द्विआधारी खोज वृक्ष में खोज लेती है:

    1. सदा O(log n)
    2. O(n), क्योंकि वृक्ष पथ में अपह्रासित हो सकता है
    3. प्रथम खोज के पश्चात् O(1)
    4. O(n log n)
    उत्तर देखें

    उत्तर: B — O(n), क्योंकि वृक्ष पथ में अपह्रासित हो सकता है

    BST खोज की लागत O(h) है, और h, ⌊log₂n⌋ से n − 1 तक कुछ भी हो सकता है: कुंजियाँ वर्गीकृत क्रम में सम्मिलित करने पर वह वृक्ष बनता है जो एक लंबा पथ है, और उसमें खोज संकेतक-पीछा उपरिव्यय सहित रैखिक अवलोकन है। अतः निकृष्टतम स्थिति O(n) है। विकल्प A संतुलित स्थिति है और संरचना प्रायः उसी पर बेची जाती है, इसीलिए भेद महत्व रखता है — और ठीक वही अंतर है जिसे बंद करने हेतु AVL व लाल-काले वृक्ष हैं, प्रत्येक सम्मिलन पर पुनर्संतुलन काम की कीमत पर O(log n) ऊँचाई लागू करके। "संतुलित" या "AVL" कहता प्रश्न O(log n) पूछ रहा है; साधारण BST उसका अधिकारी नहीं।