वेट बैलेंस्ड ट्री: Difference between revisions

Latest revision as of 10:51, 22 August 2023

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

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

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

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

विवरण

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

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

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

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

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

एक नोड

α

-भार-संतुलित है यदि weight[n.left] ≥ α·weight[n] और weight[n.right] ≥ α·weight[n].^[7]

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

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

संतुलन एल्गोरिदम के काम करने के लिए एक आवश्यक शर्त है। बाद के काम में $α$ के लिए 2⁄11 की निचली सीमा दिखाई गई, चूंकि यदि एक कस्टम पुनर्संतुलन एल्गोरिथ्म का उपयोग किया जाता है तो इसे मनमाने ढंग से छोटा किया जा सकता है।^[7]

संतुलन को सही ढंग से लागू करने से यह गारंटी मिलती है कि $n$ तत्वों की ऊंचाई होगी।^[7]

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$ में रैखिक है, अर्थात्, संतुलन एक अमूर्त अर्थ में ओवरहेड की निरंतर मात्रा लेता है।^[8]

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

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

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

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

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

function joinRightWB(T_L, k, T_R)
    (l, k', c) = expose(T_L)
    if balance(|T_L|, |T_R|) return Node(T_L, k, T_R)
    else
        T' = joinRightWB(c, k, T_R)
        (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(T_L, k, T_R)
     /* symmetric to joinRightWB */
function join(T_L, k, T_R)
     if (heavy(T_L, T_R)) return joinRightWB(T_L, k, T_R)
    if (heavy(T_R, T_L)) return joinLeftWB(T_L, k, T_R)
     Node(T_L, k, T_R)

यहाँ संतुलन $(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 1$ और $t 2$ का मिलन, एक वज़न-संतुलित ट्री $t$ है जो $A \cup B$ का प्रतिनिधित्व करता है। निम्नलिखित पुनरावर्ती फंक्शन इस मिलन की गणना करता है:

function union(t₁, t₂):
    if t₁ = nil:
        return t₂

if t₂ = nil:

       return t₁

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

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

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

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

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

संदर्भ

↑ Tsakalidis, A. K. (1984). "सामान्यीकृत लिंक्ड सूची में क्रम बनाए रखना". Acta Informatica. 21: 101–112. doi:10.1007/BF00289142.
↑ Nievergelt, J.; Reingold, E. M. (1973). "बाउंडेड बैलेंस के बाइनरी सर्च ट्री". SIAM Journal on Computing. 2: 33–43. doi:10.1137/0202005.
↑ This article incorporates public domain material from Black, Paul E. "BB(α) tree". Dictionary of Algorithms and Data Structures.
↑ ^4.0 ^4.1 ^4.2 Hirai, Y.; Yamamoto, K. (2011). "वजन-संतुलित पेड़ों को संतुलित करना" (PDF). Journal of Functional Programming. 21 (3): 287. doi:10.1017/S0956796811000104.
↑ Roura, Salvador (2001). बाइनरी सर्च ट्री को संतुलित करने की एक नई विधि. ICALP. Lecture Notes in Computer Science. Vol. 2076. pp. 469–480. doi:10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7.
↑ ^6.0 ^6.1 Adams, Stephen (1993). "Functional Pearls: Efficient sets—a balancing act". Journal of Functional Programming. 3 (4): 553–561. doi:10.1017/S0956796800000885.
↑ ^7.0 ^7.1 ^7.2 Brass, Peter (2008). उन्नत डेटा संरचनाएँ. Cambridge University Press. pp. 61–71.
↑ Blum, Norbert; Mehlhorn, Kurt (1980). "वजन-संतुलित पेड़ों में पुनर्संतुलन कार्यों की औसत संख्या पर" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.
↑ Cho, Seonghun; Sahni, Sartaj (2000). "एक नया वजन संतुलित बाइनरी सर्च ट्री". International Journal of Foundations of Computer Science. 11 (3): 485–513. doi:10.1142/S0129054100000296.
↑ ^10.0 ^10.1 Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0.
↑ Adams, Stephen (1992), Implementing sets efficiently in a functional language, CiteSeerX 10.1.1.501.8427.

[7] This is the definition used by Nievergelt and Reingold. Adams uses the size as the weight directly,^[6] which complicates analysis of his variant and has led to bugs in major implementations.^[4]

[1] Tsakalidis, A. K. (1984). "सामान्यीकृत लिंक्ड सूची में क्रम बनाए रखना". Acta Informatica. 21: 101–112. doi:10.1007/BF00289142.

[2] Nievergelt, J.; Reingold, E. M. (1973). "बाउंडेड बैलेंस के बाइनरी सर्च ट्री". SIAM Journal on Computing. 2: 33–43. doi:10.1137/0202005.

[3] This article incorporates public domain material from Black, Paul E. "BB(α) tree". Dictionary of Algorithms and Data Structures.

[Hirai-4] 4.0 ^4.1 ^4.2 Hirai, Y.; Yamamoto, K. (2011). "वजन-संतुलित पेड़ों को संतुलित करना" (PDF). Journal of Functional Programming. 21 (3): 287. doi:10.1017/S0956796811000104.

[5] Roura, Salvador (2001). बाइनरी सर्च ट्री को संतुलित करने की एक नई विधि. ICALP. Lecture Notes in Computer Science. Vol. 2076. pp. 469–480. doi:10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7.

[Adams-6] 6.0 ^6.1 Adams, Stephen (1993). "Functional Pearls: Efficient sets—a balancing act". Journal of Functional Programming. 3 (4): 553–561. doi:10.1017/S0956796800000885.

[brass-8] 7.0 ^7.1 ^7.2 Brass, Peter (2008). उन्नत डेटा संरचनाएँ. Cambridge University Press. pp. 61–71.

[9] Blum, Norbert; Mehlhorn, Kurt (1980). "वजन-संतुलित पेड़ों में पुनर्संतुलन कार्यों की औसत संख्या पर" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.

[10] Cho, Seonghun; Sahni, Sartaj (2000). "एक नया वजन संतुलित बाइनरी सर्च ट्री". International Journal of Foundations of Computer Science. 11 (3): 485–513. doi:10.1142/S0129054100000296.

[join-based-11] 10.0 ^10.1 Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0.

[adams-12] Adams, Stephen (1992), Implementing sets efficiently in a functional language, CiteSeerX 10.1.1.501.8427.

[1]

[2]

[3]

[4]

[5]

[6]

[lower-alpha 1]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 {{Short description|Self-balancing binary search tree}}
 {{Other uses|इष्टतम बाइनरी सर्च ट्री}}
-[[कंप्यूटर विज्ञान]] में, '''वज़न-संतुलित बाइनरी ट्री''' (डब्ल्यूबीटी) एक प्रकार के स्व-संतुलित बाइनरी सर्च ट्री हैं जिनका उपयोग गतिशील सेट, [[Index.php?title=शब्दकोश|शब्दकोश]] और अनुक्रमों को लागू करने के लिए किया जा सकता है।<ref>{{Cite journal | doi = 10.1007/BF00289142| title = सामान्यीकृत लिंक्ड सूची में क्रम बनाए रखना| journal = Acta Informatica| volume = 21| pages = 101–112| year = 1984| last1 = Tsakalidis | first1 = A. K. }}</ref>  इन पेड़ों को 1970 के दशक में नीवरगेल्ट और रींगोल्ड द्वारा परिबद्ध संतुलन के पेड़, या BB [α] पेड़ों के रूप में पेश किया गया था।<ref>{{Cite journal | doi = 10.1137/0202005| title = बाउंडेड बैलेंस के बाइनरी सर्च ट्री| journal = SIAM Journal on Computing| volume = 2| pages = 33–43| year = 1973| last1 = Nievergelt | first1 = J.| last2 = Reingold | first2 = E. M.}}</ref><ref>{{DADS|BB(α) tree|bbalphatree}}</ref> उनका अधिक प्रचलित नाम [[डोनाल्ड नुथ]] के कारण है।<ref name="Hirai">{{Cite journal |doi=10.1017/S0956796811000104 |title=वजन-संतुलित पेड़ों को संतुलित करना|journal=Journal of Functional Programming |volume=21 |issue=3 |pages=287 |year=2011 |last1=Hirai |first1=Y. |last2=Yamamoto |first2=K. |url=https://yoichihirai.com/bst.pdf}}</ref>
+[[Index.php?title=कंप्यूटर साइंस|कंप्यूटर साइंस]] में, '''वज़न-संतुलित बाइनरी ट्री''' (WBT) एक प्रकार के स्व-संतुलित बाइनरी सर्च ट्री हैं जिनका उपयोग गतिशील सेट, [[Index.php?title=Index.php?title=डिक्शनरी|डिक्शनरी]] और अनुक्रमों को लागू करने के लिए किया जा सकता है।<ref>{{Cite journal | doi = 10.1007/BF00289142| title = सामान्यीकृत लिंक्ड सूची में क्रम बनाए रखना| journal = Acta Informatica| volume = 21| pages = 101–112| year = 1984| last1 = Tsakalidis | first1 = A. K. }}</ref>  इन ट्रीस को 1970 के दशक में नीवरगेल्ट और रींगोल्ड द्वारा परिबद्ध संतुलन के ट्री, या BB [α] ट्रीस के रूप में प्रस्तुत किया गया था।<ref>{{Cite journal | doi = 10.1137/0202005| title = बाउंडेड बैलेंस के बाइनरी सर्च ट्री| journal = SIAM Journal on Computing| volume = 2| pages = 33–43| year = 1973| last1 = Nievergelt | first1 = J.| last2 = Reingold | first2 = E. M.}}</ref><ref>{{DADS|BB(α) tree|bbalphatree}}</ref> उनका अधिक प्रचलित नाम [[डोनाल्ड नुथ]] के कारण है।<ref name="Hirai">{{Cite journal |doi=10.1017/S0956796811000104 |title=वजन-संतुलित पेड़ों को संतुलित करना|journal=Journal of Functional Programming |volume=21 |issue=3 |pages=287 |year=2011 |last1=Hirai |first1=Y. |last2=Yamamoto |first2=K. |url=https://yoichihirai.com/bst.pdf}}</ref>
 एक प्रसिद्ध उदाहरण एक [[Index.php?title=कॉर्पस|कॉर्पस]] की [[हफ़मैन कोडिंग]] है।
-अन्य स्व-संतुलन पेड़ों की तरह, WBTs अपने नोड्स में संतुलन से संबंधित बहीखाता जानकारी संग्रहीत करते हैं और सम्मिलन या विलोपन संचालन से परेशान होने पर संतुलन को बहाल करने के लिए पेड़ को घुमाते हैं। विशेष रूप से, प्रत्येक नोड नोड पर निहित उपवृक्ष के आकार को संग्रहीत करता है, और बाएँ और दाएँ उपवृक्ष के आकार को एक दूसरे के कुछ कारक के भीतर रखा जाता है। [[एवीएल पेड़]]ों (उपपेड़ों की ऊंचाई के बारे में जानकारी का उपयोग करके) और लाल-काले पेड़ों (जो एक काल्पनिक रंग बिट को संग्रहीत करते हैं) में संतुलन जानकारी के विपरीत, डब्ल्यूबीटी में बहीखाता जानकारी अनुप्रयोगों के लिए वास्तव में उपयोगी संपत्ति है: तत्वों की संख्या पेड़ अपनी जड़ के आकार के बराबर है, और आकार की जानकारी बिल्कुल एक [[आदेश आँकड़ा वृक्ष]] के संचालन को लागू करने के लिए आवश्यक जानकारी है, अर्थात, प्राप्त करना {{mvar|n}}'किसी सेट में वां सबसे बड़ा तत्व या क्रमबद्ध क्रम में किसी तत्व के सूचकांक का निर्धारण करना।<ref>{{Cite conference| doi = 10.1007/3-540-48224-5_39| title = बाइनरी सर्च ट्री को संतुलित करने की एक नई विधि| conference = [[ICALP]]| volume = 2076| pages = 469–480| series = Lecture Notes in Computer Science| year = 2001| last1 = Roura | first1 = Salvador| isbn = 978-3-540-42287-7}}</ref>
+अन्य स्व-संतुलन ट्रीस की तरह, WBT अपने नोड्स में संतुलन से संबंधित लेजर अकाउंट इनफ़ारमेशन संग्रहीत करते हैं और सम्मिलन या विलोपन संचालन पर संतुलन को पुनः आरंभ करने के लिए रोटैटिंग करते हैं। विशेष रूप से, प्रत्येक नोड पर निहित सबट्री के आकार को संग्रहीत करता है, और लेफ्ट और राइट सबट्री के आकार को एक दूसरे के कुछ कारक के अन्दर रखा जाता है। [[Index.php?title=AVL ट्री|AVL ट्री]] और ट्रीस में संतुलन जानकारी के विपरीत, WBT में लेजर अकाउंट इनफ़ारमेशन वास्तव में अनुप्रयोगों के लिए एक उपयोगी संपत्ति है: तत्वों की संख्या एक ट्री में इसकी जड़ के आकार के बराबर होता है, और आकार की जानकारी बिल्कुल एक [[Index.php?title=ऑर्डर स्टेटिस्टिक ट्री|ऑर्डर स्टेटिस्टिक ट्री]] के संचालन को लागू करने के लिए आवश्यक इनफ़ारमेशन होती है, जैसे, किसी सेट में {{mvar|n}}' का सबसे बड़ा तत्व प्राप्त करना या किसी तत्व के सूचकांक का निर्धारण करना होता है।<ref>{{Cite conference| doi = 10.1007/3-540-48224-5_39| title = बाइनरी सर्च ट्री को संतुलित करने की एक नई विधि| conference = [[ICALP]]| volume = 2076| pages = 469–480| series = Lecture Notes in Computer Science| year = 2001| last1 = Roura | first1 = Salvador| isbn = 978-3-540-42287-7}}</ref>
-वज़न-संतुलित पेड़ [[कार्यात्मक प्रोग्रामिंग]] समुदाय में लोकप्रिय हैं और एमआईटी योजना, एसएलआईबी और [[हास्केल (प्रोग्रामिंग भाषा)]] के कार्यान्वयन में सेट और मानचित्रों को लागू करने के लिए उपयोग किए जाते हैं।<ref name="Adams">{{Cite journal| doi = 10.1017/S0956796800000885| title = Functional Pearls: Efficient sets—a balancing act| journal = Journal of Functional Programming| volume = 3| issue = 4| pages = 553–561| year = 1993| last1 = Adams | first1 = Stephen| doi-access = free}}</ref><ref name="Hirai"/>
+वज़न-संतुलित ट्री [[कार्यात्मक प्रोग्रामिंग]] समुदाय में लोकप्रिय हैं और [[Index.php?title=MIT योजना|MIT योजना]], [[Index.php?title=SLIB|SLIB]] और [[हास्केल]] के कार्यान्वयन में सेट और मानचित्रों को लागू करने के लिए उपयोग किए जाते हैं।<ref name="Adams">{{Cite journal| doi = 10.1017/S0956796800000885| title = Functional Pearls: Efficient sets—a balancing act| journal = Journal of Functional Programming| volume = 3| issue = 4| pages = 553–561| year = 1993| last1 = Adams | first1 = Stephen| doi-access = free}}</ref><ref name="Hirai" />
 ==विवरण==
-भार-संतुलित वृक्ष एक द्विआधारी खोज वृक्ष है जो नोड्स में उपवृक्षों के आकार को संग्रहीत करता है। यानी एक नोड में फ़ील्ड होते हैं
+वज़न-संतुलित ट्री एक द्विआधारी सर्च ट्री है जो नोड्स में सबट्रीयों के आकार को संग्रहीत करता है। अर्थात् एक नोड में फ़ील्ड होते हैं
-* कुंजी, किसी भी आदेशित प्रकार की
+* की (कुंजी), किसी भी आदेशित प्रकार को परिभाषित करती है।
-* मान (वैकल्पिक, केवल मैपिंग के लिए)
+* वैल्यू (वैकल्पिक, केवल मैपिंग के लिए) होता है।
-* बाएँ, दाएँ, पॉइंटर से नोड तक
+* लेफ्ट, राइट, पॉइंटर से नोड तक फ़ील्ड होते हैं।
-* आकार, पूर्णांक प्रकार का।
+* साइज, पूर्णांक प्रकार का आकार होता है।
-परिभाषा के अनुसार, एक पत्ती का आकार (आमतौर पर a द्वारा दर्शाया जाता है {{mono|nil}} सूचक) शून्य है. एक आंतरिक नोड का आकार उसके दो बच्चों के आकार का योग है, प्लस एक: ({{mono|size[n] {{=}} size[n.left] + size[n.right] + 1}}). आकार के आधार पर, कोई व्यक्ति होने वाले वजन को परिभाषित करता है {{mono|weight[n] {{=}} size[n] + 1}}.{{efn|This is the definition used by Nievergelt and Reingold. Adams uses the size as the weight directly,{{r|Adams}} which complicates analysis of his variant and has led to bugs in major implementations.{{r|Hirai}}}}
+परिभाषा के अनुसार, एक लीफ का आकार शून्य है। एक आंतरिक नोड का आकार उसके दो आकार का योग है, प्लस एक: ({{mono|size[n] {{=}} size[n.left] + size[n.right] + 1}}) आकार के आधार पर, वेट को वेट के रूप में परिभाषित किया जाता है। {{mono|weight[n] {{=}} size[n] + 1}}{{efn|This is the definition used by Nievergelt and Reingold. Adams uses the size as the weight directly,{{r|Adams}} which complicates analysis of his variant and has led to bugs in major implementations.{{r|Hirai}}}}
-[[File:BinaryTreeRotations.svg|thumb|पेड़ का घूमना.]]पेड़ को संशोधित करने वाले संचालन को यह सुनिश्चित करना चाहिए कि प्रत्येक नोड के बाएँ और दाएँ उपवृक्ष का भार कुछ कारक के भीतर रहे {{mvar|α}} एक दूसरे के, समान AVL ट्री का उपयोग करके#AVL ट्री में उपयोग किया जाने वाला पुनर्संतुलन: रोटेशन और डबल रोटेशन। औपचारिक रूप से, नोड संतुलन को इस प्रकार परिभाषित किया गया है:
+[[File:BinaryTreeRotations.svg|thumb|बाइनरी ट्री रोटेशन।]]ट्री को संशोधित करने वाले संचालन को यह सुनिश्चित करना चाहिए कि AVL ट्रीस में उपयोग किए जाने वाले समान पुनर्संतुलन संचालन का उपयोग करके प्रत्येक नोड के लेफ्ट और राइट सबट्रीस का वेट एक-दूसरे के कुछ कारक {{mvar|α}} के अन्दर रहे: रोटेशन और डबल रोटेशन औपचारिक रूप से, नोड संतुलन को इस प्रकार परिभाषित किया गया है:
-:एक नोड है {{mvar|α}}-वजन-संतुलित यदि {{mono|weight[n.left] ≥ α·weight[n]}} और {{mono|weight[n.right] ≥ α·weight[n]}}.<ref name="brass">{{cite book |first=Peter |last=Brass |title=उन्नत डेटा संरचनाएँ|url=https://archive.org/details/advanceddatastru00bras |url-access=limited |year=2008 |publisher=Cambridge University Press |pages=[https://archive.org/details/advanceddatastru00bras/page/n78 61]–71}}</ref>
+:एक नोड {{mvar|α}}-भार-संतुलित है यदि {{mono|weight[n.left] ≥ α·weight[n]}} और {{mono|weight[n.right] ≥ α·weight[n]}}.<ref name="brass">{{cite book |first=Peter |last=Brass |title=उन्नत डेटा संरचनाएँ|url=https://archive.org/details/advanceddatastru00bras |url-access=limited |year=2008 |publisher=Cambridge University Press |pages=[https://archive.org/details/advanceddatastru00bras/page/n78 61]–71}}</ref>
-यहाँ, {{mvar|α}} वजन संतुलित पेड़ों को लागू करते समय निर्धारित किया जाने वाला एक संख्यात्मक पैरामीटर है। के बड़े मूल्य {{mvar|α}} अधिक संतुलित पेड़ पैदा करते हैं, लेकिन सभी मूल्य नहीं {{mvar|α}} उपयुक्त हैं; नीवरगेल्ट और रींगोल्ड ने यह साबित किया
+जहाँ, {{mvar|α}} वेट संतुलित ट्रीस को लागू करते समय निर्धारित किया जाने वाला एक संख्यात्मक पैरामीटर है। {{mvar|α}} के बड़े मान "अधिक संतुलित" ट्री उत्पन्न करते हैं, परंतु {{mvar|α}} के सभी मान उपयुक्त नहीं होते हैं; नीवरगेल्ट और रींगोल्ड ने यह सिद्ध किया है।
 :<math>\alpha < 1 - \frac{\sqrt{2}}{2} \approx 0.29289</math>
-संतुलन एल्गोरिदम के काम करने के लिए एक आवश्यक शर्त है। बाद के काम में इसकी निचली सीमा दिखाई दी {{frac|2|11}} के लिए {{mvar|α}}, हालाँकि यदि एक कस्टम (और अधिक जटिल) पुनर्संतुलन एल्गोरिथ्म का उपयोग किया जाता है तो इसे मनमाने ढंग से छोटा किया जा सकता है।{{r|brass}}
+संतुलन एल्गोरिदम के काम करने के लिए एक आवश्यक शर्त है। बाद के काम में {{mvar|α}} के लिए {{frac|2|11}} की निचली सीमा दिखाई गई, चूंकि यदि एक कस्टम पुनर्संतुलन एल्गोरिथ्म का उपयोग किया जाता है तो इसे मनमाने ढंग से छोटा किया जा सकता है।{{r|brass}}
-सही ढंग से संतुलन लागू करने से पेड़ की गारंटी होती है {{mvar|n}}तत्वों की ऊंचाई होगी{{r|brass}}
+संतुलन को सही ढंग से लागू करने से यह गारंटी मिलती है कि {{mvar|n}} तत्वों की ऊंचाई होगी।{{r|brass}}
 :<math>h \le \log_{\frac{1}{1-\alpha}} n = \frac{\log_2 n}{\log_2 \left( \frac{1}{1-\alpha} \right)} = O(\log n)</math>
-एक क्रम में आवश्यक संतुलन संचालन की संख्या {{mvar|n}} सम्मिलन और विलोपन रैखिक है {{mvar|n}}, यानी, एक परिशोधित विश्लेषण अर्थ में संतुलन के लिए ओवरहेड की निरंतर मात्रा लगती है।<ref>{{Cite journal | doi = 10.1016/0304-3975(80)90018-3| title = वजन-संतुलित पेड़ों में पुनर्संतुलन कार्यों की औसत संख्या पर| journal = Theoretical Computer Science| volume = 11| issue = 3| pages = 303–320| year = 1980| last1 = Blum | first1 = Norbert| last2 = Mehlhorn | first2 = Kurt| url = http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf}}</ref>
+{{mvar|n}} सम्मिलन और विलोपन के अनुक्रम में आवश्यक संतुलन संचालन की संख्या {{mvar|n}}  में रैखिक है, अर्थात्, संतुलन एक अमूर्त अर्थ में ओवरहेड की निरंतर मात्रा लेता है।<ref>{{Cite journal | doi = 10.1016/0304-3975(80)90018-3| title = वजन-संतुलित पेड़ों में पुनर्संतुलन कार्यों की औसत संख्या पर| journal = Theoretical Computer Science| volume = 11| issue = 3| pages = 303–320| year = 1980| last1 = Blum | first1 = Norbert| last2 = Mehlhorn | first2 = Kurt| url = http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf}}</ref>
-जबकि न्यूनतम खोज लागत के साथ एक पेड़ को बनाए रखने के लिए सम्मिलित/हटाने के संचालन में चार प्रकार के दोहरे घुमाव (एवीएल पेड़ में एलएल, एलआर, आरएल, आरआर) की आवश्यकता होती है, यदि हम केवल लॉगरिदमिक प्रदर्शन की इच्छा रखते हैं, तो एलआर और आरएल ही एकमात्र घुमाव हैं। एक ही टॉप-डाउन पास में।<ref>{{Cite journal | title = एक नया वजन संतुलित बाइनरी सर्च ट्री| journal = International Journal of Foundations of Computer Science | volume = 11 | issue = 3 | pages = 485–513 | year = 2000 | last1 = Cho | first1 = Seonghun | last2 = Sahni | first2 = Sartaj | url = https://www.researchgate.net/publication/2241064| doi = 10.1142/S0129054100000296 }}</ref>
+जबकि न्यूनतम खोज लागत के साथ एक ट्री को बनाए रखने के लिए सम्मिलित के संचालन में चार प्रकार के दोहरे घुमाव की आवश्यकता होती है, अगर हम केवल लॉगरिदमिक प्रदर्शन की इच्छा रखते हैं, तो LR और RL ही एकमात्र घुमाव हैं। एकल टॉप-डाउन पास में होता है।<ref>{{Cite journal | title = एक नया वजन संतुलित बाइनरी सर्च ट्री| journal = International Journal of Foundations of Computer Science | volume = 11 | issue = 3 | pages = 485–513 | year = 2000 | last1 = Cho | first1 = Seonghun | last2 = Sahni | first2 = Sartaj | url = https://www.researchgate.net/publication/2241064| doi = 10.1142/S0129054100000296 }}</ref>
-== संचालन और थोक संचालन सेट करें ==
+== संचालन और बल्क ऑपरेशन ==
-वजन-संतुलित पेड़ों पर कई सेट ऑपरेशन परिभाषित किए गए हैं: यूनियन (सेट सिद्धांत), इंटरसेक्शन (सेट सिद्धांत) और सेट अंतर। फिर इन सेट फ़ंक्शंस के आधार पर सम्मिलन या विलोपन पर तेज़ बल्क ऑपरेशन लागू किया जा सकता है। ये सेट ऑपरेशन दो सहायक ऑपरेशन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, वजन-संतुलित पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।<ref name="join-based">{{citation
+वज़न-संतुलित ट्रीस पर कई सेट ऑपरेशन परिभाषित किए गए हैं: संघ, प्रतिच्छेदन और सेट अंतर होते है। फिर इन सेट फंक्शन के आधार पर सम्मिलन या विलोपन पर तेज़ बल्क ऑपरेशन लागू किया जा सकता है। ये सेट ऑपरेशन दो सहायक ऑपरेशन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, वज़न-संतुलित ट्रीस का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।<ref name="join-based">{{citation
   | last1 = Blelloch | first1 = Guy E.
   | last2 = Ferizovic | first2 = Daniel
@@ Line 52: / Line 56: @@
   | url = https://groups.csail.mit.edu/mac/users/adams/BB/92-10.ps.gz
   }}.</ref>
-*जुड़ें: फ़ंक्शन जॉइन दो वजन-संतुलित पेड़ों पर है {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} और एक कुंजी {{mvar|k}} और सभी तत्वों वाला एक पेड़ लौटाएगा {{math|''t''<sub>1</sub>}}, {{math|''t''<sub>2</sub>}} साथ ही {{mvar|k}}. उसकी आवश्यकता हैं {{mvar|k}} सभी कुंजियों से बड़ा होना {{math|''t''<sub>1</sub>}} और सभी कुंजियों से छोटा {{math|''t''<sub>2</sub>}}. यदि दो पेड़ों का वजन संतुलित है, तो बाएं उपवृक्ष के साथ एक नया नोड बनाएं {{math|''t''<sub>1</sub>}}, जड़ {{mvar|k}} और दायां उपवृक्ष {{math|''t''<sub>2</sub>}}. लगता है कि {{math|''t''<sub>1</sub>}} से भारी वजन है {{math|''t''<sub>2</sub>}} (दूसरा मामला सममित है)। जॉइन की दाहिनी रीढ़ का अनुसरण करता है {{math|''t''<sub>1</sub>}} एक नोड तक {{mvar|c}} जिसके साथ संतुलित है {{math|''t''<sub>2</sub>}}. इस बिंदु पर बाएँ बच्चे के साथ एक नया नोड {{mvar|c}}, जड़ {{mvar| k}} और सही बच्चा {{math|''t''<sub>2</sub>}} c को प्रतिस्थापित करने के लिए बनाया गया है। नया नोड भार-संतुलित अपरिवर्तनीय को अमान्य कर सकता है। इसे एक या दो बार घुमाकर ठीक किया जा सकता है <math>\alpha < 1 - \frac{1}{\sqrt{2}}</math>
+*जुड़ें: फंक्शन जॉइन दो वज़न-संतुलित ट्रीस {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} और एक की (कुंजी) {{mvar|k}} पर है और एक ट्री जिसमें {{math|''t''<sub>1</sub>}}, {{math|''t''<sub>2</sub>}} और साथ ही {{mvar|k}} सभी तत्व सम्मलित होंगे। इसके लिए आवश्यक है कि {{mvar|k}}, {{math|''t''<sub>1</sub>}} की सभी कीज़ से बड़ा हो और {{math|''t''<sub>2</sub>}} की सभी कीज़ से छोटा हो। यदि दो ट्रीस का वजन संतुलित है, तो लेफ्ट सबट्री {{math|''t''<sub>1</sub>}}, रूट के और राइट सबट्री {{math|''t''<sub>2</sub>}} के साथ एक नया नोड बनाएं गा। मान लीजिए कि {{math|''t''<sub>1</sub>}} का वेट {{math|''t''<sub>2</sub>}} से अधिक है। जॉइन {{math|''t''<sub>1</sub>}} की राइट स्पाइन का अनुसरण करता है जब तक कि एक नोड {{mvar|c}} जो {{math|''t''<sub>2</sub>}} के साथ संतुलित न हो जाए। इस बिंदु पर {{mvar|c}} को बदलने के लिए लेफ्ट सबट्री {{mvar|c}}, रूट{{mvar| k}} और राइट सबट्री {{math|''t''<sub>2</sub>}} के साथ एक नया नोड बनाया जाता है। नया नोड हो सकता है वेट-संतुलित अपरिवर्तनीय को एक या दो बार घुमाकर ठीक किया जा सकता है। <math>\alpha < 1 - \frac{1}{\sqrt{2}}</math>
-*विभाजन: वजन-संतुलित पेड़ को दो छोटे पेड़ों में विभाजित करने के लिए, जो कुंजी x से छोटे हैं, और जो कुंजी x से बड़े हैं, पहले पेड़ में x डालकर जड़ से एक पथ बनाएं। इस प्रविष्टि के बाद, x से कम के सभी मान पथ के बाईं ओर मिलेंगे, और x से बड़े सभी मान दाईं ओर मिलेंगे। जॉइन लागू करने से, बायीं ओर के सभी उपवृक्षों को नीचे से ऊपर तक मध्यवर्ती नोड्स के रूप में पथ पर कुंजियों का उपयोग करके बाएँ वृक्ष बनाने के लिए नीचे से ऊपर की ओर मर्ज किया जाता है, और दायाँ भाग सममित होता है। कुछ अनुप्रयोगों के लिए, स्प्लिट एक बूलियन मान भी लौटाता है जो दर्शाता है कि पेड़ में x दिखाई देता है या नहीं। स्प्लिट की लागत है <math>O(\log n)</math>, पेड़ की ऊंचाई का क्रम. इस एल्गोरिदम का वास्तव में वजन-संतुलित पेड़ के किसी विशेष गुण से कोई लेना-देना नहीं है, और इस प्रकार यह एवीएल पेड़ जैसी अन्य संतुलन योजनाओं के लिए सामान्य है।
+*विभाजन: वजन-संतुलित ट्री को दो छोटे ट्रीस में विभाजित करने के लिए, जो की x से छोटे हैं, और जो की x से बड़े हैं, पहले ट्री पथ बनाते है। इस प्रविष्टि के बाद, x से कम के सभी मान पथ के लेफ्ट ओर, x मान के राइट होते है। जॉइन लागू करने से, लेफ्ट के सभी सबट्री मध्यवर्ती नोड्स के रूप में पथ पर कीज़ का उपयोग करके लेफ्ट ट्री बनाने के लिए नीचे से ऊपर की ओर मर्ज किया जाता है, कुछ अनुप्रयोगों के लिए, स्प्लिट एक बूलियन मान भी लौटाता है जो दर्शाता है कि ट्री में x दिखाई देता है या नहीं। स्प्लिट की लागत है <math>O(\log n)</math>, ट्री की ऊंचाई का क्रम. इस एल्गोरिदम का वास्तव में वजन-संतुलित ट्री के किसी विशेष गुण से संबंधित नहीं है, और इस प्रकार यह AVL ट्री जैसी अन्य संतुलन योजनाओं के लिए सामान्य है।
 जॉइन एल्गोरिदम इस प्रकार है:
-  फ़ंक्शन JoinRightWB(T<sub>L</sub>, के, टी<sub>R</sub>)
+  '''function''' joinRightWB(T<sub>L</sub>, k, T<sub>R</sub>)
-      (एल, के', सी) = एक्सपोज़(टी<sub>L</sub>)
+      (l, k', c) = expose(T<sub>L</sub>)
-      यदि शेष(|टी<sub>L</sub>|, |टी<sub>R</sub>|) वापसी नोड(टी<sub>L</sub>, के, टी<sub>R</sub>)
+      '''if''' balance(|T<sub>L</sub>|, |T<sub>R</sub>|) '''return''' Node(T<sub>L</sub>, k, T<sub>R</sub>)
-      अन्य
+      '''else'''
-          टी' = जॉइनराइटडब्ल्यूबी(सी, के, टी<sub>R</sub>)
+          T' = joinRightWB(c, k, T<sub>R</sub>)
-          (एल', के', आर') = एक्सपोज़(टी')
+          (l', k', r') = expose(T')
-          यदि (शेष राशि(|एल|,|टी'|)) वापसी नोड(एल, के', टी')
+          '''if''' (balance(|l|,|T'|)) '''return''' Node(l, k', T')
-          अन्यथा यदि (शेष(|l|,|l'|) और शेष(|l|+|l'|,|r'|))
+          '''else if''' (balance(|l|,|l'|) and balance(|l|+|l'|,|r'|))
-              वापसी रोटेटलेफ्ट(नोड(एल, के', टी'))
+               '''return''' rotateLeft(Node(l, k', T'))
-          अन्यथा रोटेटलेफ्ट लौटाएं(नोड(एल, के', रोटेटराइट(टी'))
+          '''else''' return rotateLeft(Node(l, k', rotateRight(T'))
-  फ़ंक्शन JoinLeftWB(T<sub>L</sub>, के, टी<sub>R</sub>)
+  '''function''' joinLeftWB(T<sub>L</sub>, k, T<sub>R</sub>)
-     /* JoinRightWB के लिए सममित */
+      /* symmetric to joinRightWB */
-  फ़ंक्शन जॉइन (टी<sub>L</sub>, के, टी<sub>R</sub>)
+  '''function''' join(T<sub>L</sub>, k, T<sub>R</sub>)
-     अगर (भारी(टी<sub>L</sub>, टी<sub>R</sub>)) रिटर्न जॉइनराइटडब्ल्यूबी(टी<sub>L</sub>, के, टी<sub>R</sub>)
+      '''if''' (heavy(T<sub>L</sub>, T<sub>R</sub>)) return joinRightWB(T<sub>L</sub>, k, T<sub>R</sub>)
-      अगर (भारी(टी<sub>R</sub>, टी<sub>L</sub>)) रिटर्न जॉइनलेफ्टडब्ल्यूबी(टी<sub>L</sub>, के, टी<sub>R</sub>)
+      '''if''' (heavy(T<sub>R</sub>, T<sub>L</sub>)) return joinLeftWB(T<sub>L</sub>, k, T<sub>R</sub>)
-     नोड(टी<sub>L</sub>, के, टी<sub>R</sub>)
+      Node(T<sub>L</sub>, k, T<sub>R</sub>)
-यहाँ संतुलन<math>(x, y)</math> मतलब दो वजन <math>x</math> और <math>y</math> संतुलित हैं. एक्सपोज़(v)=(l, k, r) का अर्थ है एक ट्री नोड निकालना <math>v</math>का बायां बच्चा <math>l</math>, नोड की कुंजी <math>k</math> और सही बच्चा <math>r</math>. नोड (एल, के, आर) का अर्थ है बाएं बच्चे का नोड बनाना <math>l</math>, चाबी <math>k</math> और सही बच्चा <math>r</math>.
+यहाँ संतुलन<math>(x, y)</math> का अर्थ है 2 वेट <math>x</math> और <math>y</math> संतुलित हैं. एक्सपोज़(v)=(l, k, r) का अर्थ है।
 विभाजन एल्गोरिथ्म इस प्रकार है:
-  फ़ंक्शन स्प्लिट (टी, के)
+  '''function''' split(T, k)
-      यदि (T = शून्य) वापसी (शून्य, गलत, शून्य)
+      '''if''' (T = nil) return (nil, false, nil)
-     (एल, (एम, सी), आर) = एक्सपोज़ (टी)
+      (L, (m, c), R) = expose(T)
-      यदि (k = m) वापसी (L, सत्य, R)
+      '''if''' (k = m) return (L, true, R)
-     यदि (k <m)
+      '''if''' (k < m)
-         (एल', बी, आर') = विभाजित(एल, के)
+         (L', b, R') = split(L, k)
-        वापसी (एल', बी, जुड़ें (आर', एम, आर))
+         '''return''' (L', b, join(R', m, R))
-     यदि (k > m)
+      '''if''' (k > m)
-        (एल', बी, आर') = विभाजित(आर, के)
+         (L', b, R') = split(R, k)
-        वापसी (जुड़ें (एल, एम, एल'), बी, आर))
+          '''return''' (join(L, m, L'), b, R))
+सेट {{mvar|A}} और {{mvar|B}} का प्रतिनिधित्व करने वाले दो वज़न-संतुलित ट्री {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} का मिलन, एक वज़न-संतुलित ट्री {{mvar|''t''}} है जो {{math|''A'' ∪ ''B''}} का प्रतिनिधित्व करता है। निम्नलिखित पुनरावर्ती फंक्शन इस मिलन की गणना करता है:
+ '''function''' union(t<sub>1</sub>, t<sub>2</sub>):
+     '''if''' t<sub>1</sub> = nil:
+         '''return''' t<sub>2</sub>
+'''if''' t<sub>2</sub> = nil:
+        '''return''' t<sub>1</sub>
-दो भार-संतुलित पेड़ों का मिलन {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} सेट का प्रतिनिधित्व करना {{mvar|A}} और {{mvar|B}}, एक वजन-संतुलित पेड़ है {{mvar|''t''}} जो प्रतिनिधित्व करता है {{math|''A'' ∪ ''B''}}. निम्नलिखित पुनरावर्ती फ़ंक्शन इस संघ की गणना करता है:
- फ़ंक्शन यूनियन(t<sub>1</sub>, टी<sub>2</sub>):
+t<sub><</sub>, t<sub>></sub> ← split t<sub>2</sub> on t<sub>1</sub>.root
-     यदि टी<sub>1</sub> = शून्य:
+      '''return''' join(union(left(t<sub>1</sub>), t<sub><</sub>), t<sub>1</sub>.root, union(right(t<sub>1</sub>), t<sub>></sub>))
-         वापसी टी<sub>2</sub>
-यदि टी<sub>2</sub> = शून्य:
-         वापसी टी<sub>1</sub>
-टी<sub><</sub>, टी<sub>></sub> ← विभाजित टी<sub>2</sub> टी पर<sub>1</sub>।जड़
-      रिटर्न जॉइन(यूनियन(बाएं(टी)<sub>1</sub>), टी<sub><</sub>), टी<sub>1</sub>.रूट, यूनियन(दाएं(t<sub>1</sub>), टी<sub>></sub>))
-यहां, स्प्लिट को दो पेड़ों को वापस करने के लिए माना जाता है: एक कुंजी को अपनी इनपुट कुंजी से कम रखता है, एक बड़ी कुंजी को रखता है। (एल्गोरिदम [[लगातार डेटा संरचना]] है | गैर-विनाशकारी, लेकिन एक इन-प्लेस विनाशकारी संस्करण भी मौजूद है।)
+यहां, स्प्लिट को दो ट्रीस को वापस करने के लिए माना जाता है: एक की को अपनी इनपुट की से कम रखता है, एक बड़ी की को रखता है।
-प्रतिच्छेदन या अंतर के लिए एल्गोरिथ्म समान है, लेकिन इसके लिए Join2 हेल्पर रूटीन की आवश्यकता होती है जो कि Join के समान है लेकिन मध्य कुंजी के बिना। संघ, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, वजन-संतुलित पेड़ में या तो एक कुंजी या एकाधिक कुंजी डाली जा सकती है या हटाई जा सकती है। चूंकि स्प्लिट और यूनियन जॉइन को कॉल करते हैं लेकिन वजन-संतुलित पेड़ों के संतुलन मानदंडों से सीधे निपटते नहीं हैं, ऐसे कार्यान्वयन को आमतौर पर जॉइन-आधारित ट्री एल्गोरिदम | जॉइन-आधारित एल्गोरिदम कहा जाता है।
+प्रतिच्छेदन या अंतर के लिए एल्गोरिथ्म समान है, लेकिन इसके लिए  जॉइन 2 हेल्पर रूटीन की आवश्यकता होती है जो कि जॉइन के समान है लेकिन मध्य की के बिना नहीं है। संघ, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, वजन-संतुलित ट्री में या तो एक की या एकाधिक की डाली जा सकती है या हटाई जा सकती है। चूंकि स्प्लिट और यूनियन कॉल जॉइन करते हैं लेकिन सीधे वजन-संतुलित ट्रीस के संतुलन मानदंडों तक पहुंचता नहीं हैं, ऐसे कार्यान्वयन को सामान्यतः [[जॉइन-बेस्ड एल्गोरिदम]] कहा जाता है।
-मिलन, प्रतिच्छेद और भेद प्रत्येक की जटिलता है <math>O\left(m \log \left({n\over m}+1\right)\right)</math> आकार के दो वजन-संतुलित पेड़ों के लिए <math>m</math> और <math>n(\ge m)</math>. तुलनाओं की संख्या की दृष्टि से यह जटिलता इष्टतम है। अधिक महत्वपूर्ण बात यह है कि चूंकि संघ, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल एक-दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर एल्गोरिदम के विश्लेषण के साथ [[समानांतर प्रोग्रामिंग]] निष्पादित की जा सकती है। <math>O(\log m\log n)</math>.<ref name="join-based"/>कब <math>m=1</math>यदि बड़े पेड़ की जड़ का उपयोग छोटे पेड़ को विभाजित करने के लिए किया जाता है, तो जॉइन-आधारित कार्यान्वयन में एकल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल [[निर्देशित अचक्रीय ग्राफ]] (डीएजी) होता है।
+प्रतिच्छेद और भेद प्रत्येक की जटिलता है <math>O\left(m \log \left({n\over m}+1\right)\right)</math> आकार के दो वजन-संतुलित ट्रीस के लिए <math>m</math> और <math>n(\ge m)</math> तुलनाओं की संख्या की दृष्टि से यह जटिलता इष्टतम है। इससे भी महत्वपूर्ण बात यह है कि चूंकि संघ, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल एक-दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर एल्गोरिदम के विश्लेषण के साथ [[समानांतर प्रोग्रामिंग]] निष्पादित की जा सकती है। <math>O(\log m\log n)</math><ref name="join-based" /> जब <math>m=1</math> यदि बड़े ट्री की जड़ का उपयोग छोटे ट्री को विभाजित करने के लिए किया जाता है, तो जॉइन-आधारित कार्यान्वयन में एकल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल [[Index.php?title=निर्देशित एसाइक्लिक ग्राफ|निर्देशित एसाइक्लिक ग्राफ]] (DAG) होता है।
 ==टिप्पणियाँ==
@@ Line 113: / Line 119: @@
 {{CS-Trees}}
-[[Category: पेड़ खोजें]]
 [[de:Balancierter Baum#Balance der Knotenzahl]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Collapse templates]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 09/08/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:पेड़ खोजें]]

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

Anonymous

Search

वेट बैलेंस्ड ट्री: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:51, 22 August 2023

Contents

विवरण

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

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

वेट बैलेंस्ड ट्री: Difference between revisions

Latest revision as of 10:51, 22 August 2023

विवरण

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

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories