ऑर्डर स्टेटिस्टिक ट्री

कंप्यूटर विज्ञान में, ऑर्डर स्टेटिस्टिक ट्री बाइनरी सर्च ट्री (या अधिक सामान्यतः, बी-ट्री ) का प्रकार है जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:

• चयन एल्गोरिदम | सेलेक्ट(i) - ट्री में संग्रहीत i'वां सबसे छोटा अवयव ढूंढें
• रैंक (x) - ट्री में अवयव x की रैंक ढूंढें, अर्थात ट्री के अवयवों की क्रमबद्ध सूची में सूचकांक

दोनों संचालन O(log n) में सबसे खराब और औसत स्थिति किए जा सकते हैं जब एक सेल्फ-बैलेंसिंग ट्री का उपयोग आधार डेटा संरचना के रूप में किया जाता है।

संवर्धित खोज ट्री कार्यान्वयन

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

size[x] = size[left[x]] + size[right[x]] + 1

जहाँ परिभाषा के अनुसार size[nil] = 0 है। चयन को फिर के रूप में कार्यान्वित किया जा सकता है

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] का उपयोग करके क्रियान्वित किया जा सकता है

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

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

बाहरी संबंध

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