ऑर्डर स्टेटिस्टिक ट्री
कंप्यूटर विज्ञान में, ऑर्डर स्टेटिस्टिक ट्री बाइनरी सर्च ट्री (या अधिक सामान्यतः, बी-ट्री ) का प्रकार है[1] जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:
- चयन एल्गोरिदम|Select(i) - ट्री में संग्रहीत i'वां सबसे छोटा तत्व ढूंढें
- रैंक (x) - ट्री में तत्व x की रैंक ढूंढें, अर्थात ट्री के तत्वों की क्रमबद्ध सूची में इसका सूचकांक
दोनों संचालन O(log n) में सबसे खराब और औसत स्थिति किए जा सकते हैं जब एक सेल्फ-बैलेंसिंग ट्री का उपयोग आधार डेटा संरचना के रूप में किया जाता है।
संवर्धित खोज ट्री कार्यान्वयन
एक नियमित खोज ट्री को ऑर्डर स्टेटिस्टिक ट्री में बदलने के लिए, ट्री के नोड्स को अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है, जो उस नोड पर निहित उपट्री का आकार है (अर्थात, इसके नीचे नोड्स की संख्या)। ट्री को संशोधित करने वाले सभी संचालनों और लूप अपरिवर्तनीय को संरक्षित करने के लिए इस जानकारी को समायोजित किया जाता है
size[x] = size[left[x]] + size[right[x]] + 1
जहाँ परिभाषा के अनुसार size[nil] = 0 है। चयन को फिर : 342 के रूप में कार्यान्वित किया जा सकता है[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.
