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

van Emde Boas tree
Type	Non-binary tree
Invented	1975
Invented by	Peter 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 में डच कंप्यूटर वैज्ञानिक पीटर वैन एम्डे बोस के नेतृत्व वाले एक दल ने किया था। यह सभी कार्य निष्पादित करता है O(log m) समय (यह मानते हुए कि a m बिट ऑपरेशन निरंतर समय में किया जा सकता है), या समकक्ष O(log log M) समय में, जहाँ M = 2^m ट्री में संग्रहित किया जा सकने वाला सबसे बड़ा तत्व है। मापदण्ड M को ट्री में संग्रहीत तत्वों की वास्तविक संख्या के साथ भ्रमित नहीं होना चाहिए, जिसके द्वारा अन्य ट्री डेटा-संरचनाओं का प्रदर्शन प्रायः मापा जाता है।

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

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

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

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

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

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

फलन

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

मान लीजिए किसी पूर्णांक k के लिए log₂ m = k है। M = 2^m को परिभाषित करें। ब्रह्माण्ड {0, ..., M−1 पर एक vEB ट्री T में एक रूट नोड होता है जो लंबाई √M के एक सरणी T.children[i] को संग्रहीत करता है। T.children[i] एक vEB ट्री का सूचक है जो {i√M, ..., (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) कार्य करता है और फिर संभवतः M^1/2 (एक m/2 बिट समष्टि) के आकार के एक उपवृक्ष पर पुनरावृत्ति करता है)। यह $T(m)=T(m/2)+O(1)$ के चलने के समय की पुनरावृत्ति देता है, जो O(log m) = O(log log M) में परिवर्तित हो जाता है।

इन्सर्ट

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

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

इस प्रक्रिया की दक्षता की कुंजी यह है कि एक खाली वीईबी ट्री में एक तत्व डालने में O(1) समय लगता है। इसलिए, भले ही कलन विधि कभी-कभी दो पुनरावर्ती कॉल करता है, यह केवल तब होता है जब पहली पुनरावर्ती कॉल एक खाली सबट्री में थी। यह पहले की तरह $T(m)=T(m/2)+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.minx और x≠T.max है तो हम x को उपवृक्ष T.children[i] से हटाते हैं जिसमें x शामिल है।
4. यदि x == T.maxx है तो हमें vEB ट्री में दूसरा सबसे बड़ा मान y ढूंढना होगा और T.max=y सेट करना होगा। हम पिछली स्तिथि की तरह x को हटाकर शुरुआत करते हैं। फिर मान y या तो T.min या T.children[T.aux.max].max है, इसलिए इसे O(1) समय में पाया जा सकता है।
5. उपरोक्त किसी भी मामले में, यदि हम किसी सबट्री 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

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

चर्चा

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

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

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

समान संरचनाएं

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

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

कार्यान्वयन

इसाबेल (प्रमाण सहायक) में एक सत्यापित कार्यान्वयन है। कार्यात्मक सत्यता और समय सीमा दोनों सिद्ध हैं।

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

यह भी देखें

• पूर्णांक छँटाई
• पूर्ववर्ती समस्या
• संलयन ट्री
• टैंगो ट्री

संदर्भ

अग्रिम पठन

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