वैन एम्डे बोस ट्री: Difference between revisions

From Vigyanwiki
No edit summary
Line 15: Line 15:
}}
}}


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


==फ़ंक्शन==
एक वीईबी ट्री न्यूनतम और अधिकतम संचालन का भी समर्थन करता है, जो क्रमशः ट्री में संग्रहीत न्यूनतम और अधिकतम तत्व लौटाता है। <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 के बाद जड़ की ऑक्स संरचना डाली गई है।]]सरलता के लिए, चलो {{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]}} गैर-रिक्त है.
[[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)}} जो वीईबी ट्री में किसी तत्व 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}}. बच्चों के स्तर पर पाए जाने वाले तत्व को एक संपूर्ण अगला तत्व बनाने के लिए उच्च बिट्स के साथ बनाने की आवश्यकता होती है।
===फाइंडनेक्स्ट===


  फ़ंक्शन फाइंडनेक्स्ट(टी, एक्स)
ऑपरेशन {{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}} लौटाता है। चिल्ड्रन लेवल पर पाए जाने वाले तत्व को एक संपूर्ण अगला तत्व बनाने के लिए उच्च बिट्स के साथ बनाने की आवश्यकता होती है।
     यदि x < T.min तो
 
         वापसी टी.मिनट
  '''function''' FindNext(T, x)
     यदि x ≥ T.max तो ''// कोई अगला तत्व नहीं''
     '''if''' x < T.min '''then'''
         वापसी एम
         '''return''' T.min
     मैं = मंजिल(x/{{sqrt|''M''}})
     '''if''' x ≥ T.max '''then''' ''// no next element''
     लो = एक्स मॉड {{sqrt|''M''}}
         '''return''' M
     i = floor(x/''M'')
     lo = x mod √''M''
      
      
     यदि lo < T.children[i].max तो
     '''if''' lo < T.children[i].max '''then'''
         वापस करना ({{sqrt|''M''}} i) + FindNext(T.children[i], lo)
         '''return''' (''M'' i) + FindNext(T.children[i], lo)
     जे = फाइंडनेक्स्ट(टी.ऑक्स, आई)
     j = FindNext(T.aux, i)
     वापस करना ({{sqrt|''M''}} जे) + टी.चिल्ड्रन[जे].मिन
     '''return''' (''M'' j) + T.children[j].min
  अंत
  '''end'''
 


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


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


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


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


===हटाएं===
===हटाएं===


वीईबी पेड़ों को हटाना सबसे मुश्किल ऑपरेशन है। कॉल {{mono|Delete(T, x)}} जो वीईबी ट्री से एक मान x हटाता है T निम्नानुसार संचालित होता है:
वीईबी ट्रीों को हटाना सबसे मुश्किल ऑपरेशन है। कॉल {{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=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|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|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)}} समय।
# अगर {{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}}.
# उपरोक्त किसी भी मामले में, यदि हम किसी उपट्री से अंतिम तत्व x या y हटाते हैं {{mono|T.children[i]}} फिर हम i को भी हटा देते हैं {{mono|T.aux}}.


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


फिर, इस प्रक्रिया की दक्षता इस तथ्य पर निर्भर करती है कि केवल एक तत्व वाले वीईबी पेड़ को हटाने में केवल निरंतर समय लगता है। विशेष रूप से, दूसरा डिलीट कॉल केवल तभी निष्पादित होता है जब ''x'' एकमात्र तत्व था {{mono|T.children[i]}} हटाने से पहले.
फिर, इस प्रक्रिया की दक्षता इस तथ्य पर निर्भर करती है कि केवल एक तत्व वाले वीईबी ट्री को हटाने में केवल निरंतर समय लगता है। विशेष रूप से, दूसरा डिलीट कॉल केवल तभी निष्पादित होता है जब ''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}}, क्रमश। किसी भी मौजूदा मशीन पर, यह विभाजन या शेष गणना से अधिक कुशल है।
यह धारणा {{math|log ''m''}} एक पूर्णांक अनावश्यक है. संचालन <math>x\sqrt{M}</math> और <math>x\bmod\sqrt{M}</math> केवल उच्च-क्रम लेकर प्रतिस्थापित किया जा सकता है {{math|⌈''m''/2⌉}} और निचला क्रम {{math|⌊''m''/2⌋}} का {{mvar|x}}, क्रमश। किसी भी उपस्थिता मशीन पर, यह विभाजन या शेष गणना से अधिक कुशल है।


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


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




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


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


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


