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

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

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

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

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

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

विवरण

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

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

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

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

ट्री को संशोधित करने वाले संचालन को यह सुनिश्चित करना चाहिए कि 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 में रैखिक है, अर्थात्, संतुलन एक अमूर्त अर्थ में ओवरहेड की निरंतर मात्रा लेता है।

जबकि न्यूनतम खोज लागत के साथ एक ट्री को बनाए रखने के लिए सम्मिलित के संचालन में चार प्रकार के दोहरे घुमाव की आवश्यकता होती है, अगर हम केवल लॉगरिदमिक प्रदर्शन की इच्छा रखते हैं, तो LR और RL ही एकमात्र घुमाव हैं। एकल टॉप-डाउन पास में होता है।

संचालन और बल्क ऑपरेशन

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

• जुड़ें: फलन जॉइन दो वज़न-संतुलित ट्रीस 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$ का नोड बनाता है।

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

function split(T, k)
    if (T = nil) return (nil, false, nil)
     (L, (m, c), R) = expose(T)
    if (k = m) return (L, true, R)
     if (k < m)
       (L', b, R') = split(L, k)
        return (L', b, join(R', m, R))
     if (k > m)
        (L', b, R') = split(R, k)
         return (join(L, m, L'), b, R))

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

function union(t1, t2):
    if t1 = nil:
        return t2

if t₂ = nil:

       return t1

t_<, t_> ← split t₂ on t₁.root

    return join(union(left(t1), t<), t1.root, union(right(t1), t>))

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

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

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