वान एम्दे बोस ट्री

सभी को शुभ दिन!

आज मैं आपको एक दिलचस्प डेटा संरचना के बारे में बताऊंगा, जिसके बारे में कुछ ही लोगों ने सुना है और जिसके बारे में बहुत कम अवांछनीय रूप से RuNet में लिखा गया है, और अंग्रेजी जानकारी में, सामान्य रूप से भी विरल है। यह स्थिति को सुधारने और जनता के साथ एक सुलभ रूप में विदेशी डेटा संरचना को साझा करने का निर्णय लिया गया था।

वैन एम्ड बोआस पेड़ एक साहचर्य सरणी है जो आपको पूर्णांक को श्रेणी में संग्रहीत करने की अनुमति देता है [0; U), जहाँ U = 2 ^k , दूसरे शब्दों में, संख्याएँ k बिट्स से अधिक नहीं होती हैं। ऐसा लगता है, हमें किसी अन्य पेड़ की आवश्यकता क्यों है, जो हमें केवल पूर्णांक स्टोर करने की अनुमति देता है, जब कई अलग-अलग संतुलित बाइनरी खोज पेड़ होते हैं जो आपको ओ, (लॉग एन) में सम्मिलन, विलोपन और अन्य संचालन करने की अनुमति देते हैं, जहां n पेड़ में तत्वों की संख्या है। ?

इस संरचना की मुख्य विशेषता हे (लॉग (लॉग (यू))) के दौरान सभी कार्यों का प्रदर्शन है, भले ही इसमें संग्रहीत तत्वों की संख्या हो।

दरअसल, यहाँ समर्थित कार्यों की एक छोटी सूची है:

• इन्सर्ट (x) - एक नंबर को एक पेड़ में डालें
• निकालें (x) - एक संख्या निकालें
• गेटमिन (), गेटमैक्स () - पेड़ में न्यूनतम और अधिकतम ढूँढना
• Find (x) - एक पेड़ में एक नंबर के लिए खोजें
• FindNext (x) - ट्री में निहित x के बाद अगले नंबर की खोज करें
• FindPrepret (x) - पिछले एक्स नंबर के लिए खोजें

इसी समय, निश्चित रूप से, आप प्रत्येक संख्या के साथ कुछ जानकारी जोड़ सकते हैं, कहते हैं, हम कुछ सामानों की संख्या को पेड़ में संग्रहीत करेंगे और संख्या से हम माल के नाम का पता लगा सकते हैं, अर्थात, ढूँढें (x) केवल सही नहीं होगा / गलत - उत्पाद मौजूद है या नहीं, और नंबर x के साथ उत्पाद का नाम। हम एक कार्यान्वयन पर गौर करेंगे जो अतिरिक्त जानकारी के बिना केवल संख्याओं को संग्रहीत करता है। यह सुविधा कठिन नहीं है।

इसलिए, हम अपनी संरचना का निर्माण शुरू करेंगे, और हम इसे पुनरावर्ती रूप से बनाएंगे।

के-ट्री को इंटरवल में संख्याओं को रखने दें [0]; 2 ^k ), यानी, k बिट्स से मिलकर। इसके अलावा, संख्या k अपने आप में दो की शक्ति होगी, बाद में यह स्पष्ट होगा कि हमें ऐसी स्थिति की आवश्यकता क्यों है। फिर यह स्पष्ट है कि 1-ट्री का निर्माण कैसे किया जाता है, यह केवल इस बारे में जानकारी संग्रहीत करेगा कि इसमें नंबर 0 या 1 मौजूद है या नहीं।

अब एक के-वृक्ष का निर्माण करें। यह स्टोर करेगा:

• 2 ^{k / 2} टुकड़े (k / 2)-पेड़
• सहायक (k / 2) -tree
• इस पेड़ में निहित न्यूनतम और अधिकतम संख्या (यदि यह खाली नहीं है)

यह समझ से बाहर हो जाता है, हमें यह सब क्यों चाहिए?

अब कल्पना करें कि हम एक बी-एक्स को सम्मिलित करने का प्रयास कर रहे हैं, जिसमें k बिट्स शामिल हैं, एक के-ट्री में, जिसमें उप-बच्चों वाले बच्चे हैं [0..2 ^{k / 2} - 1]। उदाहरण के लिए, चलो x = 93. आइए इसके बाइनरी प्रतिनिधित्व को देखें:



हम अपनी संख्या को दो बराबर भागों में विभाजित करते हैं, उच्च और निम्न, प्रत्येक (k / 2) बिट्स के साथ। हम याद करते हैं कि हमारे पेड़ में 2 ^{k / 2} पेड़ हैं जो (k / 2) बिट्स की संख्या को संग्रहीत करते हैं। और अब हम इन सभी पेड़ों को उच्च-से-गिनती (यानी, बच्चों [उच्च]) से लेते हैं और पुन: इसमें कम संख्या डालते हैं।