==संदर्भ==
==संदर्भ==

Revision as of 20:41, 5 July 2023

van Emde Boas tree
TypeNon-binary tree
Invented1975
Invented byPeter van Emde Boas
Time complexity in big O notation
Algorithm Average Worst case
Space O(M) O(M)
Search O(log log M) O(log log M)
Insert O(log log M) O(log log M)
Delete O(log log M) O(log log M)

एक वैन एम्डे बोस ट्री (Dutch pronunciation: [vɑn ˈɛmdə ˈboːɑs]), जिसे वीईबी ट्री या वैन एम्डे बोस प्रायोरिटी क्यू के रूप में भी जाना जाता है, एक ट्री डेटा संरचना है जो एक सहयोगी सरणी m-बिट पूर्णांक कुंजियाँ को लागू करती है। इसका आविष्कार 1975 में डच कंप्यूटर वैज्ञानिक पीटर वैन एम्डे बोस के नेतृत्व वाले एक दल ने किया था। [1] यह सभी कार्य निष्पादित करता है O(log m) समय (यह मानते हुए कि a m बिट ऑपरेशन निरंतर समय में किया जा सकता है), या समकक्ष O(log log M) समय में, जहाँ M = 2m ट्री में संग्रहित किया जा सकने वाला सबसे बड़ा तत्व है। मापदण्ड M को ट्री में संग्रहीत तत्वों की वास्तविक संख्या के साथ भ्रमित नहीं होना चाहिए, जिसके द्वारा अन्य ट्री डेटा-संरचनाओं का प्रदर्शन प्रायः मापा जाता है।

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

समर्थित संचालन

वीईबी एक क्रमित किए गए एसोसिएटिव ऐरे के संचालन का समर्थन करता है, जिसमें सामान्य एसोसिएटिव ऐरे ऑपरेशंस के साथ-साथ दो और ऑर्डर ऑपरेशंस, फाइंडनेक्स्ट और फाइंडप्रिवियस सम्मिलित हैं:[2]

  • इन्सर्ट: एम-बिट कुंजी के साथ एक कुंजी/मूल्य युग्म डालें
  • डिलीट: किसी दी गई कुंजी से कुंजी/मान युग्म को हटाएँ
  • लुकअप: किसी दी गई कुंजी से संबद्ध मान ज्ञात करें
  • फाइंडनेक्स्ट: सबसे छोटी कुंजी के साथ कुंजी/मान जोड़ी ढूंढें जो दी गई कुंजी k से बड़ी हो
  • फाइंडप्रीवियस: सबसे बड़ी कुंजी के साथ कुंजी/मूल्य जोड़ी ढूंढें जो दी गई कुंजी k से छोटी है

एक वीईबी ट्री न्यूनतम और अधिकतम संचालन का भी समर्थन करता है, जो क्रमशः ट्री में संग्रहीत न्यूनतम और अधिकतम तत्व लौटाता है। [3] ये दोनों O(1) समय में चलते हैं, क्योंकि न्यूनतम और अधिकतम तत्व प्रत्येक ट्री में विशेषताओं के रूप में संग्रहीत होते हैं

फलन

Example van Emde Boas tree
आयाम 5 के साथ वैन एम्डे बोस ट्री का एक उदाहरण और 1, 2, 3, 5, 8 और 10 के बाद जड़ की ऑक्स संरचना डाली गई है।

