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

{{Short description|Self-balancing binary search tree}}
{{Other uses|इष्टतम बाइनरी सर्च ट्री}}
[[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=कॉर्पस|कॉर्पस]] की [[हफ़मैन कोडिंग]] है।

अन्य स्व-संतुलन ट्रीस की तरह, 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>

वज़न-संतुलित ट्री [[कार्यात्मक प्रोग्रामिंग]] समुदाय में लोकप्रिय हैं और [[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" />



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

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

परिभाषा के अनुसार, एक लीफ का आकार शून्य है। एक आंतरिक नोड का आकार उसके दो आकार का योग है, प्लस एक: ({{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|बाइनरी ट्री रोटेशन।]]ट्री को संशोधित करने वाले संचालन को यह सुनिश्चित करना चाहिए कि 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|α}} वेट संतुलित ट्रीस को लागू करते समय निर्धारित किया जाने वाला एक संख्यात्मक पैरामीटर है। {{mvar|α}} के बड़े मान "अधिक संतुलित" ट्री उत्पन्न करते हैं, परंतु {{mvar|α}} के सभी मान उपयुक्त नहीं होते हैं; नीवरगेल्ट और रींगोल्ड ने यह सिद्ध किया है।

:<math>\alpha < 1 - \frac{\sqrt{2}}{2} \approx 0.29289</math>
संतुलन एल्गोरिदम के काम करने के लिए एक आवश्यक शर्त है। बाद के काम में {{mvar|α}} के लिए {{frac|2|11}} की निचली सीमा दिखाई गई, चूंकि यदि एक कस्टम पुनर्संतुलन एल्गोरिथ्म का उपयोग किया जाता है तो इसे मनमाने ढंग से छोटा किया जा सकता है।{{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>

जबकि न्यूनतम खोज लागत के साथ एक ट्री को बनाए रखने के लिए सम्मिलित के संचालन में चार प्रकार के दोहरे घुमाव की आवश्यकता होती है, अगर हम केवल लॉगरिदमिक प्रदर्शन की इच्छा रखते हैं, तो 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
 | last1 = Blelloch | first1 = Guy E.
 | last2 = Ferizovic | first2 = Daniel
 | last3 = Sun | first3 = Yihan
 | contribution = Just Join for Parallel Ordered Sets
 | doi = 10.1145/2935764.2935768
 | isbn = 978-1-4503-4210-0
 | pages = 253–264
 | publisher = ACM
 | title = Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016)
 | year = 2016 | arxiv = 1602.02120
 }}.</ref><ref name="adams">{{citation
 | last1 = Adams | first1 = Stephen
 | title = Implementing sets efficiently in a functional language
 | year = 1992 | citeseerx = 10.1.1.501.8427
 | 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>}}, रूट के और राइट सबट्री {{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 दिखाई देता है या नहीं। स्प्लिट की लागत है <math>O(\log n)</math>, ट्री की ऊंचाई का क्रम. इस एल्गोरिदम का वास्तव में वजन-संतुलित ट्री के किसी विशेष गुण से संबंधित नहीं है, और इस प्रकार यह AVL ट्री जैसी अन्य संतुलन योजनाओं के लिए सामान्य है।

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

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

यहाँ संतुलन<math>(x, y)</math> का अर्थ है 2 वेट <math>x</math> और <math>y</math> संतुलित हैं. एक्सपोज़(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))

सेट {{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>


t<sub><</sub>, t<sub>></sub> ← split t<sub>2</sub> on t<sub>1</sub>.root
     '''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>))

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

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

==टिप्पणियाँ==
{{notelist}}


==संदर्भ==
{{reflist|30em}}

{{CS-Trees}}
 

[[de:Balancierter Baum#Balance der Knotenzahl]]

[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Collapse templates]]
[[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:पेड़ खोजें]]