वेट बैलेंस्ड ट्री

For other uses, see Optimal binary search tree.

कंप्यूटर विज्ञान में, वजन-संतुलित बाइनरी ट्री (डब्ल्यूबीटी) एक प्रकार के स्व-संतुलित बाइनरी सर्च ट्री हैं जिनका उपयोग सेट (अमूर्त डेटा प्रकार), सहयोगी सरणी (मानचित्र) और अनुक्रमों को लागू करने के लिए किया जा सकता है। इन पेड़ों को 1970 के दशक में नीवरगेल्ट और रींगोल्ड द्वारा बाउंडेड बैलेंस या बीबी [α] पेड़ों के रूप में पेश किया गया था। उनका अधिक प्रचलित नाम डोनाल्ड नुथ के कारण है। एक प्रसिद्ध उदाहरण पाठ कोष की हफ़मैन कोडिंग है।

अन्य स्व-संतुलन पेड़ों की तरह, WBTs अपने नोड्स में संतुलन से संबंधित बहीखाता जानकारी संग्रहीत करते हैं और सम्मिलन या विलोपन संचालन से परेशान होने पर संतुलन को बहाल करने के लिए पेड़ को घुमाते हैं। विशेष रूप से, प्रत्येक नोड नोड पर निहित उपवृक्ष के आकार को संग्रहीत करता है, और बाएँ और दाएँ उपवृक्ष के आकार को एक दूसरे के कुछ कारक के भीतर रखा जाता है। एवीएल पेड़ों (उपपेड़ों की ऊंचाई के बारे में जानकारी का उपयोग करके) और लाल-काले पेड़ों (जो एक काल्पनिक रंग बिट को संग्रहीत करते हैं) में संतुलन जानकारी के विपरीत, डब्ल्यूबीटी में बहीखाता जानकारी अनुप्रयोगों के लिए वास्तव में उपयोगी संपत्ति है: तत्वों की संख्या पेड़ अपनी जड़ के आकार के बराबर है, और आकार की जानकारी बिल्कुल एक आदेश आँकड़ा वृक्ष के संचालन को लागू करने के लिए आवश्यक जानकारी है, अर्थात, प्राप्त करना n'किसी सेट में वां सबसे बड़ा तत्व या क्रमबद्ध क्रम में किसी तत्व के सूचकांक का निर्धारण करना। वज़न-संतुलित पेड़ कार्यात्मक प्रोग्रामिंग समुदाय में लोकप्रिय हैं और एमआईटी योजना, एसएलआईबी और हास्केल (प्रोग्रामिंग भाषा) के कार्यान्वयन में सेट और मानचित्रों को लागू करने के लिए उपयोग किए जाते हैं।

विवरण

भार-संतुलित वृक्ष एक द्विआधारी खोज वृक्ष है जो नोड्स में उपवृक्षों के आकार को संग्रहीत करता है। यानी एक नोड में फ़ील्ड होते हैं

• कुंजी, किसी भी आदेशित प्रकार की
• मान (वैकल्पिक, केवल मैपिंग के लिए)
• बाएँ, दाएँ, पॉइंटर से नोड तक
• आकार, पूर्णांक प्रकार का।

परिभाषा के अनुसार, एक पत्ती का आकार (आमतौर पर a द्वारा दर्शाया जाता है nil सूचक) शून्य है. एक आंतरिक नोड का आकार उसके दो बच्चों के आकार का योग है, प्लस एक: (size[n] = size[n.left] + size[n.right] + 1). आकार के आधार पर, कोई व्यक्ति होने वाले वजन को परिभाषित करता है weight[n] = size[n] + 1.

पेड़ का घूमना.

पेड़ को संशोधित करने वाले संचालन को यह सुनिश्चित करना चाहिए कि प्रत्येक नोड के बाएँ और दाएँ उपवृक्ष का भार कुछ कारक के भीतर रहे α एक दूसरे के, समान AVL ट्री का उपयोग करके#AVL ट्री में उपयोग किया जाने वाला पुनर्संतुलन: रोटेशन और डबल रोटेशन। औपचारिक रूप से, नोड संतुलन को इस प्रकार परिभाषित किया गया है:

एक नोड है α-वजन-संतुलित यदि weight[n.left] ≥ α·weight[n] और weight[n.right] ≥ α·weight[n].

यहाँ, α वजन संतुलित पेड़ों को लागू करते समय निर्धारित किया जाने वाला एक संख्यात्मक पैरामीटर है। के बड़े मूल्य α अधिक संतुलित पेड़ पैदा करते हैं, लेकिन सभी मूल्य नहीं α उपयुक्त हैं; नीवरगेल्ट और रींगोल्ड ने यह साबित किया

$\alpha <1-{\frac {\sqrt {2}}{2}}\approx 0.29289$

संतुलन एल्गोरिदम के काम करने के लिए एक आवश्यक शर्त है। बाद के काम में इसकी निचली सीमा दिखाई दी 2⁄11 के लिए α, हालाँकि यदि एक कस्टम (और अधिक जटिल) पुनर्संतुलन एल्गोरिथ्म का उपयोग किया जाता है तो इसे मनमाने ढंग से छोटा किया जा सकता है।

सही ढंग से संतुलन लागू करने से पेड़ की गारंटी होती है nतत्वों की ऊंचाई होगी

$h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)$

एक क्रम में आवश्यक संतुलन संचालन की संख्या n सम्मिलन और विलोपन रैखिक है n, यानी, एक परिशोधित विश्लेषण अर्थ में संतुलन के लिए ओवरहेड की निरंतर मात्रा लगती है। जबकि न्यूनतम खोज लागत के साथ एक पेड़ को बनाए रखने के लिए सम्मिलित/हटाने के संचालन में चार प्रकार के दोहरे घुमाव (एवीएल पेड़ में एलएल, एलआर, आरएल, आरआर) की आवश्यकता होती है, यदि हम केवल लॉगरिदमिक प्रदर्शन की इच्छा रखते हैं, तो एलआर और आरएल ही एकमात्र घुमाव हैं। एक ही टॉप-डाउन पास में।

संचालन और थोक संचालन सेट करें

वजन-संतुलित पेड़ों पर कई सेट ऑपरेशन परिभाषित किए गए हैं: यूनियन (सेट सिद्धांत), इंटरसेक्शन (सेट सिद्धांत) और सेट अंतर। फिर इन सेट फ़ंक्शंस के आधार पर सम्मिलन या विलोपन पर तेज़ बल्क ऑपरेशन लागू किया जा सकता है। ये सेट ऑपरेशन दो सहायक ऑपरेशन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, वजन-संतुलित पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।

• जुड़ें: फ़ंक्शन जॉइन दो वजन-संतुलित पेड़ों पर है t₁ और t₂ और एक कुंजी k और सभी तत्वों वाला एक पेड़ लौटाएगा t₁, t₂ साथ ही k. उसकी आवश्यकता हैं k सभी कुंजियों से बड़ा होना t₁ और सभी कुंजियों से छोटा t₂. यदि दो पेड़ों का वजन संतुलित है, तो बाएं उपवृक्ष के साथ एक नया नोड बनाएं t₁, जड़ k और दायां उपवृक्ष t₂. लगता है कि t₁ से भारी वजन है t₂ (दूसरा मामला सममित है)। जॉइन की दाहिनी रीढ़ का अनुसरण करता है t₁ एक नोड तक c जिसके साथ संतुलित है t₂. इस बिंदु पर बाएँ बच्चे के साथ एक नया नोड c, जड़ k और सही बच्चा t₂ c को प्रतिस्थापित करने के लिए बनाया गया है। नया नोड भार-संतुलित अपरिवर्तनीय को अमान्य कर सकता है। इसे एक या दो बार घुमाकर ठीक किया जा सकता है $\alpha <1-{\frac {1}{\sqrt {2}}}$
• विभाजन: वजन-संतुलित पेड़ को दो छोटे पेड़ों में विभाजित करने के लिए, जो कुंजी x से छोटे हैं, और जो कुंजी x से बड़े हैं, पहले पेड़ में x डालकर जड़ से एक पथ बनाएं। इस प्रविष्टि के बाद, x से कम के सभी मान पथ के बाईं ओर मिलेंगे, और x से बड़े सभी मान दाईं ओर मिलेंगे। जॉइन लागू करने से, बायीं ओर के सभी उपवृक्षों को नीचे से ऊपर तक मध्यवर्ती नोड्स के रूप में पथ पर कुंजियों का उपयोग करके बाएँ वृक्ष बनाने के लिए नीचे से ऊपर की ओर मर्ज किया जाता है, और दायाँ भाग सममित होता है। कुछ अनुप्रयोगों के लिए, स्प्लिट एक बूलियन मान भी लौटाता है जो दर्शाता है कि पेड़ में x दिखाई देता है या नहीं। स्प्लिट की लागत है $O(\log n)$, पेड़ की ऊंचाई का क्रम. इस एल्गोरिदम का वास्तव में वजन-संतुलित पेड़ के किसी विशेष गुण से कोई लेना-देना नहीं है, और इस प्रकार यह एवीएल पेड़ जैसी अन्य संतुलन योजनाओं के लिए सामान्य है।

जॉइन एल्गोरिदम इस प्रकार है:

