ऑर्डर स्टेटिस्टिक ट्री
कंप्यूटर विज्ञान में, ऑर्डर स्टेटिस्टिक ट्री बाइनरी सर्च ट्री (या अधिक सामान्यतः, बी-ट्री ) का प्रकार है[1] जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:
- चयन एल्गोरिदम | सेलेक्ट(i) - ट्री में संग्रहीत i'वां सबसे छोटा अवयव ढूंढें
- रैंक (x) - ट्री में अवयव x की रैंक ढूंढें, अर्थात ट्री के अवयवों की क्रमबद्ध सूची में सूचकांक
दोनों संचालन O(log n) में सबसे खराब और औसत स्थिति किए जा सकते हैं जब एक सेल्फ-बैलेंसिंग ट्री का उपयोग आधार डेटा संरचना के रूप में किया जाता है।
संवर्धित खोज ट्री कार्यान्वयन
एक नियमित खोज ट्री को ऑर्डर स्टेटिस्टिक ट्री में बदलने के लिए, ट्री के नोड्स को अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है, जो उस नोड पर निहित उपट्री का आकार है (अर्थात, इसके नीचे नोड्स की संख्या)। ट्री को संशोधित करने वाले सभी संचालनों और लूप अपरिवर्तनीय को संरक्षित करने के लिए इस जानकारी को समायोजित किया जाता है
size[x] = size[left[x]] + size[right[x]] + 1
जहाँ परिभाषा के अनुसार size[nil] = 0 है। चयन को फिर के रूप में कार्यान्वित किया जा सकता है[2]
function Select(t, i)
// Returns the i'th element (one-indexed) of the elements in t
p ← size[left[t]]+1
if i = p
return t
else if i < p
return Select(left[t], i)
else
return Select(right[t], i - p)रैंक को पैरेंट-फ़ंक्शन p[x] का उपयोग करके क्रियान्वित किया जा सकता है[3]
function Rank(T, x)
// Returns the position of x (one-indexed) in the linear sorted list of elements of the tree T
r ← size[left[x]] + 1
y ← x
while y ≠ T.root
if y = right[p[y]]
r ← r + size[left[p[y]]] + 1
y ← p[y]
return rऑर्डर-स्टेटिस्टिक ट्री को संतुलन बनाए रखने के लिए बहीखाता जानकारी के साथ और संशोधित किया जा सकता है (उदाहरण के लिए, ऑर्डर स्टेटिस्टिक एवीएल ट्री प्राप्त करने के लिए ट्री की ऊंचाई जोड़ी जा सकती है, या लाल-काला ऑर्डर स्टेटिस्टिक ट्री प्राप्त करने के लिए रंग बिट को जोड़ा जा सकता है)। वैकल्पिक रूप से, आकार क्षेत्र का उपयोग बिना किसी अतिरिक्त संचय निवेश के भार-संतुलन योजना के संयोजन में किया जा सकता है।[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.