बीआईटी: एक बाइनरी अनुक्रमित पेड़ का उपयोग करना?

Question

अन्य डेटा संरचनाओं की तुलना में एक बाइनरी अनुक्रमित पेड़ का अध्ययन करने के लिए बहुत कम या अपेक्षाकृत कोई सिद्धांत नहीं है। एकमात्र जगह जहां इसे संक्षेप में is the topcoder tutorial सिखाया जाता है। हालांकि ट्यूटोरियल सभी स्पष्टीकरणों में पूरा हो गया है, मैं समझ नहीं पा रहा हूं कि इस तरह के पेड़ के पीछे अंतर्ज्ञान क्या है? और यह कैसे शुद्धता साबित करने के लिए?

मुझे लगता है कि सबूत समझाने के लिए जटिल है। तो बीआईटी का उपयोग करते समय, आप किस दृष्टिकोण का पालन करते हैं?

Answer 1

मैं बहुत स्पष्ट रूप से @templatetypedef अंतर्ज्ञान और एक द्विआधारी अनुक्रमित पेड़ के सबूत के बारे में समझाने के द्वारा this answer पाया: जवाब ....

Intuitively, आप की एक संकुचित प्रतिनिधित्व के रूप में एक द्विआधारी अनुक्रमित पेड़ के बारे में सोच सकते हैं एक बाइनरी पेड़ जो स्वयं मानक सरणी प्रतिनिधित्व का अनुकूलन है। यह उत्तर एक संभावित व्युत्पन्न में चला जाता है।

मान लें कि, उदाहरण के लिए, आप कुल 7 विभिन्न तत्वों के लिए संचयी आवृत्तियों को संग्रहीत करना चाहते हैं। आप सात बाल्टी जिसमें संख्या वितरित किया जाएगा बाहर लिख कर शुरू कर सकते हैं:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105] 
    1  2  3  4  5  6  7 

सरणी के इस संस्करण का उपयोग करना:

[ ] [ ] [ ] [ ] [ ] [ ] [ ] 
    1  2  3  4  5  6  7 

अब

, चलो कि संचयी आवृत्तियों कुछ इस तरह दिखाई लगता है जाने , आप किसी भी तत्व की संचयी आवृत्ति को उस स्थान पर संग्रहीत संख्या के मूल्य को बढ़ाकर बढ़ा सकते हैं, फिर बाद में आने वाली सभी चीजों की आवृत्तियों को बढ़ा सकते हैं। उदाहरण के लिए, 7 से 3 का संचयी आवृत्ति को बढ़ाने के लिए, हम पर या स्थिति 3 के बाद सरणी में प्रत्येक तत्व के लिए 7 जोड़ सकता है, जैसा कि यहाँ दिखाया:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112] 
    1  2  3  4  5  6  7 

(इस के साथ समस्या यह है कि हे लेता है n) ऐसा करने का समय, जो बहुत बड़ा है अगर एन बड़ा है।

एक तरीका यह है कि हम इस ऑपरेशन में सुधार के बारे में सोच सकते हैं, जो हम बाल्टी में स्टोर करते हैं उसे बदलना होगा। दिए गए बिंदु तक संचयी आवृत्ति को संग्रहीत करने के बजाय, आप केवल उस राशि को संग्रहीत करने के बारे में सोच सकते हैं जो पिछले बाल्टी के सापेक्ष वर्तमान आवृत्ति बढ़ गई है। उदाहरण के लिए, हमारे मामले में, हम ऊपर बाल्टी इस प्रकार पुनर्लेखन होगा:

अब, हम (1) सिर्फ इतना है कि बाल्टी के लिए उचित मात्रा में जोड़कर समय हे में एक बाल्टी के भीतर आवृत्ति बढ़ाने के कर सकते हैं। हालांकि, लुकअप करने की कुल लागत अब ओ (एन) बन जाती है, क्योंकि हमें सभी छोटी बाल्टी में मूल्यों को जोड़कर बाल्टी में कुल को दोबारा बदलना पड़ता है।