इस प्रकार, हम नंबर x, स्यूडोकोड के पेड़ T में डालने और खोजने के लिए एक सरल एल्गोरिथ्म प्राप्त करते हैं:

insert(T, x): if Tk == 1: T.exist[x] = True #      1- else: insert(T.children[high(x)], low(x)) find(T, x): if Tk == 1: return T.exist[x] else: return find(T.children[high(x)], low(x)) 

आइए हम इन कार्यों के संचालन समय का अनुमान लगाते हैं। T-(k) k- ट्री में संख्या के लिए सम्मिलित / खोज करने के लिए आवश्यक परिचालनों की संख्या है। 1-ट्री में सम्मिलित / खोज करने के लिए, हमें O (1) संचालन की आवश्यकता होती है, हमें वह T (1) = O (1) मिलता है। यदि हम k- ट्री (k> 1) पर विचार करते हैं, तो हमें यह पता चलता है कि इसमें बिट संचालन का उपयोग करते हुए संख्या का कटाव O (1) में होता है, जिसके बाद हम (k / 2) ट्री के लिए इन्सर्ट / सर्च ऑपरेशन करते हैं, ऐसे कि टी (के) = ओ (1) + टी (के / 2)। इस समीकरण का स्पष्ट समाधान T (k) = O (लॉग (k)) = O (लॉग (लॉग (U))) है। इससे पता चलता है कि हमने सम्मिलन और खोज के लिए आवश्यक विषम व्यवहार को प्राप्त कर लिया है।

दुर्भाग्य से, इस तरह की संरचना केवल सम्मिलित करने, खोज और हटाने के संचालन के साथ, इसे हल्के ढंग से डालने के लिए, ज्यादातर मामलों में संवेदनहीन है, यह देखते हुए कि इस मामले में एक नियमित सरणी ए बनाना आसान था, जिस तत्व में यह संग्रहीत है कि क्या कोई संख्या x है हमारा सेट है या नहीं।

यह स्थिति को सुधारने का समय है! ऐसा करने के लिए, हम कहते हैं, FindNext (x) ऑपरेशन को लागू करते हैं। आपको याद दिला दूं कि यह ऑपरेशन हमारे पेड़ में निहित न्यूनतम संख्या q को खोजता है, जैसे कि q> = x।

ऐसा करने के लिए, थोड़ा हमारी संरचना का पूरक है। आपको याद दिला दूं कि मैंने शुरुआत में ही कहा था कि हम के-ट्री में न केवल 2 ^{k / 2 के} पेड़ (k / 2) के पेड़, बल्कि इसमें न्यूनतम, अधिकतम और एक और सहायक (k / 2) पेड़ को स्टोर करेंगे, चलो इसे aux कहते हैं (अंग्रेजी से। सहायक - सहायक)। यह हमारी मदद कैसे करेगा?

के-ट्री को इसके उप-बच्चों के साथ लें [0..2 ^{k / 2} - 1] और सहायक ट्री ऑक्स। ऑक्स में, हम ऐसे सभी नंबरों को स्टोर करेंगे जैसे कि बच्चे [पी] का पेड़ खाली नहीं है, यानी इसमें कम से कम एक नंबर होता है। तदनुसार, यदि बच्चों का pth पेड़ [p] खाली है, तो संख्या p ऑक्स में समाहित नहीं है।

इसके अलावा, हम एक मामूली संशोधन करेंगे: किसी भी पेड़ के लिए T हम उसके सबटाइटल T.children में न्यूनतम संख्या को संग्रहीत नहीं करेंगे, हम इसे केवल चर T.min में लिखते हैं। जब डालने के अनुरोध में हमें इसमें एक नंबर x डालना होता है जो T.min से कम है, क्योंकि T.min हमारे उपप्रकारों में समाहित नहीं है, इसे उपशीर्षक में डालें, और फिर T.min = x असाइन करें।

ध्यान दें कि अब हम केस k = 1 पर अलग से विचार नहीं करेंगे, क्योंकि हमारे पास चर T.min और T.max हैं। और यदि कहें, एक 1-ट्री में 0 और 1 की संख्या होती है, तो इसका बस T.min = 0 होगा, और T.max = 1. यदि, उदाहरण के लिए, इसमें केवल 1 नंबर होता है, तो यह T.min होगा। = T.max = 1।

