ऑर्डर स्टेटिस्टिक ट्री: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, एक '''ऑर्डर स्टेटिस्टिक ट्री''' [[बाइनरी सर्च ट्री]] (या अधिक सामान्यतः, [[ बी-वृक्ष | बी-ट्री]] ) का एक प्रकार है<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> जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:
[[कंप्यूटर विज्ञान]] में, '''ऑर्डर स्टेटिस्टिक ट्री''' [[बाइनरी सर्च ट्री]] (या अधिक सामान्यतः, [[ बी-वृक्ष |बी-ट्री]] ) का प्रकार है<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> जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:


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


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


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


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


जहाँ परिभाषा के अनुसार <code>size[nil] = 0</code> है। चयन को फिर {{rp|342}} के रूप में कार्यान्वित किया जा सकता है<ref>{{Introduction to Algorithms|2}}</ref>{{rp|342}}
जहाँ परिभाषा के अनुसार <code>size[nil] = 0</code> है। चयन को फिर के रूप में कार्यान्वित किया जा सकता है<ref>{{Introduction to Algorithms|2}}</ref><syntaxhighlight>
 
function Select(t, i)                                                                                                
फ़ंक्शन चुनें(t, i)
    // Returns the i'th element (one-indexed) of the elements in t                                         
    // टी में तत्वों का i'वां तत्व (एक-अनुक्रमित) लौटाता है
    p size[left[t]]+1                                                                                            
    पी आकार[बाएं[टी+1
    if i = p                                                                                                   
    यदि मैं = पी
        return t                                                                                                     
        वापसी टी
    else if i < p                                                                                               
    अन्यथा यदि मैं <पी
        return Select(left[t], i)                                                                                
        वापसी चयन करें(बाएं[t], i)
    else                                                                                                             
    अन्य
        return Select(right[t], i - p)                                                                      
        वापसी चयन करें (दाएं[t], i - p)
</syntaxhighlight>रैंक को पैरेंट-फ़ंक्शन p[x] का उपयोग करके क्रियान्वित किया जा सकता है<ref>{{Introduction to Algorithms|3}}</ref><syntaxhighlight>
 
function Rank(T, x)                                                                                          
रैंक को पैरेंट-फ़ंक्शन p[x] का उपयोग करके लागू किया जा सकता है<ref>{{Introduction to Algorithms|3}}</ref>{{rp|342}}
    // 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                                                                                                    
    // पेड़ टी के तत्वों की रैखिक क्रमबद्ध सूची में x (एक-अनुक्रमित) की स्थिति लौटाता है
    while y ≠ T.root                                                               
    r ← आकार[बाएँ[x + 1
        if y = right[p[y]]                                                           
    y ← x
            r r + size[left[p[y]]] + 1                                                                                                      
    जबकि y ≠ टी.रूट
        y ← p[y]                                                                      
        यदि y = सही[p[y
    return r                                                                                                                                                                                                                           
            आर आर + आकार[बाएं[पी[वाई] + 1
</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>
        y ← p[y]
    वापसी आर
 
ऑर्डर-स्टेटिस्टिक पेड़ों को संतुलन बनाए रखने के लिए बहीखाता जानकारी के साथ और संशोधित किया जा सकता है (उदाहरण के लिए, ऑर्डर स्टेटिस्टिक [[ एवीएल पेड़ | एवीएल ट्री]] प्राप्त करने के लिए ट्री की ऊंचाई जोड़ी जा सकती है, या लाल-काला ट्री प्राप्त करने के लिए एक रंग बिट जोड़ा जा सकता है। लाल-काला ऑर्डर स्टेटिस्टिक ट्री)। वैकल्पिक रूप से, आकार फ़ील्ड का उपयोग बिना किसी अतिरिक्त भंडारण लागत के वजन-संतुलित वृक्ष | वजन-संतुलन योजना के संयोजन में किया जा सकता है।<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}}
{{reflist|30em}}
==बाहरी संबंध==
==बाहरी संबंध==
* [http://www.cs.yale.edu/homes/aspnes/pinewiki/OrderStatisticsTree.html Order statistic tree] on PineWiki, Yale University.
* [http://www.cs.yale.edu/homes/aspnes/pinewiki/OrderStatisticsTree.html Order statistic tree] on PineWiki, Yale University.
Line 47: Line 39:


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


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:चयन एल्गोरिदम]]
[[Category:पेड़ खोजें]]

Latest revision as of 11:46, 18 August 2023

कंप्यूटर विज्ञान में, ऑर्डर स्टेटिस्टिक ट्री बाइनरी सर्च ट्री (या अधिक सामान्यतः, बी-ट्री ) का प्रकार है[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]

संदर्भ

  1. "गिने गए बी-पेड़". 11 December 2004. Retrieved 18 January 2014.
  2. 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.
  3. 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.
  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.

बाहरी संबंध