फ़ंक्शन JoinRightWB(TL, के, टीR)
    (एल, के', सी) = एक्सपोज़(टीL)
    यदि शेष(|टीL|, |टीR|) वापसी नोड(टीL, के, टीR)
    अन्य
        टी' = जॉइनराइटडब्ल्यूबी(सी, के, टीR)
        (एल', के', आर') = एक्सपोज़(टी')
        यदि (शेष राशि(|एल|,|टी'|)) वापसी नोड(एल, के', टी')
        अन्यथा यदि (शेष(|l|,|l'|) और शेष(|l|+|l'|,|r'|))
             वापसी रोटेटलेफ्ट(नोड(एल, के', टी'))
        अन्यथा रोटेटलेफ्ट लौटाएं(नोड(एल, के', रोटेटराइट(टी'))
फ़ंक्शन JoinLeftWB(TL, के, टीR)
    /* JoinRightWB के लिए सममित */
फ़ंक्शन जॉइन (टीL, के, टीR)
    अगर (भारी(टीL, टीR)) रिटर्न जॉइनराइटडब्ल्यूबी(टीL, के, टीR)
    अगर (भारी(टीR, टीL)) रिटर्न जॉइनलेफ्टडब्ल्यूबी(टीL, के, टीR)
    नोड(टीL, के, टीR)

यहाँ संतुलन$(x,y)$ मतलब दो वजन $x$ और $y$ संतुलित हैं. एक्सपोज़(v)=(l, k, r) का अर्थ है एक ट्री नोड निकालना $v$का बायां बच्चा $l$, नोड की कुंजी $k$ और सही बच्चा $r$. नोड (एल, के, आर) का अर्थ है बाएं बच्चे का नोड बनाना $l$, चाबी $k$ और सही बच्चा $r$.

विभाजन एल्गोरिथ्म इस प्रकार है:

फ़ंक्शन स्प्लिट (टी, के)
    यदि (T = शून्य) वापसी (शून्य, गलत, शून्य)
    (एल, (एम, सी), आर) = एक्सपोज़ (टी)
    यदि (k = m) वापसी (L, सत्य, R)
    यदि (k <m)
       (एल', बी, आर') = विभाजित(एल, के)
       वापसी (एल', बी, जुड़ें (आर', एम, आर))
    यदि (k > m)
       (एल', बी, आर') = विभाजित(आर, के)
       वापसी (जुड़ें (एल, एम, एल'), बी, आर))

दो भार-संतुलित पेड़ों का मिलन t₁ और t₂ सेट का प्रतिनिधित्व करना A और B, एक वजन-संतुलित पेड़ है t जो प्रतिनिधित्व करता है A ∪ B. निम्नलिखित पुनरावर्ती फ़ंक्शन इस संघ की गणना करता है:

फ़ंक्शन यूनियन(t1, टी2):
    यदि टी1 = शून्य:
        वापसी टी2

यदि टी₂ = शून्य:

        वापसी टी1

टी_<, टी_> ← विभाजित टी₂ टी पर₁।जड़

    रिटर्न जॉइन(यूनियन(बाएं(टी)1), टी<), टी1.रूट, यूनियन(दाएं(t1), टी>))

यहां, स्प्लिट को दो पेड़ों को वापस करने के लिए माना जाता है: एक कुंजी को अपनी इनपुट कुंजी से कम रखता है, एक बड़ी कुंजी को रखता है। (एल्गोरिदम लगातार डेटा संरचना है | गैर-विनाशकारी, लेकिन एक इन-प्लेस विनाशकारी संस्करण भी मौजूद है।)

प्रतिच्छेदन या अंतर के लिए एल्गोरिथ्म समान है, लेकिन इसके लिए Join2 हेल्पर रूटीन की आवश्यकता होती है जो कि Join के समान है लेकिन मध्य कुंजी के बिना। संघ, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, वजन-संतुलित पेड़ में या तो एक कुंजी या एकाधिक कुंजी डाली जा सकती है या हटाई जा सकती है। चूंकि स्प्लिट और यूनियन जॉइन को कॉल करते हैं लेकिन वजन-संतुलित पेड़ों के संतुलन मानदंडों से सीधे निपटते नहीं हैं, ऐसे कार्यान्वयन को आमतौर पर जॉइन-आधारित ट्री एल्गोरिदम | जॉइन-आधारित एल्गोरिदम कहा जाता है।

मिलन, प्रतिच्छेद और भेद प्रत्येक की जटिलता है $O\left(m\log \left({n \over m}+1\right)\right)$ आकार के दो वजन-संतुलित पेड़ों के लिए $m$ और $n(\geq m)$. तुलनाओं की संख्या की दृष्टि से यह जटिलता इष्टतम है। अधिक महत्वपूर्ण बात यह है कि चूंकि संघ, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल एक-दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर एल्गोरिदम के विश्लेषण के साथ समानांतर प्रोग्रामिंग निष्पादित की जा सकती है। $O(\log m\log n)$.कब $m=1$यदि बड़े पेड़ की जड़ का उपयोग छोटे पेड़ को विभाजित करने के लिए किया जाता है, तो जॉइन-आधारित कार्यान्वयन में एकल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल निर्देशित अचक्रीय ग्राफ (डीएजी) होता है।