View source for ऑर्डर स्टेटिस्टिक ट्री

[[कंप्यूटर विज्ञान]] में, '''ऑर्डर स्टेटिस्टिक ट्री''' [[बाइनरी सर्च ट्री]] (या अधिक सामान्यतः, [[ बी-वृक्ष |बी-ट्री]] ) का प्रकार है<ref>{{cite web |url=http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html |title=गिने गए बी-पेड़|date=11 December 2004 |access-date=18 January 2014}}</ref> जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:

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

दोनों संचालन {{math|''O''(log ''n'')                                                                                      }} में सबसे खराब और औसत स्थिति किए जा सकते हैं जब एक [[ स्व-संतुलन द्विआधारी खोज वृक्ष |सेल्फ-बैलेंसिंग ट्री]] का उपयोग आधार डेटा संरचना के रूप में किया जाता है।

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

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

जहाँ परिभाषा के अनुसार <code>size[nil] = 0</code> है। चयन को फिर  के रूप में कार्यान्वित किया जा सकता है<ref>{{Introduction to Algorithms|2}}</ref><syntaxhighlight>
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)                                                                       
</syntaxhighlight>रैंक को पैरेंट-फ़ंक्शन p[x] का उपयोग करके क्रियान्वित किया जा सकता है<ref>{{Introduction to Algorithms|3}}</ref><syntaxhighlight>
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                                                                                                                                                                                                                             
</syntaxhighlight>ऑर्डर-स्टेटिस्टिक ट्री को संतुलन बनाए रखने के लिए बहीखाता जानकारी के साथ और संशोधित किया जा सकता है (उदाहरण के लिए, ऑर्डर स्टेटिस्टिक [[ एवीएल पेड़ |एवीएल ट्री]] प्राप्त करने के लिए ट्री की ऊंचाई जोड़ी जा सकती है, या लाल-काला ऑर्डर स्टेटिस्टिक ट्री प्राप्त करने के लिए रंग बिट को जोड़ा जा सकता है)। वैकल्पिक रूप से, आकार क्षेत्र का उपयोग बिना किसी अतिरिक्त संचय निवेश  के भार-संतुलन योजना के संयोजन में किया जा सकता है।<ref>{{Cite conference| doi = 10.1007/3-540-48224-5_39| title = बाइनरी सर्च ट्री को संतुलित करने की एक नई विधि| conference = [[ICALP]]| volume = 2076| pages = 469–480| series = Lecture Notes in Computer Science| year = 2001| last1 = Roura | first1 = Salvador| isbn = 978-3-540-42287-7}}</ref>
==संदर्भ==
{{reflist|30em}}
==बाहरी संबंध==
* [http://www.cs.yale.edu/homes/aspnes/pinewiki/OrderStatisticsTree.html Order statistic tree] on PineWiki, Yale University.
* The [[Python (programming language)|Python]] package [http://stutzbachenterprises.com/blist/ blist] uses order statistic B-trees to implement [[List (abstract data type)|lists]] with fast insertion at arbitrary positions.

{{CS-Trees}}
[[Category: पेड़ खोजें]] [[Category: चयन एल्गोरिदम]] 



[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Vigyan Ready]]