मान लीजिए किसी पूर्णांक k के लिए log2 m = k है। M = 2m को परिभाषित करें। ब्रह्माण्ड {0, ..., M−1 पर एक vEB ट्री T में एक रूट नोड होता है जो लंबाई M के एक सरणी T.children[i] को संग्रहीत करता है। T.children[i] एक vEB ट्री का सूचक है जो {iM, ..., (i+1)M−1 मानों के लिए जिम्मेदार है। इसके अतिरिक्त, T दो मान T.min और T.max के साथ-साथ एक सहायक vEB ट्री T.aux भी संग्रहीत करता है।

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

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

ऑपरेशन FindNext(T, x) जो vEB ट्री में तत्व x के उत्तराधिकारी की खोज करता है, इस प्रकार आगे बढ़ता है: यदि x<T.min है तो खोज पूरी हो गई है, और उत्तर T.min है। यदि x≥T.max है तो अगला तत्व उपस्थित नहीं है। अन्यथा मान लीजिये कि i = ⌊x/M है। अगर x<T.children[i].max तो खोजा जा रहा मान इसमें समाहित T.children[i] है इसलिए T.children[i] खोज पुनरावर्ती रूप से आगे बढ़ती है। अन्यथा, हम i मान के उत्तराधिकारी T.aux की खोज करते हैं। यह हमें पहले उपट्री का सूचकांक j देता है जिसमें x से बड़ा तत्व होता है। इसके बाद एल्गोरिथम 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) काम करता है और फिर संभवतः आकार के ब्रह्मांड में एक उपट्री पर पुनरावृत्ति करता है M1/2 (एक m/2 बिट ब्रह्मांड). यह के चलने के समय की पुनरावृत्ति देता है , जो हल करता है O(log m) = O(log log M).

सम्मिलित करें

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

  1. यदि T खाली है तो हम सेट करते हैं T.min = T.max = x और हमारा काम हो गया.
  2. अन्यथा, यदि x<T.min फिर हम डालते हैं T.min उपट्री में i के लिए जिम्मेदार T.min और फिर सेट करें T.min = x. अगर T.children[i] पहले खाली था, फिर हम भी डालते हैं i में T.aux
  3. अन्यथा, यदि x>T.max फिर हम डालते हैं x उपट्री में i के लिए जिम्मेदार x और फिर सेट करें T.max = x. अगर T.children[i] पहले खाली था, फिर हम भी डालते हैं i में T.aux
  4. अन्यथा, T.min< x < T.max तो हम सम्मिलित करते हैं x उपट्री में i के लिए जिम्मेदार x. अगर T.children[i] पहले खाली था, फिर हम भी डालते हैं i में T.aux.

कोड में:

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

इस प्रक्रिया की दक्षता की कुंजी यह है कि एक खाली वीईबी ट्री में एक तत्व डालने में समय लगता है O(1) समय। इसलिए, भले ही एल्गोरिदम कभी-कभी दो पुनरावर्ती कॉल करता है, यह केवल तब होता है जब पहली पुनरावर्ती कॉल एक खाली सबट्री में थी। इससे उसी रनिंग टाइम की पुनरावृत्ति होती है पहले जैसा।

हटाएं

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

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

कोड में:

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

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

चर्चा

यह धारणा log m एक पूर्णांक अनावश्यक है. संचालन और केवल उच्च-क्रम लेकर प्रतिस्थापित किया जा सकता है m/2⌉ और निचला क्रम m/2⌋ का x, क्रमश। किसी भी उपस्थिता मशीन पर, यह विभाजन या शेष गणना से अधिक कुशल है।

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

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

ऊपर वर्णित कार्यान्वयन पॉइंटर्स का उपयोग करता है और कुल स्थान घेरता है O(M) = O(2m), प्रमुख ब्रह्मांड के आकार के समानुपाती। इस प्रकार इसे देखा जा सकता है। पुनरावृत्ति है . उसका समाधान करने से यह होगा . सौभाग्य से, कोई इसे दिखा भी सकता है S(M) = M−2 प्रेरण द्वारा.[4]


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

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

कार्यान्वयन

इसाबेल (प्रमाण सहायक) में एक सत्यापित कार्यान्वयन है।[5] कार्यात्मक शुद्धता और समय सीमा दोनों सिद्ध हैं। कुशल अनिवार्य मानक एमएल कोड उत्पन्न किया जा सकता है।

यह भी देखें

संदर्भ

  1. 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)
  2. Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF) (University of Aarhus, Department of Computer Science)
  3. 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. 531–560.
  4. Rex, A. "वैन एम्डे बोस पेड़ों की अंतरिक्ष जटिलता का निर्धारण". Retrieved 2011-05-27.
  5. Ammer, Thomas; Lammich, Peter. "एम्डे बोस पेड़ों की". Archive of Formal Proofs. Retrieved 26 November 2021.



अग्रिम पठन