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|''m''}}-बिट कुंजी
*हटाएँ: किसी दी गई कुंजी से कुंजी/मान युग्म को हटाएँ
*लुकअप: किसी दी गई कुंजी से संबद्ध मान ज्ञात करें
*अगला खोजें: सबसे छोटी कुंजी के साथ कुंजी/मान जोड़ी ढूंढें जो दी गई कुंजी से बड़ी हो {{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> ये दोनों अंदर भागते हैं {{math|''O''(1)}} समय, चूंकि न्यूनतम और अधिकतम तत्व प्रत्येक पेड़ में विशेषताओं के रूप में संग्रहीत होते हैं।

==फ़ंक्शन==

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

 फ़ंक्शन फाइंडनेक्स्ट(टी, एक्स)
     यदि x < T.min तो
         वापसी टी.मिनट
     यदि x ≥ T.max तो ''// कोई अगला तत्व नहीं''
         वापसी एम
     मैं = मंजिल(x/{{sqrt|''M''}})
     लो = एक्स मॉड {{sqrt|''M''}}
     
     यदि lo < T.children[i].max तो
         वापस करना ({{sqrt|''M''}} i) + FindNext(T.children[i], lo)
     जे = फाइंडनेक्स्ट(टी.ऑक्स, आई)
     वापस करना ({{sqrt|''M''}} जे) + टी.चिल्ड्रन[जे].मिन
 अंत

ध्यान दें कि, किसी भी स्थिति में, एल्गोरिदम कार्य करता है {{math|''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|x}} एक वीईबी पेड़ में {{mono|T}} निम्नानुसार संचालित होता है:

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

कोड में:
 फ़ंक्शन सम्मिलित करें (टी, एक्स)
     यदि T.min > T.max है तो ''// T खाली है''
         टी.मिनट = टी.मैक्स = एक्स;
         वापस करना
     यदि x < T.min तो
         स्वैप(एक्स, टी.मिनट)
     यदि x > T.max तो
         टी.मैक्स = एक्स
     मैं = मंजिल(x / {{sqrt|''M''}})
     लो = एक्स मॉड {{sqrt|''M''}}
     सम्मिलित करें(टी.बच्चे[i], लो)
     यदि T.children[i].min == T.children[i].max तब
         सम्मिलित करें(T.aux, i)
 अंत

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

कोड में:
 फ़ंक्शन हटाएं(टी, एक्स)
     यदि T.min == T.max == x तो
         टी.मिन = एम
         टी.मैक्स = −1
         वापस करना
     यदि x == T.min तो
         नमस्ते = T.aux.min * {{sqrt|''M''}}
         जे = टी.ऑक्स.मिन
         टी.मिनट = एक्स = हाय + टी.चिल्ड्रेन[जे].मिनट
     मैं = मंजिल(x / {{sqrt|''M''}})
     लो = एक्स मॉड {{sqrt|''M''}}
     हटाएं(टी.बच्चे[i], लो)
     यदि T.children[i] तब खाली है
         हटाएँ(T.aux, i)
     यदि x == T.max तो
         यदि T.aux खाली है तो
             टी.मैक्स = टी.मिनट
         अन्य
             हाय = टी.ऑक्स.मैक्स * {{sqrt|''M''}}
             जे = टी.ऑक्स.मैक्स
             टी.मैक्स = हाय + टी.चिल्ड्रेन[जे].मैक्स
 अंत

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

===चर्चा===

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

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

वीईबी वृक्षों का एक स्पष्ट अनुकूलन खाली उपवृक्षों को त्यागना है। यह वीईबी पेड़ों को काफी कॉम्पैक्ट बनाता है जब उनमें कई तत्व होते हैं, क्योंकि जब तक उनमें कुछ जोड़ने की आवश्यकता नहीं होती तब तक कोई उप-पेड़ नहीं बनाया जाता है। प्रारंभ में, जोड़ा गया प्रत्येक तत्व लगभग बनाता है {{math|log(''m'')}} नए पेड़ों के बारे में {{math|''m''/2}} सूचक सभी एक साथ। जैसे-जैसे पेड़ बढ़ता है, अधिक से अधिक उप-वृक्षों का पुन: उपयोग किया जाता है, विशेषकर बड़े पेड़ों का। के एक पूर्ण वृक्ष में {{math|''M''}}तत्व, केवल {{math|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}} डेटा संरचना को यादृच्छिक बनाने की कीमत पर डेटा संरचना में संग्रहीत तत्वों की संख्या है)।

[[एक्स-फास्ट ट्राई]] और अधिक जटिल वाई-फास्ट प्रयास में वीईबी पेड़ों के लिए तुलनीय अद्यतन और क्वेरी समय होता है और उपयोग किए गए स्थान को कम करने के लिए यादृच्छिक हैश तालिकाओं का उपयोग किया जाता है। एक्स-फास्ट का उपयोग करने की कोशिश करता है {{math|''O''(''n'' log ''M'')}} स्थान जबकि y-fast उपयोग करने का प्रयास करता है {{math|''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: कंप्यूटर विज्ञान लेखों पर विशेषज्ञ ध्यान देने की आवश्यकता है]] [[Category: प्राथमिकता कतारें]] [[Category: पेड़ खोजें]] 



[[Category: Machine Translated Page]]
[[Category:Created On 25/06/2023]]