पहली प्रमुख अंतर्दृष्टि जिसे हमें यहां से एक बाइनरी अनुक्रमित पेड़ तक पहुंचने की आवश्यकता है, निम्नलिखित है: किसी विशेष तत्व से पहले वाले सरणी तत्वों के योग को लगातार पुनः संयोजित करने के बजाय, यदि हम सभी की कुल राशि का प्रीकंप्यूट करना चाहते हैं, तो क्या होगा अनुक्रम में विशिष्ट बिंदुओं से पहले तत्व? अगर हम ऐसा कर सकते हैं, तो हम इन प्रीकंप्यूटेड रकम के सही संयोजन को संक्षेप में एक बिंदु पर संचयी योग को समझ सकते हैं।

ऐसा करने का एक तरीका नोड्स के बाइनरी पेड़ होने के लिए बाल्टी की सरणी होने से प्रतिनिधित्व को बदलना है। प्रत्येक नोड को उस मान के साथ एनोटेट किया जाएगा जो उस नोड के बाईं ओर सभी नोड्स के संचयी योग का प्रतिनिधित्व करता है।उदाहरण के लिए, हम इन नोड से निम्नलिखित द्विआधारी पेड़ का निर्माण लगता है:

   4 
     / \ 
     2  6 
     /\ /\ 
     1 3 5 7 

अब, हम उस नोड और उसके बाएं सबट्री सहित सभी मूल्यों के संचयी योग भंडारण के द्वारा प्रत्येक नोड बढ़ाने कर सकते हैं। उदाहरण के लिए, हमारे मूल्यों को देखते हुए, हम संग्रहीत करेंगे निम्नलिखित:

Before: 
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0] 
    1  2  3  4  5  6  7 

After: 
       4 
       [+32] 
      / \ 
      2   6 
     [ +6]  [+80] 
     / \  / \ 
     1  3  5  7 
     [ +5] [+15] [+52] [ +0] 

इस वृक्ष संरचना को देखते हुए यह एक बिंदु के लिए संचयी योग को ऊपर निर्धारित करने के लिए आसान है। विचार निम्न है: हम काउंटर को बनाए रखते हैं, शुरुआत में 0, फिर सामान्य बाइनरी खोज तब तक करें जब तक हम नोड को प्रश्न में न पाएं। जैसा कि हम करते हैं, हम भी निम्नलिखित हैं: जब भी हम सही स्थानांतरित करते हैं, हम काउंटर पर वर्तमान मूल्य में भी जोड़ते हैं।

उदाहरण के लिए, हम 3 के लिए योग को देखने के लिए ऐसा करने के लिए चाहते हैं, हम निम्न करें:

• प्रारंभ जड़ (4) में। काउंटर 0.
• नोड (2) पर जाएं। काउंटर 0.
• नोड (3) पर जाएं। काउंटर 0 + 6 = 6.
• नोड (3) खोजें। काउंटर 6 + 15 = 21.

आप कल्पना कर सकते हैं कि इस प्रक्रिया को रिवर्स में भी चलाना: किसी दिए गए नोड से शुरू करना, काउंटर को उस नोड के मान में प्रारंभ करना, फिर पेड़ को रूट पर ले जाना। जब भी आप सही बच्चे को ऊपर की ओर लिंक करते हैं, तो उस नोड पर मूल्य जोड़ें जो आप पहुंचते हैं। उदाहरण के लिए, 3 के लिए आवृत्ति को खोजने के लिए, हम निम्नलिखित कर सकते हैं:

• नोड (3) पर प्रारंभ करें। काउंटर 15.
• ऊपर नोड (2) तक जाएं। काउंटर 15 + 6 = 21.
• ऊपर नोड (1) तक जाएं। काउंटर, हम पेड़ में नोड्स के सेट है कि में उस नोड में शामिल हैं अद्यतन करने की आवश्यकता 21.

