View source for वैन एम्डे बोस ट्री

{{tone|date=May 2021}}
{{Infobox data structure
| name               = van Emde Boas tree
| type               = Non-binary [[tree data structure|tree]]
| invented_by        = [[Peter van Emde Boas]]
| invented_year      = 1975
| space_avg          = {{math|''O''(''M'')}}
| space_worst        = {{math|''O''(''M'')}}
| search_avg         = {{math|''O''(log log ''M'')}}
| search_worst       = {{math|''O''(log log ''M'')}}
| insert_avg         = {{math|''O''(log log ''M'')}}
| insert_worst       = {{math|''O''(log log ''M'')}}
| delete_avg         = {{math|''O''(log log ''M'')}}
| delete_worst       = {{math|''O''(log log ''M'')}}
}}

एक '''वैन एम्डे बोस ट्री''' ({{IPA-nl|vɑn ˈɛmdə ˈboːɑs}}), जिसे वीईबी ट्री या वैन एम्डे बोस प्रायोरिटी क्यू के रूप में भी जाना जाता है, एक ट्री डेटा संरचना है जो एक सहयोगी सरणी {{math|''m''}}-बिट पूर्णांक कुंजियाँ को लागू करती है। इसका आविष्कार 1975 में डच कंप्यूटर वैज्ञानिक [[पीटर वैन एम्डे बोस]] के नेतृत्व वाले एक दल ने किया था। <ref>[[Peter van Emde Boas]]: ''Preserving order in a forest in less than logarithmic time'' (''Proceedings of the 16th Annual Symposium on Foundations of Computer Science'' 10: 75-84, 1975)</ref> यह सभी कार्य निष्पादित करता है {{math|[[Big-O notation|''O'']](log&nbsp;''m'')}} समय (यह मानते हुए कि a {{math|''m''}} बिट ऑपरेशन निरंतर समय में किया जा सकता है), या समकक्ष {{math|''O''(log log&nbsp;''M'')}} समय में, जहाँ {{math|''M'' {{=}} 2<sup>''m''</sup>}} ट्री में संग्रहित किया जा सकने वाला सबसे बड़ा तत्व है। मापदण्ड {{math|''M''}} को ट्री में संग्रहीत तत्वों की वास्तविक संख्या के साथ भ्रमित नहीं होना चाहिए, जिसके द्वारा अन्य ट्री डेटा-संरचनाओं का प्रदर्शन प्रायः मापा जाता है।

वीईबी ट्री की अंतरिक्ष दक्षता ख़राब है। उदाहरण के लिए, 32-बिट पूर्णांक संग्रहीत करने के लिए (अर्थात्, कब {{math|''m''{{=}}32}}), उसकी आवश्यकता हैं {{math|''M''{{=}}2<sup>32</sup>}} भंडारण के टुकड़े। हालाँकि, समान रूप से अच्छी समय दक्षता और स्थान के साथ समान डेटा संरचनाएँ {{math|''O''(''n'')}} अस्तित्व में है, जहाँ {{math|''n''}} संग्रहीत तत्वों की संख्या है।

