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

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)$, ट्री की ऊंचाई का क्रम. इस एल्गोरिदम का वास्तव में वजन-संतुलित ट्री के किसी विशेष गुण से संबंधित नहीं है, और इस प्रकार यह AVL ट्री जैसी अन्य संतुलन योजनाओं के लिए सामान्य है।

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

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) होता है।