एक नोड की आवृत्ति को बढ़ाने के लिए है (परोक्ष सभी नोड्स है कि यह बाद आने की आवृत्तियों और,) ने अपने बाएं subtree। ऐसा करने के लिए, हम निम्न कार्य करते हैं: उस नोड के लिए आवृत्ति को बढ़ाएं, फिर पेड़ की जड़ तक चलना शुरू करें। जब भी आप एक लिंक का पालन करते हैं जो आपको बाएं बच्चे के रूप में ले जाता है, तो वर्तमान मूल्य में जोड़कर आपको नोड की आवृत्ति में वृद्धि होती है।

उदाहरण के लिए, पाँच से नोड 1 की आवृत्ति को बढ़ाने के लिए, हम निम्नलिखित करना होगा: नोड 1 में शुरू

    4 
       [+32] 
      / \ 
      2   6 
     [ +6]  [+80] 
     / \  / \ 
     > 1  3  5  7 
     [ +5] [+15] [+52] [ +0] 

, अब

    4 
       [+32] 
      / \ 
      2   6 
     [ +6]  [+80] 
     / \  / \ 
     > 1  3  5  7 
     [+10] [+15] [+52] [ +0] 

प्राप्त करने के लिए 5 से इसकी आवृत्ति बढ़ाने के , अपने माता-पिता के पास जाएं:

    4 
       [+32] 
      / \ 
     > 2   6 
     [ +6]  [+80] 
     / \  / \ 
     1  3  5  7 
     [+10] [+15] [+52] [ +0] 

हमने ऊपर बाएं बाल लिंक का पालन किया, इसलिए हम इस नोड के fr equency रूप में अच्छी तरह:

    4 
       [+32] 
      / \ 
     > 2   6 
     [+11]  [+80] 
     / \  / \ 
     1  3  5  7 
     [+10] [+15] [+52] [ +0] 

अब हम अपनी मूल पर जाएँ:

   > 4 
       [+32] 
      / \ 
      2   6 
     [+11]  [+80] 
     / \  / \ 
     1  3  5  7 
     [+10] [+15] [+52] [ +0] 

एक छोड़ दिया बच्चे को कड़ी था, इसलिए हम के रूप में अच्छी तरह से इस नोड को बढ़ा:

    4 
       [+37] 
      / \ 
      2   6 
     [+11]  [+80] 
     / \  / \ 
     1  3  5  7 
     [+10] [+15] [+52] [ +0] 

और अब हम हो चुका है!

अंतिम चरण इसे बाइनरी अनुक्रमित पेड़ में परिवर्तित करना है, और यह वह जगह है जहां हम बाइनरी संख्याओं के साथ कुछ मजेदार चीजें करते हैं। के बाइनरी में इस पेड़ में प्रत्येक बकेट इंडेक्स पुनर्लेखन करते हैं:

   100 
       [+37] 
      / \ 
      010   110 
     [+11]  [+80] 
     / \  / \ 
     001 011 101 111 
     [+10] [+15] [+52] [ +0] 

यहाँ, हम एक बहुत, बहुत शांत अवलोकन कर सकते हैं। इन बाइनरी संख्याओं में से कोई भी लें और संख्या में सेट किया गया अंतिम अंतिम 1 ढूंढें, उसके बाद आने वाले सभी बिट्स के साथ उस बिट को छोड़ दें।

   (empty) 
       [+37] 
      / \ 
      0   1 
     [+11]  [+80] 
     / \  / \ 
     00 01  10 11 
     [+10] [+15] [+52] [ +0] 

यहाँ एक सच में, सच शांत अवलोकन है: इसका मतलब यह है कि अगर आप 0 का इलाज "छोड़" और 1 मतलब "ठीक है," प्रत्येक संख्या पर शेष बिट वास्तव में उल्लेख अब आप के साथ निम्नलिखित छोड़ दिया जाता है रूट पर कैसे शुरू करें और फिर उस नंबर पर जाएं। उदाहरण के लिए, नोड 5 में द्विआधारी पैटर्न 101 है। अंतिम 1 अंतिम बिट है, इसलिए हम उसे 10 प्राप्त करने के लिए छोड़ देते हैं। दरअसल, यदि आप रूट पर शुरू करते हैं, तो सही (1) पर जाएं, फिर बाएं (0) पर जाएं, आप अंत करें नोड 5 पर ऊपर!

