ऑर्डर स्टेटिस्टिक ट्री
कंप्यूटर विज्ञान में, एक ऑर्डर स्टेटिस्टिक ट्री बाइनरी सर्च ट्री (या अधिक सामान्यतः, बी-वृक्ष ) का एक प्रकार है[1]) जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:
- चयन एल्गोरिदम|Select(i) - पेड़ में संग्रहीत i'वां सबसे छोटा तत्व ढूंढें
- रैंक (x) - पेड़ में तत्व x की रैंक ढूंढें, यानी पेड़ के तत्वों की क्रमबद्ध सूची में इसका सूचकांक
दोनों ऑपरेशन इसमें किए जा सकते हैं O(log n) सबसे अच्छा, सबसे खराब और औसत मामला वह समय है जब एक स्व-संतुलन द्विआधारी खोज वृक्ष |सेल्फ-बैलेंसिंग ट्री का उपयोग आधार डेटा संरचना के रूप में किया जाता है।
संवर्धित खोज वृक्ष कार्यान्वयन
एक नियमित खोज ट्री को ऑर्डर स्टेटिस्टिक ट्री में बदलने के लिए, ट्री के नोड्स को एक अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है, जो उस नोड पर निहित उपट्री का आकार है (यानी, इसके नीचे नोड्स की संख्या)। पेड़ को संशोधित करने वाले सभी ऑपरेशनों को लूप अपरिवर्तनीय को संरक्षित करने के लिए इस जानकारी को समायोजित करना होगा
आकार[x] = आकार[बाएं[x + आकार[दाएं[x + 1
कहाँ size[nil] = 0 परिभाषा से। फिर चयन को इस प्रकार कार्यान्वित किया जा सकता है[2]: 342
फ़ंक्शन चुनें(t, i)
// टी में तत्वों का i'वां तत्व (एक-अनुक्रमित) लौटाता है
पी ← आकार[बाएं[टी+1
यदि मैं = पी
वापसी टी
अन्यथा यदि मैं <पी
वापसी चयन करें(बाएं[t], i)
अन्य
वापसी चयन करें (दाएं[t], i - p)
रैंक को पैरेंट-फ़ंक्शन p[x] का उपयोग करके लागू किया जा सकता है[3]: 342
फ़ंक्शन रैंक (टी, एक्स)
// पेड़ टी के तत्वों की रैखिक क्रमबद्ध सूची में x (एक-अनुक्रमित) की स्थिति लौटाता है
r ← आकार[बाएँ[x + 1
y ← x
जबकि y ≠ टी.रूट
यदि y = सही[p[y
आर ← आर + आकार[बाएं[पी[वाई] + 1
y ← p[y]
वापसी आर
ऑर्डर-स्टेटिस्टिक पेड़ों को संतुलन बनाए रखने के लिए बहीखाता जानकारी के साथ और संशोधित किया जा सकता है (उदाहरण के लिए, ऑर्डर स्टेटिस्टिक एवीएल पेड़ प्राप्त करने के लिए पेड़ की ऊंचाई जोड़ी जा सकती है, या लाल-काला पेड़ प्राप्त करने के लिए एक रंग बिट जोड़ा जा सकता है। लाल-काला ऑर्डर स्टेटिस्टिक ट्री)। वैकल्पिक रूप से, आकार फ़ील्ड का उपयोग बिना किसी अतिरिक्त भंडारण लागत के वजन-संतुलित वृक्ष | वजन-संतुलन योजना के संयोजन में किया जा सकता है।[4]
संदर्भ
- ↑ "गिने गए बी-पेड़". 11 December 2004. Retrieved 18 January 2014.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
- ↑ Roura, Salvador (2001). बाइनरी सर्च ट्री को संतुलित करने की एक नई विधि. ICALP. Lecture Notes in Computer Science. Vol. 2076. pp. 469–480. doi:10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7.
बाहरी संबंध
- Order statistic tree on PineWiki, Yale University.
- The Python package blist uses order statistic B-trees to implement lists with fast insertion at arbitrary positions.