अब पेड़ में सम्मिलन एल्गोरिदम पर विचार करें, उपरोक्त सभी को ध्यान में रखते हुए:

 insert(T, x): if T.is_empty(): T.min = T.max = x else: if x < T.min: swap(x, T.min) #      ,     if x > T.max: T.max = x if Tk != 1: #   1-,      -  if T.children[high(x)].is_empty(): insert(T.aux, high(x)) #  ,   insert   O(1) insert(T.children[high(x)], low(x)) 

इसके संचालन समय का विषम व्यवहार अभी भी O (लॉग (लॉग (U))) होगा, यह सम्मिलित फ़ंक्शन के पिछले संस्करण के समान मूल्यांकन किया गया है। केवल यह ध्यान रखना आवश्यक है कि यदि हम ऑक्स में सम्मिलित करते हैं, तो यह निम्नलिखित डालें ओ (1) के लिए काम करेगा, क्योंकि यह सबट्री खाली होगी।

खोज फ़ंक्शन थोड़ा बदल जाएगा:

 find(T, x): if T.is_empty(): return False else if T.min == x or T.max == x: #  T.max == x      return True else: return find(T.children[high(x)], low(x)) 

अब FindNext (x) फ़ंक्शन पर विचार करें, यहां टिप्पणियों के साथ इसका छद्म कोड है:

 find_next(T, x): if T.is_empty() or x > T.max: return None #    x      if x <= T.min: return T.min #    ,     if Tk == 1: #   1- if T.max == x: return T.max else: return None if not T.children[high(x)].is_empty() and low(x) <= T.children[high(x)].max: # ,  ,   ,   high(x) return merge(high(x), find_next(T.children[high(x)], low(x))) else: #      ,    next_high = find_next(aux, high(x) + 1) #     if next_high != None: return merge(next_high, T.children[next_high].min) #  ,    return None merge(high, low): return   (k / 2)-  high  low 

उसके काम का विषम व्यवहार स्पष्ट रूप से हे (लॉग (लॉग)) है।

मुझे लगता है कि इस तरह के फ़ंक्शंस को निकालें, फाइंडप्रैस्प के रूप में लिखना और दूसरों को बहुत कठिनाई नहीं होनी चाहिए, क्योंकि वे सभी एक ही तरह से लिखे गए हैं, इसलिए मैं उनके छद्म कोड को छोड़ दूँगा।

आवेदन

वान ईमेड बोस पेड़ के स्पष्ट उपयोग के अलावा, आप कई अप्रत्याशित चीजों के साथ आ सकते हैं, उदाहरण के लिए:

• ओ (एन * लॉग (लॉग (यू)) में एन नंबर के एक क्रम को क्रमबद्ध करें)

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

• O (n * लॉग (लॉग) (U)) में सबसे लंबे समय तक बढ़ने वाले परिणाम का पता लगाना)

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

• ओ (ई * लॉग (यू)) के लिए दिक्जस्ट्रा का एल्गोरिथ्म)

  उन लोगों के लिए जो एक भारित ग्राफ में सबसे छोटा रास्ता खोजने के लिए दिज्क्स्ट्रा के एल्गोरिथ्म से परिचित नहीं हैं, मेरा सुझाव है कि आप अपने आप को इसके साथ परिचित करते हैं, साथ ही साथ इस लेख को भी। दीजकस्ट्रा के एल्गोरिथ्म का कार्यान्वयन ढेर का उपयोग करके, जैसा कि आप जानते हैं, ओ (ई * लॉग (वी)) के लिए काम करता है, जहां वी कोने की संख्या है और ई किनारों की संख्या है। लेकिन अगर अब ढेर के बजाय हम पहले से ही ज्ञात डेटा संरचना को हम सभी पर लागू करते हैं, तो हमें एसिम्पोटिक्स ओ (ई * लॉग (लॉग (यू))) मिलता है, जो अच्छी खबर है।
  
  
• और कई, कई और अधिक कार्य, जिनमें से केवल आपकी कल्पना से सीमित है :)

इन सभी एल्गोरिदम का माइनस यह है कि बहुत बड़े यू के लिए वैन एमडे बोस ट्री अधिक मेमोरी (एक मोटा अनुमान ओ (यू) है) पर कब्जा कर लेगा, जो कि, आवश्यक रूप से "लेज़ीली," बनाकर आंशिक रूप से बचा जा सकता है। केवल जब हमें उनकी आवश्यकता हो।

एक निष्कर्ष के बजाय

यहाँ C ++ में वैन एम्ड बोआस पेड़ का मेरा कार्यान्वयन है। वह सही होने का दिखावा नहीं करती, लेकिन उसे अपना काम पूरा करना चाहिए। परिवर्धन और टिप्पणियां स्वागत योग्य हैं।

आपका ध्यान देने के लिए आप सभी का धन्यवाद!