ऑर्डर स्टेटिस्टिक ट्री: Difference between revisions
From Vigyanwiki
(Created page with "कंप्यूटर विज्ञान में, एक ऑर्डर स्टेटिस्टिक ट्री बाइनरी सर्च ट्र...") |
No edit summary |
||
| 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) - | * चयन एल्गोरिदम|Select(i) - ट्री में संग्रहीत i'वां सबसे छोटा तत्व ढूंढें | ||
* रैंक (x) - | * रैंक (x) - ट्री में तत्व x की रैंक ढूंढें, अर्थात ट्री के तत्वों की क्रमबद्ध सूची में इसका सूचकांक | ||
दोनों | दोनों संचालन {{math|''O''(log ''n'')}} में सबसे खराब और औसत स्थिति किए जा सकते हैं जब एक [[ स्व-संतुलन द्विआधारी खोज वृक्ष | सेल्फ-बैलेंसिंग ट्री]] का उपयोग आधार डेटा संरचना के रूप में किया जाता है। | ||
'''कते हैं जब एक [[ स्व-संतुलन द्विआधारी खोज वृक्ष | सेल्फ-बैलेंसिंग ट्री]] का उपयोग आधार डेटा संरचना के रूप में किया जाता है।''' | |||
==संवर्धित खोज वृक्ष कार्यान्वयन== | ==संवर्धित खोज वृक्ष कार्यान्वयन== | ||
एक नियमित खोज ट्री को ऑर्डर स्टेटिस्टिक ट्री में बदलने के लिए, ट्री के नोड्स को एक अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है, जो उस नोड पर निहित उपट्री का आकार है (यानी, इसके नीचे नोड्स की संख्या)। | एक नियमित खोज ट्री को ऑर्डर स्टेटिस्टिक ट्री में बदलने के लिए, ट्री के नोड्स को एक अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है, जो उस नोड पर निहित उपट्री का आकार है (यानी, इसके नीचे नोड्स की संख्या)। ट्री को संशोधित करने वाले सभी ऑपरेशनों को [[ लूप अपरिवर्तनीय ]] को संरक्षित करने के लिए इस जानकारी को समायोजित करना होगा | ||
आकार[x] = आकार[बाएं[x + आकार[दाएं[x + 1 | आकार[x] = आकार[बाएं[x + आकार[दाएं[x + 1 | ||
| Line 35: | Line 37: | ||
वापसी आर | वापसी आर | ||
ऑर्डर-स्टेटिस्टिक पेड़ों को संतुलन बनाए रखने के लिए बहीखाता जानकारी के साथ और संशोधित किया जा सकता है (उदाहरण के लिए, ऑर्डर स्टेटिस्टिक [[ एवीएल पेड़ ]] प्राप्त करने के लिए | ऑर्डर-स्टेटिस्टिक पेड़ों को संतुलन बनाए रखने के लिए बहीखाता जानकारी के साथ और संशोधित किया जा सकता है (उदाहरण के लिए, ऑर्डर स्टेटिस्टिक [[ एवीएल पेड़ | एवीएल ट्री]] प्राप्त करने के लिए ट्री की ऊंचाई जोड़ी जा सकती है, या लाल-काला ट्री प्राप्त करने के लिए एक रंग बिट जोड़ा जा सकता है। लाल-काला ऑर्डर स्टेटिस्टिक ट्री)। वैकल्पिक रूप से, आकार फ़ील्ड का उपयोग बिना किसी अतिरिक्त भंडारण लागत के वजन-संतुलित वृक्ष | वजन-संतुलन योजना के संयोजन में किया जा सकता है।<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> | ||
Revision as of 11:32, 16 July 2023
कंप्यूटर विज्ञान में, एक ऑर्डर स्टेटिस्टिक ट्री बाइनरी सर्च ट्री (या अधिक सामान्यतः, बी-ट्री ) का एक प्रकार है[1] जो सम्मिलन, लुकअप और विलोपन से परे दो अतिरिक्त संचालन का समर्थन करता है:
- चयन एल्गोरिदम|Select(i) - ट्री में संग्रहीत i'वां सबसे छोटा तत्व ढूंढें
- रैंक (x) - ट्री में तत्व x की रैंक ढूंढें, अर्थात ट्री के तत्वों की क्रमबद्ध सूची में इसका सूचकांक
दोनों संचालन O(log n) में सबसे खराब और औसत स्थिति किए जा सकते हैं जब एक सेल्फ-बैलेंसिंग ट्री का उपयोग आधार डेटा संरचना के रूप में किया जाता है।
कते हैं जब एक सेल्फ-बैलेंसिंग ट्री का उपयोग आधार डेटा संरचना के रूप में किया जाता है।
संवर्धित खोज वृक्ष कार्यान्वयन
एक नियमित खोज ट्री को ऑर्डर स्टेटिस्टिक ट्री में बदलने के लिए, ट्री के नोड्स को एक अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है, जो उस नोड पर निहित उपट्री का आकार है (यानी, इसके नीचे नोड्स की संख्या)। ट्री को संशोधित करने वाले सभी ऑपरेशनों को लूप अपरिवर्तनीय को संरक्षित करने के लिए इस जानकारी को समायोजित करना होगा
आकार[x] = आकार[बाएं[x + आकार[दाएं[x + 1
कहाँ size[nil] = 0 परिभाषा से। फिर चयन को इस प्रकार कार्यान्वित किया जा सकता है[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.