==समर्थित संचालन==
वीईबी एक क्रमित किए गए एसोसिएटिव ऐरे के संचालन का समर्थन करता है, जिसमें सामान्य एसोसिएटिव ऐरे ऑपरेशंस के साथ-साथ दो और ऑर्डर ऑपरेशंस, फाइंडनेक्स्ट और फाइंडप्रिवियस सम्मिलित हैं:<ref>[[Gudmund Skovbjerg Frandsen]]: ''[http://www.daimi.au.dk/~gudmund/dynamicF04/vEB.pdf Dynamic algorithms: Course notes on van Emde Boas trees (PDF)]'' ([[University of Aarhus]], Department of Computer Science)</ref>
*इन्सर्ट: एम-बिट कुंजी के साथ एक कुंजी/मूल्य युग्म डालें 
*डिलीट: किसी दी गई कुंजी से कुंजी/मान युग्म को हटाएँ
*लुकअप: किसी दी गई कुंजी से संबद्ध मान ज्ञात करें
*फाइंडनेक्स्ट: सबसे छोटी कुंजी के साथ कुंजी/मान जोड़ी ढूंढें जो दी गई कुंजी {{math|''k''}} से बड़ी हो 

*फाइंडप्रीवियस: सबसे बड़ी कुंजी के साथ कुंजी/मूल्य जोड़ी ढूंढें जो दी गई कुंजी {{math|''k''}} से छोटी है 

एक वीईबी ट्री न्यूनतम और अधिकतम संचालन का भी समर्थन करता है, जो क्रमशः ट्री में संग्रहीत न्यूनतम और अधिकतम तत्व लौटाता है। <ref> [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Third Edition. [[MIT Press]], 2009. {{ISBN|978-0-262-53305-8}}. Chapter 20: The van Emde Boas tree, pp.&nbsp;531–560.
</ref> ये दोनों O(1) समय में चलते हैं, क्योंकि न्यूनतम और अधिकतम तत्व प्रत्येक ट्री में विशेषताओं के रूप में संग्रहीत होते हैं

==फलन==

[[Image:VebDiagram.svg|thumb |alt=Example van Emde Boas tree |आयाम 5 के साथ वैन एम्डे बोस ट्री का एक उदाहरण और 1, 2, 3, 5, 8 और 10 के बाद जड़ की ऑक्स संरचना डाली गई है।]]मान लीजिए किसी पूर्णांक k के लिए {{math|log<sub>2</sub> ''m'' {{=}} ''k''}} है। {{math|''M'' {{=}} 2<sup>''m''</sup>}} को परिभाषित करें। ब्रह्माण्ड {{math|{0, ..., ''M''−1}} पर एक vEB ट्री T में एक रूट नोड होता है जो लंबाई {{sqrt|''M''}} के एक सरणी {{mono|T.children[i]}} को संग्रहीत करता है। {{mono|T.children[i]}} एक vEB ट्री का सूचक है जो {{math|{''i''{{sqrt|''M''}}, ..., (''i''+1){{sqrt|''M''}}−1}} मानों के लिए जिम्मेदार है। इसके अतिरिक्त, T दो मान {{mono|T.min}} और T.max के साथ-साथ एक सहायक vEB ट्री T.aux भी संग्रहीत करता है।

डेटा को वीईबी ट्री में निम्नानुसार संग्रहीत किया जाता है: वर्तमान में ट्री में सबसे छोटा मान {{mono|T.min}} संग्रहीत किया जाता है और सबसे बड़ा मान {{mono|T.max}} संग्रहीत किया जाता है। ध्यान दें कि {{mono|T.min}} को vEB ट्री में कहीं और संग्रहीत नहीं किया गया है, जबकि {{mono|T.max}} संग्रहीत किया गया। यदि T खाली है तो हम उस परिपाटी {{mono|1=T.max=−1}} और {{mono|1=T.min=M}} का उपयोग करते हैं।  कोई अन्य मान x उपट्री में {{mono|T.children[i]}} संग्रहीत है।  जहाँ {{math|''i'' {{=}} ⌊''x''/{{sqrt|''M''}}⌋}} सहायक ट्री {{mono|T.aux}} इस बात पर ध्यान देता है कि कौन से बच्चे खाली नहीं हैं, इसलिए {{mono|T.aux}} में मान j यदि और केवल यदि सम्मिलित है {{mono|T.children[j]}} गैर-रिक्त है।

===फाइंडनेक्स्ट===

ऑपरेशन {{mono|FindNext(T, x)}} जो vEB ट्री में तत्व x के उत्तराधिकारी की खोज करता है, इस प्रकार आगे बढ़ता है: यदि {{mono|''x''<T.min}} है तो खोज पूरी हो गई है, और उत्तर T.min है। यदि {{mono|x≥T.max}} है तो अगला तत्व उपस्थित नहीं है। अन्यथा मान लीजिये कि {{math|''i'' {{=}} ⌊''x''/{{sqrt|''M''}}⌋}} है। अगर {{mono|x<T.children[i].max}} तो खोजा जा रहा मान इसमें समाहित {{mono|T.children[i]}} है  इसलिए {{mono|T.children[i]}} खोज पुनरावर्ती रूप से आगे बढ़ती है। अन्यथा, हम i मान के उत्तराधिकारी {{mono|T.aux}} की खोज करते हैं। यह हमें पहले उपट्री का सूचकांक j देता है जिसमें x से बड़ा तत्व होता है। इसके बाद एल्गोरिथम {{mono|T.children[j].min}} लौटाता है। चिल्ड्रन लेवल पर पाए जाने वाले तत्व को एक संपूर्ण अगला तत्व बनाने के लिए उच्च बिट्स के साथ बनाने की आवश्यकता होती है।

 '''function''' FindNext(T, x)
     '''if''' x < T.min '''then'''
         '''return''' T.min
     '''if''' x ≥ T.max '''then''' ''// no next element''
         '''return''' M
     i = floor(x/√''M'')
     lo = x mod √''M''
     
     '''if''' lo < T.children[i].max '''then'''
         '''return''' (√''M'' i) + FindNext(T.children[i], lo)
     j = FindNext(T.aux, i)
     '''return''' (√''M'' j) + T.children[j].min
 '''end'''

ध्यान दें कि, किसी भी स्थिति में, एल्गोरिदम O(1) कार्य करता है और फिर संभवतः {{math|''M''<sup>{{sfrac|1|2}}</sup>}} (एक {{math|{{sfrac|''m''|2}}}} बिट समष्टि) के आकार के एक उपवृक्ष पर पुनरावृत्ति करता है)। यह {{tmath|1=T(m)=T(m/2) + O(1)}} के चलने के समय की पुनरावृत्ति देता है, जो {{math|1=''O''(log ''m'') = ''O''(log log ''M'')}} में परिवर्तित हो जाता है।

===इन्सर्ट===

कॉल {{mono|insert(T, x)}} जो एक वीईबी ट्री {{mono|T}} में एक मान x डालता है, निम्नानुसार संचालित होता है:

# यदि T खाली है तो हम {{mono|1=T.min = T.max = x}} सेट करते हैं और हमारा काम हो गया।
# अन्यथा, यदि {{mono|x&lt;T.min}} है तो हम {{mono|T.min}} को {{mono|T.min}} के लिए जिम्मेदार उपट्री {{mono|i}} में सम्मिलित करते हैं और फिर {{mono|1=T.min = x}} सेट करते हैं। यदि {{mono|T.children[i]}} पहले खाली था, तो हम {{mono|T.aux}} में i भी डालते हैं।
# अन्यथा, यदि {{mono|x&gt;T.max}}x> है तो हम x को x के लिए जिम्मेदार उप-वृक्ष i में सम्मिलित करते हैं और फिर {{mono|1=T.max = x}} सेट करते हैं। यदि {{mono|T.children[i]}} पहले खाली था, तो हम {{mono|T.aux}} में {{mono|i}} भी डालते हैं। 
# अन्यथा, {{mono|T.min&lt; x &lt; T.max}} इसलिए हम x को x के लिए जिम्मेदार उपवृक्ष i में सम्मिलित करते हैं। यदि {{mono|T.children[i]}} पहले खाली था, तो हम {{mono|T.aux}} में i भी डालते हैं।

कोड में:
 '''function''' Insert(T, x)
     '''if''' T.min > T.max '''then''' ''// T is empty''
         T.min = T.max = x;
         '''return'''
     '''if''' x < T.min '''then'''
         swap(x, T.min)
     '''if''' x > T.max '''then'''
         T.max = x
     i = floor(x / √''M'')
     lo = x mod √''M''
     Insert(T.children[i], lo)
     '''if''' T.children[i].min == T.children[i].max '''then'''
         Insert(T.aux, i)
 '''end'''

इस प्रक्रिया की दक्षता की कुंजी यह है कि एक खाली वीईबी ट्री में एक तत्व डालने में  {{math|''O''(1)}} समय लगता है। इसलिए, भले ही कलन विधि कभी-कभी दो पुनरावर्ती कॉल करता है, यह केवल तब होता है जब पहली पुनरावर्ती कॉल एक खाली सबट्री में थी। यह पहले की तरह {{tmath|1=T(m)=T(m/2) + O(1)}} की समान रनिंग टाइम पुनरावृत्ति देता है।

===डिलीट===

वीईबी ट्री को हटाना सबसे मुश्किल ऑपरेशन है। कॉल {{mono|Delete(T, x)}} जो वीईबी ट्री से एक मान x हटाता है T निम्नानुसार संचालित होता है:

# अगर {{mono|1=T.min = T.max = x}} तो x ट्री में संग्रहीत एकमात्र तत्व है और हम {{mono|1=T.min = M}} और {{mono|1=T.max = −1}} यह इंगित करने के लिए सेट करते हैं कि ट्री खाली है।
# अन्यथा, यदि {{mono|1=x == T.min}} फिर हमें वीईबी ट्री में दूसरा सबसे छोटा मान y ढूंढना होगा, इसे इसके वर्तमान स्थान से हटाना होगा, और {{mono|1=T.min=y}} सेट करना होगा। दूसरा सबसे छोटा मान y {{mono|T.children[T.aux.min].min}} है, इसलिए इसे O(1) समय में पाया जा सकता है। हम y को उस उपवृक्ष से हटा देते हैं जिसमें यह सम्मिलित है।
# यदि {{mono|x≠T.min}}x और x≠T.max है तो हम x को उपवृक्ष {{mono|T.children[i]}} से हटाते हैं जिसमें x शामिल है।
# यदि {{mono|1=x == T.max}}x है तो हमें vEB ट्री में दूसरा सबसे बड़ा मान y ढूंढना होगा और T.max=y सेट करना होगा। हम पिछली स्तिथि की तरह x को हटाकर शुरुआत करते हैं। फिर मान y या तो T.min या {{mono|T.children[T.aux.max].max}} है, इसलिए इसे O(1) समय में पाया जा सकता है।
# उपरोक्त किसी भी मामले में, यदि हम किसी सबट्री {{mono|T.children[i]}} से अंतिम तत्व x या y को हटाते हैं तो हम T.aux से i को भी हटा देते हैं।

कोड में:
 '''function''' Delete(T, x)
     '''if''' T.min == T.max == x '''then'''
         T.min = M
         T.max = −1
         '''return'''
     '''if''' x == T.min '''then'''
         hi = T.aux.min * √''M''
         j = T.aux.min
         T.min = x = hi + T.children[j].min
     i = floor(x / √''M'')
     lo = x mod √''M''
     Delete(T.children[i], lo)
     '''if''' T.children[i] is empty '''then'''
         Delete(T.aux, i)
     '''if''' x == T.max '''then'''
         '''if''' T.aux is empty '''then'''
             T.max = T.min
         '''else'''
             hi = T.aux.max * √''M''
             j = T.aux.max
             T.max = hi + T.children[j].max
 '''end'''

फिर, इस प्रक्रिया की दक्षता इस तथ्य पर निर्भर करती है कि केवल एक तत्व वाले वीईबी ट्री को हटाने में केवल निरंतर समय लगता है। विशेष रूप से, दूसरा डिलीट कॉल केवल तभी निष्पादित होता है यदि हटाए जाने से पहले {{mono|T.children[i]}} में x एकमात्र तत्व था।

===चर्चा===

यह धारणा {{math|log ''m''}} एक पूर्णांक अनावश्यक है। संचालन <math>x\sqrt{M}</math> और <math>x\bmod\sqrt{M}</math> केवल उच्च-क्रम {{math|⌈''m''/2⌉}} और निचला क्रम {{math|⌊''m''/2⌋}} का {{mvar|x}} लेकर प्रतिस्थापित किया जा सकता है। किसी भी उपस्थिता मशीन पर, यह विभाजन या शेष गणना से अधिक कुशल है।

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

वीईबी ट्री का एक स्पष्ट अनुकूलन खाली उपट्री को त्यागना है। यह वीईबी ट्री को काफी सघन बनाता है जब उनमें कई तत्व होते हैं, क्योंकि जब तक उनमें कुछ जोड़ने की आवश्यकता नहीं होती तब तक कोई उप-ट्री नहीं बनाया जाता है। प्रारंभ में, जोड़ा गया प्रत्येक तत्व लगभग लॉग (एम) नए ट्री बनाता है जिसमें लगभग एम/2 पॉइंटर्स होते हैं। जैसे-जैसे ट्री बढ़ता है, अधिक से अधिक उप-वृक्षों का पुन: उपयोग किया जाता है, विशेषकर बड़े ट्रीों का। एम तत्वों के एक पूर्ण वृक्ष में, केवल O(M) स्थान का उपयोग किया जाता है। इसके अतिरिक्त, बाइनरी सर्च ट्री के विपरीत, इस स्थान का अधिकांश उपयोग डेटा संग्रहीत करने के लिए किया जा रहा है: यहां तक कि अरबों तत्वों के लिए, पूर्ण वीईबी ट्री में पॉइंटर्स की संख्या हजारों में होती है।

ऊपर वर्णित कार्यान्वयन पॉइंटर्स का उपयोग करता है और कुंजी समष्टि के आकार के अनुपात में {{math|''O''(''M'') {{=}} ''O''(2<sup>''m''</sup>)}} का कुल स्थान घेरता है। इस प्रकार इसे देखा जा सकता है। पुनरावृत्ति <math> S(M) = O( \sqrt{M}) + (\sqrt{M}+1) \cdot S(\sqrt{M}) </math> है। इसे हल करने पर <math> S(M) \in (1 + \sqrt{M})^{\log \log M}  + \log \log M \cdot O( \sqrt{M} )</math> प्राप्त होगा। सौभाग्य से, कोई यह भी दिखा सकता है कि प्रेरण द्वारा {{math|''S''(''M'') {{=}} ''M''−2}} है।<ref>{{cite web|last=Rex|first=A|title=वैन एम्डे बोस पेड़ों की अंतरिक्ष जटिलता का निर्धारण|url=https://mathoverflow.net/q/2245 |access-date=2011-05-27}}</ref>

=== समान संरचनाएं ===
{{math|''O''(''M'')}')}} वीईबी ट्री का अंतरिक्ष उपयोग एक बहुत बड़ा उपरिव्यय है जब तक कि चाबियों के समष्टि का एक बड़ा हिस्सा संग्रहीत नहीं किया जा रहा हो। यही एक कारण है कि वीईबी ट्री व्यवहार में लोकप्रिय नहीं हैं। चिल्ड्रन को किसी अन्य डेटा संरचना में संग्रहीत करने के लिए उपयोग की जाने वाली सरणी को बदलकर इस सीमा को संबोधित किया जा सकता है। एक संभावना यह है कि प्रति स्तर केवल एक निश्चित संख्या में बिट्स का उपयोग किया जाए, जिसके परिणामस्वरूप एक प्रयास होता है। वैकल्पिक रूप से, प्रत्येक सरणी को [[हैश तालिका]] द्वारा प्रतिस्थापित किया जा सकता है, जिससे स्थान कम {{math|''O''(''n'' log log ''M'')}} हो जाता है (जहाँ {{mvar|n}} डेटा संरचना को यादृच्छिक बनाने की कीमत पर डेटा संरचना में संग्रहीत तत्वों की संख्या है)।

[[एक्स-फास्ट ट्राई]] और अधिक जटिल वाई-फास्ट प्रयास में वीईबी ट्री के लिए तुलनीय अद्यतन और क्वेरी समय होता है और उपयोग किए गए स्थान को कम करने के लिए यादृच्छिक हैश तालिकाओं का उपयोग किया जाता है। एक्स-फास्ट O(n log M) स्पेस का उपयोग करने का प्रयास करता है जबकि वाई-फास्ट O(n) स्पेस का उपयोग करने का प्रयास करता है।

== कार्यान्वयन ==
[[इसाबेल (प्रमाण सहायक)]] में एक सत्यापित कार्यान्वयन है।<ref>{{cite web |last1=Ammer |first1=Thomas |last2=Lammich |first2=Peter |title=एम्डे बोस पेड़ों की|url=https://www.isa-afp.org/entries/Van_Emde_Boas_Trees.html |website=Archive of Formal Proofs |access-date=26 November 2021}}</ref> कार्यात्मक सत्यता और समय सीमा दोनों सिद्ध हैं।

कुशल अनिवार्य [[मानक एमएल]] कोड उत्पन्न किया जा सकता है।

== यह भी देखें ==
* [[पूर्णांक छँटाई]]
* [[पूर्ववर्ती समस्या]]
* [[संलयन वृक्ष|संलयन ट्री]]
* [[टैंगो पेड़|टैंगो ट्री]]

==संदर्भ==
{{reflist}}




===अग्रिम पठन===
{{refbegin}}
* Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Advanced Data Structures (Spring 2012). [http://courses.csail.mit.edu/6.851/spring12/scribe/L11.pdf Lecture 11 notes]. March 22, 2012.
* {{cite journal |author-link1=Peter van Emde Boas |last1=van Emde Boas |first1=P. |last2=Kaas |first2=R. |last3=Zijlstra |first3=E. |year=1976 |title=Design and implementation of an efficient priority queue |journal=[[Mathematical Systems Theory]] |volume=10 |pages=99–127 |doi=10.1007/BF01683268}}
{{refend}}

{{CS trees}}

[[Category:All articles with style issues]]
[[Category:Articles with invalid date parameter in template]]
[[Category:Collapse templates]]
[[Category:Created On 25/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia articles with style issues from May 2021]]
[[Category:Wikipedia metatemplates]]
[[Category:कंप्यूटर विज्ञान लेखों पर विशेषज्ञ ध्यान देने की आवश्यकता है]]
[[Category:पेड़ खोजें]]
[[Category:प्राथमिकता कतारें]]