कारण यह महत्वपूर्ण है कि हमारा लुकअप और अपडेट ऑपरेशन नोड से रूट तक पहुंच पथ पर निर्भर करता है और क्या हम बाएं या दाएं बच्चे के लिंक का पालन कर रहे हैं। उदाहरण के लिए, एक लुकअप के दौरान, हम केवल हमारे द्वारा अनुसरण किए गए बाएं लिंक की परवाह करते हैं। एक अद्यतन के दौरान, हम केवल हमारे द्वारा अनुसरण किए जाने वाले सही लिंक की परवाह करते हैं। यह बाइनरी अनुक्रमित पेड़ इंडेक्स में बिट्स का उपयोग करके इस सुपर को कुशलतापूर्वक करता है।

को देखते हुए नोड एन, पहुँच मार्ग पर अगले नोड वापस जड़ तक जा जिसमें हम सही द्विआधारी लेने के द्वारा दिया जाता है:

कुंजी चाल इस आदर्श द्विआधारी पेड़ के निम्नलिखित गुण है एन का प्रतिनिधित्व और अंतिम 1.

उदाहरण के लिए, नोड 7 के लिए एक्सेस पथ पर एक नज़र डालें, जो 111 है।111

नोड 6:: 110

नोड 4: 100

जड़ है कि हम उस लेने के लिए पहुंच पथ पर नोड्स

• नोड 7 के बाद एक सही सूचक ऊपर की ओर है शामिल ये सभी सही लिंक हैं। हम नोड 3 है, जो 011 है के लिए पहुंच पथ लेते हैं, और नोड्स जहां हम सही जाना को देखें, तो हम पाते हैं
  • नोड 3: 011
  • नोड 2: 010
  • (नोड 4 : 100 है, जो एक बाएं लिंक इस प्रकार है)

  इसका मतलब यह है कि हम बहुत, बहुत कुशलता से संचयी योग को एक नोड के लिए गणना कर सकता है इस प्रकार है:

  • बाइनरी में नोड एन लिखें।
    • नोड n पर मूल्य में जोड़ें:
    • को 0.
    • दोहराएँ का अनुसरण करते हुए n ≠ 0 काउंटर निर्धारित करें।
    • एन से बाएं 1 बिट हटाएं।

  इसी तरह, हम कैसे एक अद्यतन कदम क्या करना होगा के बारे में सोचते हैं। ऐसा करने के लिए, हम रूट पर बैक अप पहुंच पथ का पालन करना चाहते हैं, सभी नोड्स को अपडेट करना जहां हमने ऊपर बाएं लिंक का पालन किया था। हम अनिवार्य रूप से उपर्युक्त एल्गोरिदम कर कर ऐसा कर सकते हैं, लेकिन सभी 1 से 0 और 0 से 1 तक स्विच कर सकते हैं।

  बाइनरी अनुक्रमित पेड़ में अंतिम चरण यह ध्यान रखना है कि इस बिटवाई की चालबाजी के कारण, हमें पेड़ को स्पष्ट रूप से संग्रहीत करने की भी आवश्यकता नहीं है। हम सभी नोड्स को लम्बाई एन की सरणी में स्टोर कर सकते हैं, फिर पेड़ को नेविगेट करने के लिए बिटवाईड ट्विडलिंग तकनीकों का उपयोग करें। असल में, यह वही है जो बिटवाईड इंडेक्टेड पेड़ करता है - यह नोड्स को एक सरणी में संग्रहीत करता है, फिर इन पेड़ में ऊपर चलने के लिए कुशलता से अनुकरण करने के लिए इन बिटटाइम चाल का उपयोग करता है।

  आशा है कि इससे मदद मिलती है!