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

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 दिखाई देता है या नहीं। स्प्लिट की लागत है $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)$ का अर्थ है 2 वेट $x$ और $y$ संतुलित हैं. एक्सपोज़(v)=(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>))

यहां, स्प्लिट को दो ट्रीस को वापस करने के लिए माना जाता है: एक की को अपनी इनपुट की से कम रखता है, एक बड़ी की को रखता है।

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

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