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

van Emde Boas tree
van Emde Boas tree
Type	Non-binary tree
Invented	1975
Invented by	Peter van Emde Boas
Time complexity in big O notation
Algorithm
Algorithm	Average
Space	O(M)
Search	O(log log M)
Insert	O(log log M)
Delete	O(log log M)

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

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

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

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

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

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

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

फलन

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

मान लीजिए किसी पूर्णांक k के लिए $log 2 m = k$ है। $M = 2 m$ को परिभाषित करें। ब्रह्माण्ड ${0, ..., M -1$ पर एक vEB ट्री T में एक रूट नोड होता है जो लंबाई √M के एक सरणी T.children[i] को संग्रहीत करता है। T.children[i] एक vEB ट्री का सूचक है जो ${i \sqrt M, ..., (i +1) \sqrt 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 / \sqrt M ⌋$ सहायक ट्री T.aux इस बात पर ध्यान देता है कि कौन से बच्चे खाली नहीं हैं, इसलिए T.aux में मान j यदि और केवल यदि सम्मिलित है T.children[j] गैर-रिक्त है।

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

ऑपरेशन FindNext(T, x) जो vEB ट्री में तत्व x के उत्तराधिकारी की खोज करता है, इस प्रकार आगे बढ़ता है: यदि x<T.min है तो खोज पूरी हो गई है, और उत्तर T.min है। यदि x≥T.max है तो अगला तत्व उपस्थित नहीं है। अन्यथा मान लीजिये कि $i = ⌊ x / \sqrt 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)$ काम करता है और फिर संभवतः आकार के ब्रह्मांड में एक उपट्री पर पुनरावृत्ति करता है $M.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2$ (एक $m / 2$ बिट ब्रह्मांड). यह के चलने के समय की पुनरावृत्ति देता है $T(m)=T(m/2)+O(1)$ , जो हल करता है $O (log m) = O (log log M)$ .

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

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

यदि T खाली है तो हम सेट करते हैं T.min = T.max = x और हमारा काम हो गया.
अन्यथा, यदि x<T.min फिर हम डालते हैं T.min उपट्री में i के लिए जिम्मेदार T.min और फिर सेट करें T.min = x. अगर T.children[i] पहले खाली था, फिर हम भी डालते हैं i में T.aux
अन्यथा, यदि x>T.max फिर हम डालते हैं x उपट्री में i के लिए जिम्मेदार x और फिर सेट करें T.max = x. अगर T.children[i] पहले खाली था, फिर हम भी डालते हैं i में T.aux
अन्यथा, 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)$ समय। इसलिए, भले ही एल्गोरिदम कभी-कभी दो पुनरावर्ती कॉल करता है, यह केवल तब होता है जब पहली पुनरावर्ती कॉल एक खाली सबट्री में थी। इससे उसी रनिंग टाइम की पुनरावृत्ति होती है $T(m)=T(m/2)+O(1)$ पहले जैसा।

हटाएं

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

अगर T.min = T.max = x तो x ट्री में संग्रहीत एकमात्र तत्व है और हम सेट करते हैं T.min = M और T.max = −1 यह इंगित करने के लिए कि ट्री खाली है।
अन्यथा, यदि x == T.min फिर हमें वीईबी ट्री में दूसरा सबसे छोटा मान y ढूंढना होगा, इसे इसके वर्तमान स्थान से हटाना होगा, और सेट करना होगा T.min=y. दूसरा सबसे छोटा मान y है T.children[T.aux.min].min, इसलिए इसे पाया जा सकता है $O (1)$ समय। हम y को उस उपट्री से हटा देते हैं जिसमें यह सम्मिलित है।
अगर x≠T.min और x≠T.max फिर हम सबट्री से x हटाते हैं T.children[i] जिसमें x सम्मिलित है।
अगर x == T.max तो हमें वीईबी ट्री और सेट में दूसरा सबसे बड़ा मान y ढूंढना होगा T.max=y. हम पिछले मामले की तरह x को हटाकर शुरुआत करते हैं। तब मान y या तो है T.min या T.children[T.aux.max].max, इसलिए इसे पाया जा सकता है $O (1)$ समय।
उपरोक्त किसी भी मामले में, यदि हम किसी उपट्री से अंतिम तत्व 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$ एक पूर्णांक अनावश्यक है. संचालन $x{\sqrt {M}}$ और $x{\bmod {\sqrt {M}}}$ केवल उच्च-क्रम लेकर प्रतिस्थापित किया जा सकता है $⌈ m /2⌉$ और निचला क्रम $⌊ m /2⌋$ का $x$ , क्रमश। किसी भी उपस्थिता मशीन पर, यह विभाजन या शेष गणना से अधिक कुशल है।

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

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

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

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

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

कार्यान्वयन

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

यह भी देखें

संदर्भ

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

अग्रिम पठन

Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Advanced Data Structures (Spring 2012). Lecture 11 notes. March 22, 2012.
van Emde Boas, P.; Kaas, R.; Zijlstra, E. (1976). "Design and implementation of an efficient priority queue". Mathematical Systems Theory. 10: 99–127. doi:10.1007/BF01683268.

[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.

[1]

[2]

[3]

[4]

[5]

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

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

Namespaces

More

Page actions

Contents

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

फलन

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

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

हटाएं

चर्चा

कार्यान्वयन

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

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

फलन

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

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

हटाएं

चर्चा

कार्यान्वयन

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories