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

For other uses, see इष्टतम बाइनरी सर्च ट्री.

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

एक प्रसिद्ध उदाहरण एक कॉर्पस की हफ़मैन कोडिंग है।

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

वज़न-संतुलित पेड़ कार्यात्मक प्रोग्रामिंग समुदाय में लोकप्रिय हैं और एमआईटी योजना, एसएलआईबी और हास्केल के कार्यान्वयन में सेट और मानचित्रों को लागू करने के लिए उपयोग किए जाते हैं।

विवरण

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

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

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

बाइनरी ट्री रोटेशन।

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

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

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

function joinRightWB(TL, k, TR)
    (l, k', c) = expose(TL)
    if balance(|TL|, |TR|) return Node(TL, k, TR)
    else
        T' = joinRightWB(c, k, TR)
        (l', k', r') = expose(T')
        if (balance(|l|,|T'|)) return Node(l, k', T')
        else if (balance(|l|,|l'|) and balance(|l|+|l'|,|r'|))
              return rotateLeft(Node(l, k', T'))
        else return rotateLeft(Node(l, k', rotateRight(T'))
function joinLeftWB(TL, k, TR)
     /* symmetric to joinRightWB */
function join(TL, k, TR)
     if (heavy(TL, TR)) return joinRightWB(TL, k, TR)
    if (heavy(TR, TL)) return joinLeftWB(TL, k, TR)
     Node(TL, k, TR)

यहाँ संतुलन$(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$यदि बड़े पेड़ की जड़ का उपयोग छोटे पेड़ को विभाजित करने के लिए किया जाता है, तो जॉइन-आधारित कार्यान्वयन में एकल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल निर्देशित अचक्रीय ग्राफ (डीएजी) होता है।