स्कैप्गोट ट्री: Difference between revisions
(Created page with "{{Short description|Type of balanced binary search tree}} {{multiple issues| {{more footnotes|date=March 2014}} {{refimprove|date=March 2014}} }} {{Infobox data structure-amor...") |
No edit summary |
||
(8 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Type of balanced binary search tree}} | {{Short description|Type of balanced binary search tree}} | ||
{{Infobox data structure-amortized | {{Infobox data structure-amortized | ||
|name= | |name=स्कैप्गोट ट्री | ||
|type=tree | |type=tree | ||
|invented_year=1989 | |invented_year=1989 | ||
Line 18: | Line 14: | ||
}} | }} | ||
[[कंप्यूटर विज्ञान]] में, | [[कंप्यूटर विज्ञान]] में, '''स्कैप्गोट ट्री''' एक [[स्व-संतुलन द्विआधारी खोज वृक्ष|सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] है, जिसका आविष्कार 1989 में अर्ने एंडरसन<ref name=anderson1>{{Cite conference |title=सरल संतुलन मानदंड का उपयोग करके आंशिक पुनर्निर्माण में सुधार करना|url=http://user.it.uu.se/~arnea/abs/partb.html |citeseerx=10.1.1.138.4859 |journal=Journal of Algorithms |first=Arne |last=Andersson |conference=Proc. Workshop on Algorithms and Data Structures |pages=393–402 |year=1989 |publisher=Springer-Verlag |doi=10.1007/3-540-51542-9_33}}</ref>द्वारा और फिर 1993 में [[ईगल कहानी|इगल गैल्परिन]] और रोनाल्ड एल. रिवेस्ट द्वारा किया गया था।<ref name=galperin_rivest>{{Cite conference |first1=Igal |last1=Galperin |first2=Ronald L. |last2=Rivest |authorlink2=Ronald L. Rivest |title=बलि का बकरा पेड़|journal=Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |pages=165–174 |year=1993 |url=http://people.csail.mit.edu/rivest/pubs/GR93.pdf |citeseerx=10.1.1.309.9376 |isbn=0-89871-313-7 |publisher=[[Society for Industrial and Applied Mathematics]] |location=Philadelphia}}</ref> यह निकृष्टतम् <math>{\color{Blue}O(\log n)}</math> परीक्षण समय (प्रविष्टियों की संख्या के रूप में आर के साथ) और <math>n</math> प्रविष्टियों की संख्या के रूप में) और <math>O(\log n)</math> [[परिशोधन विश्लेषण]] और विलोपन समय प्रदान करता है। | ||
अधिकांश अन्य | अधिकांश अन्य सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री के विपरीत, जो निकृष्टतम् <math>O(\log n)</math> भी प्रदान करते हैं परीक्षण समय, नियमित [[बाइनरी सर्च ट्री]] की तुलना में स्कैप्गोट ट्री में कोई अतिरिक्त प्रति-नोड मेमोरी उपरि नहीं होता है: कीय और मान के अतिरिक्त, एक नोड चाइल्ड नोड्स में केवल दो पॉइंटर्स संग्रहीत करता है। इससे स्कैप्गोट ट्री लागू करना आसान हो जाता है और [[डेटा संरचना संरेखण]] के कारण, नोड उपरि को एक तिहाई तक कम किया जा सकता है। | ||
अधिकांश संतुलित | अधिकांश संतुलित ट्री एल्गोरिदम द्वारा उपयोग किए जाने वाले छोटे वृद्धिशील पुनर्संतुलन संचालन के अतिरिक्त, स्कैप्गोट ट्री शायद ही कभी लेकिन महंगा रूप से स्कैप्गोट ट्री चुनते हैं और "स्कैप्गोट" में निहित सबट्री को पूर्ण बाइनरी ट्री में पूरी तरह से पुनर्निर्माण करते हैं। इस प्रकार, स्कैप्गोट ट्री <math>O(n)</math> निकृष्टतम् में अद्यतन प्रदर्शन है। | ||
==सिद्धांत== | ==सिद्धांत== | ||
बाइनरी सर्च ट्री को भारित-संतुलित कहा जाता है यदि आधे नोड्स मूल के बाईं ओर और आधे दाईं ओर होंते हैं। α-भारित-संतुलित नोड को विश्रांत भारित संतुलन मानदंड को पूरा करने के रूप में परिभाषित किया गया है: | |||
size(left) ≤ α*size(node) | |||
size(right) ≤ α*size(node) | |||
जहां माप को पुनरावर्ती रूप से परिभाषित किया जा सकता है: | |||
जहां | '''function''' size(node) '''is''' | ||
'''if''' node = nil '''then''' | |||
'''return''' 0 | |||
'''else | |||
return''' size(node->left) + size(node->right) + 1 | |||
'''end if | |||
end function''' | |||
यहां तक कि | यहां तक कि पतित ट्री (लिंक्ड सूची) भी इस शर्त को संतुष्ट करता है यदि α=1, जबकि α=0.5 केवल बाइनरी ट्री के प्रकार से बराबर होगा। | ||
बाइनरी सर्च ट्री जो α-भारित-संतुलित है, उसे '''α-ऊंचाई-संतुलित''' भी होना चाहिए, अर्थात | |||
height(tree) ≤ floor(log1/α(size(tree))) | |||
विरोधाभास द्वारा, | विरोधाभास द्वारा, ट्री जो α-ऊंचाई-संतुलित नहीं है, वह α-भारित-संतुलित नहीं है। | ||
स्कैप्गोट ट्री हर समय α-भारित-संतुलन बनाए रखने की गारंटी नहीं देता है, लेकिन इसमें हमेशा α-ऊंचाई-संतुलित होता है | |||
height(scapegoat tree) ≤ floor(log1/α(size(tree))) + 1. | |||
इस ऊंचाई संतुलन की स्थिति के उल्लंघन का पता प्रविष्टि के समय लगाया जा सकता है, और इसका अर्थ यह है कि | इस ऊंचाई संतुलन की स्थिति के उल्लंघन का पता प्रविष्टि के समय लगाया जा सकता है, और इसका अर्थ यह है कि भारित संतुलन की स्थिति का उल्लंघन अवश्य होना चाहिए। | ||
यह | यह स्कैप्गोट ट्री को रेड–ब्लैक ट्री के समान बनाता है, क्योंकि उन दोनों की ऊंचाई पर प्रतिबंध है। हालाँकि वे यह निर्धारित करने के अपने कार्यान्वयन में बहुत भिन्न हैं कि घुमाव (या स्कैप्गोट ट्री के मामले में, पुनर्संतुलन) जहाँ होते हैं। जबकि रेड–ब्लैक ट्री स्थान निर्धारित करने के लिए प्रत्येक नोड में अतिरिक्त 'रंग' जानकारी संग्रहीत करते हैं, स्कैप्गोट ट्री, '''स्कैप्गोट ट्री''' ढूंढते हैं जो पुनर्संतुलन संचालन करने के लिए α-भारित-संतुलित नहीं होता है। यह [[एवीएल पेड़|एवीएल ट्री]] के समान है, जिसमें वास्तविक घुमाव नोड्स के 'संतुलन' पर निर्भर करते हैं, लेकिन संतुलन निर्धारित करने के साधन बहुत भिन्न होते हैं। चूंकि एवीएल ट्री प्रत्येक प्रविष्टि/विलोपन पर शेष मान की जांच करते हैं, इसलिए इसे सामान्यतः प्रत्येक नोड में संग्रहीत किया जाता है; स्कैप्गोट ट्री केवल आवश्यकतानुसार ही इसकी गणना करने में सक्षम होते हैं, जो केवल तब होता है जब स्कैप्गोट ट्री प्रतिलब्धि की आवश्यकता होती है। | ||
अधिकांश अन्य स्व-संतुलन खोज | अधिकांश अन्य स्व-संतुलन खोज ट्री के विपरीत, स्कैप्गोट ट्री अपने संतुलन के मामले में पूरी तरह से लचीले होते हैं। वे किसी भी α का समर्थन करते हैं जैसे कि 0.5 < α < 1। उच्च α मान के परिणामस्वरूप कम संतुलन होता है, जिससे सम्मिलन तेज हो जाता है लेकिन परीक्षण और विलोपन धीमा हो जाता है, और कम α के लिए इसका विपरीत होता है। इसलिए व्यावहारिक अनुप्रयोगों में, इन क्रियाओं को कितनी बार किया जाना चाहिए, इसके आधार पर एक α चुना जा सकता है। | ||
==संचालन== | ==संचालन== | ||
=== | ===परीक्षण=== | ||
परीक्षण को मानक बाइनरी सर्च ट्री से संशोधित नहीं किया गया है, और इसकी निकृष्टतम् <math>O(\log n)</math> है, यह उन ट्री के विपरीत है जिनकी निकृष्टतम् <math>O(n)</math> होती है। अन्य सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में कम नोड मेमोरी उपरि संदर्भ और कैशिंग की स्थानीयता में और सुधार कर सकता है। | |||
===सम्मिलन=== | ===सम्मिलन=== | ||
सम्मिलन को बाइनरी सर्च ट्री | सम्मिलन को बाइनरी सर्च ट्री के समान मूल विचारों के साथ, हालाँकि कुछ महत्वपूर्ण परिवर्तनों के साथ कार्यान्वित किया जाता है। | ||
सम्मिलन बिंदु ढूंढते समय, नए नोड की गहराई भी दर्ज की जानी चाहिए। इसे | सम्मिलन बिंदु ढूंढते समय, नए नोड की गहराई भी दर्ज की जानी चाहिए। इसे साधारण काउंटर के माध्यम से कार्यान्वित किया जाता है जो परीक्षण के प्रत्येक पुनरावृत्ति के दौरान बढ़ता है, मूल और सम्मिलित नोड के बीच किनारों की संख्या को प्रभावी ढंग से गिनता है। यदि यह नोड α-ऊंचाई-संतुलन गुण (ऊपर परिभाषित) का उल्लंघन करता है, तो पुनर्संतुलन की आवश्यकता होती है। | ||
पुनर्संतुलन के लिए, | पुनर्संतुलन के लिए, '''स्कैप्गोट''' पर आधारित संपूर्ण सबट्री को संतुलन संचालन से गुजरना पड़ता है। स्कैप्गोट को सम्मिलित नोड के पूर्वज के रूप में परिभाषित किया गया है जो α-भारित-संतुलित नहीं है। ऐसा कम से कम एक पूर्वज हमेशा रहेगा। उनमें से किसी को भी पुनर्संतुलित करने से α-ऊंचाई-संतुलित गुण बहाल हो जाएगी। | ||
स्कैप्गोट ट्री प्रतिलब्धि का एक तरीका है, नए नोड से वापस मूल तक उन्नति और पहले नोड का चयन करना जो α-भारित-संतुलित नहीं है। | |||
मूल तक वापस उन्नति <math>O(\log n)</math> की आवश्यकता है भंडारण स्थान, सामान्यतः स्टैक, या पैरेंट पॉइंटर्स पर आवंटित किया जाता है। वास्तव में इससे बचा जा सकता है, जब आप नीचे जाते समय प्रत्येक बच्चे को उसके माता-पिता की ओर इशारा करते हैं, और वापस ऊपर जाते समय मरम्मत करते हैं। | |||
यह निर्धारित करने के लिए कि क्या | यह निर्धारित करने के लिए कि क्या संभावित नोड व्यवहार्य स्कैप्गोट ट्री है, हमें इसकी α-भारित-संतुलित गुण की जांच करने की आवश्यकता है। ऐसा करने के लिए हम परिभाषा पर वापस जा सकते हैं: | ||
size(left) ≤ α*size(node) | |||
size(right) ≤ α*size(node) | |||
हालाँकि, यह महसूस करके | हालाँकि, यह महसूस करके बड़ा अनुकूलन किया जा सकता है कि हम पहले से ही तीन में से दो आकारों को जानते हैं, केवल तीसरे की गणना करना बाकी है। | ||
इसे प्रदर्शित करने के लिए निम्नलिखित उदाहरण पर विचार करें। यह मानते हुए कि हम | इसे प्रदर्शित करने के लिए निम्नलिखित उदाहरण पर विचार करें। यह मानते हुए कि हम मूल तक वापस चढ़ रहे हैं: | ||
size(parent) = size(node) + size(sibling) + 1 | |||
परंतु जैसे: | परंतु जैसे: | ||
size(inserted node) = 1. | |||
मामले को निम्न स्तर तक महत्वहीन बना दिया गया है: | मामले को निम्न स्तर तक महत्वहीन बना दिया गया है: | ||
size[x+1] = size[x] + size(sibling) + 1 | |||
जहां x = यह नोड, x + 1 = मूल और | जहां x = यह नोड, x + 1 = मूल और माप (भाई-बहन) ही एकमात्र फ़ंक्शन कॉल है जो वास्तव में आवश्यक है। | ||
एक बार जब | एक बार जब स्कैप्गोट ट्री मिल जाता है, तो स्कैप्गोट में निहित सबट्री को पूरी तरह से संतुलित करने के लिए फिर से बनाया जाता है।यह सबट्री के नोड्स को क्रमबद्ध क्रम में उनके मान को खोजने के लिए उप-ट्री के नोड्स को पार करके और उप-ट्री के मूल के रूप में मध्यिका को पुनरावर्ती रूप से चुनकर <math>O(n)</math> समय में किया जा सकता है। | ||
जैसा कि पुनर्संतुलन संचालन में लगता है <math>O(n)</math> समय (उपट्री के नोड्स की संख्या पर निर्भर), सम्मिलन | जैसा कि पुनर्संतुलन संचालन में लगता है <math>O(n)</math> समय (उपट्री के नोड्स की संख्या पर निर्भर), सम्मिलन में <math>O(n)</math> समय प्रदर्शन निकृष्टतम् है। हालाँकि, क्योंकि ये निकृष्टतम् फैली हुई है, सम्मिलन में <math>O(\log n)</math> परिशोधित समय लगता है। | ||
====प्रविष्टि की लागत के लिए प्रमाण का स्केच==== | ====प्रविष्टि की लागत के लिए प्रमाण का स्केच==== | ||
किसी नोड के असंतुलन को परिभाषित करें v इसके बाएं नोड और दाएं नोड के बीच | किसी नोड के असंतुलन को परिभाषित करें ''v'' इसके बाएं नोड और दाएं नोड के बीच माप में अंतर का पूर्ण मान शून्य से 1, या 0, जो भी अधिक हो। दूसरे शब्दों में: | ||
<math>I(v) = \operatorname{max}(|\operatorname{left}(v) - \operatorname{right}(v)| - 1, 0) </math> | <math>I(v) = \operatorname{max}(|\operatorname{left}(v) - \operatorname{right}(v)| - 1, 0) </math> | ||
'लेम्मा:' सबट्री के पुनर्निर्माण से ठीक पहले v, <br /> पर | ''v, I(v) = 0'' पर निहित सबट्री के पुनर्निर्माण के तुरंत बाद। | ||
<math>I(v) \in \Omega (|v|) </math><br/> | |||
(<math>\Omega </math> [[बिग ओमेगा संकेतन]] है।) | '''लेम्मा:''' सबट्री के पुनर्निर्माण से ठीक पहले ''v'', <br /> पर मूल किया गया | ||
<math>I(v) \in \Omega (|v|) </math><br />(<math>\Omega </math> [[बिग ओमेगा संकेतन]] है।) | |||
लेम्मा का प्रमाण: | लेम्मा का प्रमाण: | ||
मान लीजिये <math>v_0</math> पुनर्निर्माण के तुरंत बाद क सबट्री की मूल बनें। <math>h(v_0) = \log(|v_0| + 1) </math>, यदि वहाँ <math>\Omega (|v_0|)</math> पतित सम्मिलन (अर्थात, जहां प्रत्येक सम्मिलित नोड ऊंचाई 1 से बढ़ाता है), फिर <br /><math>I(v) \in \Omega (|v_0|) </math>,<br/><math>h(v) = h(v_0) + \Omega (|v_0|) </math> और<br/><math>\log(|v|) \le \log(|v_0| + 1) + 1 </math>. | |||
<math>I(v) \in \Omega (|v_0|) </math>,<br/> | |||
<math>h(v) = h(v_0) + \Omega (|v_0|) </math> और<br/> | |||
<math>\log(|v|) \le \log(|v_0| + 1) + 1 </math>. | |||
तब से <math>I(v) \in \Omega (|v|)</math> पुनर्निर्माण से पहले, वहाँ | तब से <math>I(v) \in \Omega (|v|)</math> पुनर्निर्माण से पहले, वहाँ <math>\Omega (|v|)</math> पर निहित सबट्री में सम्मिलन <math>v</math> थे जिसके परिणामस्वरूप पुनर्निर्माण नहीं हुआ। इनमें से प्रत्येक सम्मिलन <math>O(\log n)</math> समय में किया जा सकता है। अंतिम सम्मिलन जो पुनर्निर्माण लागत <math>O(|v|)</math> का कारण बनता है, [[समग्र विश्लेषण]] का उपयोग करने से यह स्पष्ट हो जाता है कि किसी प्रविष्टि की परिशोधित लागत <math>O(\log n)</math> है : | ||
<math>{\Omega (|v|) O(\log n) + O(|v|) \over \Omega (|v|)} = O(\log n) </math> | <math>{\Omega (|v|) O(\log n) + O(|v|) \over \Omega (|v|)} = O(\log n) </math> | ||
===विलोपन=== | ===विलोपन=== | ||
स्कैप्गोट ट्री इस मायने में असामान्य है कि सम्मिलन की तुलना में हटाना आसान है। विलोपन को सक्षम करने के लिए, स्कैप्गोट ट्री को ट्री डेटा संरचना के साथ अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है। यह गुण, जिसे हम मैक्सनोडकाउंट कहेंगे, केवल उच्चतम प्राप्त नोडकाउंट का प्रतिनिधित्व करती है। जब भी पूरा ट्री पुनर्संतुलित होता है तो इसे नोडकाउंट पर सेट किया जाता है, और सम्मिलन के बाद अधिकतम (मैक्सनोडकाउंट, नोडकाउंट) पर सेट किया जाता है। | |||
विलोपन करने के लिए, हम बस नोड को हटा देते हैं जैसे आप | विलोपन करने के लिए, हम बस नोड को हटा देते हैं जैसे आप साधारण बाइनरी सर्च ट्री में करते हैं, लेकिन यदि | ||
NodeCount ≤ α*MaxNodeCount | |||
फिर हम पूरे | फिर हम पूरे ट्री को मूल के बारे में पुनर्संतुलित करते हैं, मैक्सनोडकाउंट को नोडकाउंट पर सेट करना याद रखते हैं। | ||
यह विलोपन को | यह विलोपन को <math>O(n)</math> समय निकृष्टतम् वाला प्रदर्शन देता है, जबकि परिशोधित समय <math>O(\log n)</math> है | ||
==== | ====विलोपन की लागत के लिए प्रमाण का स्केच==== | ||
मान लीजिए कि | मान लीजिए कि स्कैप्गोट ट्री के पास <math>n</math> तत्व है और अभी इसका पुनर्निर्माण किया गया है (दूसरे शब्दों में, यह पूर्ण बाइनरी ट्री है)। अधिक से अधिक <math>n/2 - 1</math> ट्री को फिर से बनाने से पहले हटाया जा सकता है। इनमें से प्रत्येक विलोपन <math>O(\log n)</math> समय (तत्व को खोजने और उसे हटाए गए के रूप में चिह्नित करने के लिए समय की मात्रा) लेता है । <math>n/2</math> h> विलोपन के कारण ट्री का पुनर्निर्माण होता है और <math>O(\log n) + O(n)</math> (या केवल <math>O(n)</math>) समय लेता है। समग्र विश्लेषण का उपयोग करने से यह स्पष्ट हो जाता है कि विलोपन की परिशोधित लागत <math>O(\log n)</math> है : | ||
<math> | <math> | ||
Line 127: | Line 118: | ||
स्कैपगोट ट्री नाम '' [...] सामान्य ज्ञान पर आधारित है कि, जब कुछ गलत होता है, तो सबसे पहले लोग जो करते हैं वह किसी को दोष देने के लिए ( | '''<big>व्युत्पत्ति</big>''' | ||
'''स्कैपगोट ट्री''' नाम '' "[...]" सामान्य ज्ञान पर आधारित है कि, जब कुछ गलत होता है, तो सबसे पहले लोग जो करते हैं वह किसी को दोष देने के लिए (स्कैप्गोट ट्री) ढूंढना होता है। ''<ref name="opendatastructures">{{cite book |chapter-url=http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html|title=डेटा संरचनाएँ खोलें (छद्म कोड में)|chapter=Chapter 8 - Scapegoat Trees |url=http://opendatastructures.org/versions/edition-0.1g/ods-python/ods-python-html.html |edition=0.1G β |first=Pat |last=Morin|authorlink= Pat Morin |accessdate=2017-09-16}}</ref> [[बाइबिल]] में, [[बलि का बकरा|स्कैप्गोट ट्री]] एक ऐसा जानवर है जिस पर अनुष्ठानिक रूप से दूसरों के पापों का बोझ डाला जाता है और फिर उसे भगा दिया जाता है। | |||
==यह भी देखें== | ==यह भी देखें== | ||
* | * सप्लाय ट्री | ||
* [[वृक्ष डेटा संरचना]] | * [[वृक्ष डेटा संरचना|ट्री डेटा संरचना]] | ||
* | * ट्री परिभ्रमण | ||
*एवीएल | *एवीएल ट्री | ||
*[[बी-वृक्ष]] | *[[बी-वृक्ष|बी-ट्री]] | ||
* [[ टी पेड़ ]] | * [[ टी पेड़ | टी- ट्री]] | ||
==संदर्भ== | ==संदर्भ== | ||
{{Reflist}} | {{Reflist}} | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
*{{cite thesis |url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-700.pdf |title=On Consulting a Set of Experts and Searching |type=Ph.D. thesis |first=Igal |last=Galpern |publisher=[[Massachusetts Institute of Technology|MIT]] |date=September 1996}} | *{{cite thesis |url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-700.pdf |title=On Consulting a Set of Experts and Searching |type=Ph.D. thesis |first=Igal |last=Galpern |publisher=[[Massachusetts Institute of Technology|MIT]] |date=September 1996}} | ||
*{{cite book |chapter-url=http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html |title=Open Data Structures (in pseudocode) |chapter=Chapter 8 - Scapegoat Trees |url=http://opendatastructures.org/versions/edition-0.1g/ods-python/ods-python-html.html |edition=0.1G β |first=Pat |last=Morin |accessdate=2017-09-16}} | *{{cite book |chapter-url=http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html |title=Open Data Structures (in pseudocode) |chapter=Chapter 8 - Scapegoat Trees |url=http://opendatastructures.org/versions/edition-0.1g/ods-python/ods-python-html.html |edition=0.1G β |first=Pat |last=Morin |accessdate=2017-09-16}} | ||
{{DEFAULTSORT:Scapegoat Tree}} | |||
{{DEFAULTSORT:Scapegoat Tree}} | |||
[[Category: Machine Translated Page]] | [[Category:Created On 10/07/2023|Scapegoat Tree]] | ||
[[Category: | [[Category:Lua-based templates|Scapegoat Tree]] | ||
[[Category:Machine Translated Page|Scapegoat Tree]] | |||
[[Category:Pages with script errors|Scapegoat Tree]] | |||
[[Category:Templates Vigyan Ready|Scapegoat Tree]] | |||
[[Category:Templates that add a tracking category|Scapegoat Tree]] | |||
[[Category:Templates that generate short descriptions|Scapegoat Tree]] | |||
[[Category:Templates using TemplateData|Scapegoat Tree]] | |||
[[Category:परिशोधित डेटा संरचनाएँ|Scapegoat Tree]] | |||
[[Category:पेड़ खोजें|Scapegoat Tree]] | |||
[[Category:बाइनरी पेड़|Scapegoat Tree]] |
Latest revision as of 10:56, 26 July 2023
स्कैप्गोट ट्री | |||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | tree | ||||||||||||||||||||||||||||
Invented | 1989 | ||||||||||||||||||||||||||||
Invented by | Arne Andersson, Igal Galperin, Ronald L. Rivest | ||||||||||||||||||||||||||||
Complexities in big O notation | |||||||||||||||||||||||||||||
|
कंप्यूटर विज्ञान में, स्कैप्गोट ट्री एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री है, जिसका आविष्कार 1989 में अर्ने एंडरसन[2]द्वारा और फिर 1993 में इगल गैल्परिन और रोनाल्ड एल. रिवेस्ट द्वारा किया गया था।[1] यह निकृष्टतम् परीक्षण समय (प्रविष्टियों की संख्या के रूप में आर के साथ) और प्रविष्टियों की संख्या के रूप में) और परिशोधन विश्लेषण और विलोपन समय प्रदान करता है।
अधिकांश अन्य सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री के विपरीत, जो निकृष्टतम् भी प्रदान करते हैं परीक्षण समय, नियमित बाइनरी सर्च ट्री की तुलना में स्कैप्गोट ट्री में कोई अतिरिक्त प्रति-नोड मेमोरी उपरि नहीं होता है: कीय और मान के अतिरिक्त, एक नोड चाइल्ड नोड्स में केवल दो पॉइंटर्स संग्रहीत करता है। इससे स्कैप्गोट ट्री लागू करना आसान हो जाता है और डेटा संरचना संरेखण के कारण, नोड उपरि को एक तिहाई तक कम किया जा सकता है।
अधिकांश संतुलित ट्री एल्गोरिदम द्वारा उपयोग किए जाने वाले छोटे वृद्धिशील पुनर्संतुलन संचालन के अतिरिक्त, स्कैप्गोट ट्री शायद ही कभी लेकिन महंगा रूप से स्कैप्गोट ट्री चुनते हैं और "स्कैप्गोट" में निहित सबट्री को पूर्ण बाइनरी ट्री में पूरी तरह से पुनर्निर्माण करते हैं। इस प्रकार, स्कैप्गोट ट्री निकृष्टतम् में अद्यतन प्रदर्शन है।
सिद्धांत
बाइनरी सर्च ट्री को भारित-संतुलित कहा जाता है यदि आधे नोड्स मूल के बाईं ओर और आधे दाईं ओर होंते हैं। α-भारित-संतुलित नोड को विश्रांत भारित संतुलन मानदंड को पूरा करने के रूप में परिभाषित किया गया है:
size(left) ≤ α*size(node) size(right) ≤ α*size(node)
जहां माप को पुनरावर्ती रूप से परिभाषित किया जा सकता है:
function size(node) is if node = nil then return 0 else return size(node->left) + size(node->right) + 1 end if end function
यहां तक कि पतित ट्री (लिंक्ड सूची) भी इस शर्त को संतुष्ट करता है यदि α=1, जबकि α=0.5 केवल बाइनरी ट्री के प्रकार से बराबर होगा।
बाइनरी सर्च ट्री जो α-भारित-संतुलित है, उसे α-ऊंचाई-संतुलित भी होना चाहिए, अर्थात
height(tree) ≤ floor(log1/α(size(tree)))
विरोधाभास द्वारा, ट्री जो α-ऊंचाई-संतुलित नहीं है, वह α-भारित-संतुलित नहीं है।
स्कैप्गोट ट्री हर समय α-भारित-संतुलन बनाए रखने की गारंटी नहीं देता है, लेकिन इसमें हमेशा α-ऊंचाई-संतुलित होता है
height(scapegoat tree) ≤ floor(log1/α(size(tree))) + 1.
इस ऊंचाई संतुलन की स्थिति के उल्लंघन का पता प्रविष्टि के समय लगाया जा सकता है, और इसका अर्थ यह है कि भारित संतुलन की स्थिति का उल्लंघन अवश्य होना चाहिए।
यह स्कैप्गोट ट्री को रेड–ब्लैक ट्री के समान बनाता है, क्योंकि उन दोनों की ऊंचाई पर प्रतिबंध है। हालाँकि वे यह निर्धारित करने के अपने कार्यान्वयन में बहुत भिन्न हैं कि घुमाव (या स्कैप्गोट ट्री के मामले में, पुनर्संतुलन) जहाँ होते हैं। जबकि रेड–ब्लैक ट्री स्थान निर्धारित करने के लिए प्रत्येक नोड में अतिरिक्त 'रंग' जानकारी संग्रहीत करते हैं, स्कैप्गोट ट्री, स्कैप्गोट ट्री ढूंढते हैं जो पुनर्संतुलन संचालन करने के लिए α-भारित-संतुलित नहीं होता है। यह एवीएल ट्री के समान है, जिसमें वास्तविक घुमाव नोड्स के 'संतुलन' पर निर्भर करते हैं, लेकिन संतुलन निर्धारित करने के साधन बहुत भिन्न होते हैं। चूंकि एवीएल ट्री प्रत्येक प्रविष्टि/विलोपन पर शेष मान की जांच करते हैं, इसलिए इसे सामान्यतः प्रत्येक नोड में संग्रहीत किया जाता है; स्कैप्गोट ट्री केवल आवश्यकतानुसार ही इसकी गणना करने में सक्षम होते हैं, जो केवल तब होता है जब स्कैप्गोट ट्री प्रतिलब्धि की आवश्यकता होती है।
अधिकांश अन्य स्व-संतुलन खोज ट्री के विपरीत, स्कैप्गोट ट्री अपने संतुलन के मामले में पूरी तरह से लचीले होते हैं। वे किसी भी α का समर्थन करते हैं जैसे कि 0.5 < α < 1। उच्च α मान के परिणामस्वरूप कम संतुलन होता है, जिससे सम्मिलन तेज हो जाता है लेकिन परीक्षण और विलोपन धीमा हो जाता है, और कम α के लिए इसका विपरीत होता है। इसलिए व्यावहारिक अनुप्रयोगों में, इन क्रियाओं को कितनी बार किया जाना चाहिए, इसके आधार पर एक α चुना जा सकता है।
संचालन
परीक्षण
परीक्षण को मानक बाइनरी सर्च ट्री से संशोधित नहीं किया गया है, और इसकी निकृष्टतम् है, यह उन ट्री के विपरीत है जिनकी निकृष्टतम् होती है। अन्य सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में कम नोड मेमोरी उपरि संदर्भ और कैशिंग की स्थानीयता में और सुधार कर सकता है।
सम्मिलन
सम्मिलन को बाइनरी सर्च ट्री के समान मूल विचारों के साथ, हालाँकि कुछ महत्वपूर्ण परिवर्तनों के साथ कार्यान्वित किया जाता है।
सम्मिलन बिंदु ढूंढते समय, नए नोड की गहराई भी दर्ज की जानी चाहिए। इसे साधारण काउंटर के माध्यम से कार्यान्वित किया जाता है जो परीक्षण के प्रत्येक पुनरावृत्ति के दौरान बढ़ता है, मूल और सम्मिलित नोड के बीच किनारों की संख्या को प्रभावी ढंग से गिनता है। यदि यह नोड α-ऊंचाई-संतुलन गुण (ऊपर परिभाषित) का उल्लंघन करता है, तो पुनर्संतुलन की आवश्यकता होती है।
पुनर्संतुलन के लिए, स्कैप्गोट पर आधारित संपूर्ण सबट्री को संतुलन संचालन से गुजरना पड़ता है। स्कैप्गोट को सम्मिलित नोड के पूर्वज के रूप में परिभाषित किया गया है जो α-भारित-संतुलित नहीं है। ऐसा कम से कम एक पूर्वज हमेशा रहेगा। उनमें से किसी को भी पुनर्संतुलित करने से α-ऊंचाई-संतुलित गुण बहाल हो जाएगी।
स्कैप्गोट ट्री प्रतिलब्धि का एक तरीका है, नए नोड से वापस मूल तक उन्नति और पहले नोड का चयन करना जो α-भारित-संतुलित नहीं है।
मूल तक वापस उन्नति की आवश्यकता है भंडारण स्थान, सामान्यतः स्टैक, या पैरेंट पॉइंटर्स पर आवंटित किया जाता है। वास्तव में इससे बचा जा सकता है, जब आप नीचे जाते समय प्रत्येक बच्चे को उसके माता-पिता की ओर इशारा करते हैं, और वापस ऊपर जाते समय मरम्मत करते हैं।
यह निर्धारित करने के लिए कि क्या संभावित नोड व्यवहार्य स्कैप्गोट ट्री है, हमें इसकी α-भारित-संतुलित गुण की जांच करने की आवश्यकता है। ऐसा करने के लिए हम परिभाषा पर वापस जा सकते हैं:
size(left) ≤ α*size(node) size(right) ≤ α*size(node)
हालाँकि, यह महसूस करके बड़ा अनुकूलन किया जा सकता है कि हम पहले से ही तीन में से दो आकारों को जानते हैं, केवल तीसरे की गणना करना बाकी है।
इसे प्रदर्शित करने के लिए निम्नलिखित उदाहरण पर विचार करें। यह मानते हुए कि हम मूल तक वापस चढ़ रहे हैं:
size(parent) = size(node) + size(sibling) + 1
परंतु जैसे:
size(inserted node) = 1.
मामले को निम्न स्तर तक महत्वहीन बना दिया गया है:
size[x+1] = size[x] + size(sibling) + 1
जहां x = यह नोड, x + 1 = मूल और माप (भाई-बहन) ही एकमात्र फ़ंक्शन कॉल है जो वास्तव में आवश्यक है।
एक बार जब स्कैप्गोट ट्री मिल जाता है, तो स्कैप्गोट में निहित सबट्री को पूरी तरह से संतुलित करने के लिए फिर से बनाया जाता है।यह सबट्री के नोड्स को क्रमबद्ध क्रम में उनके मान को खोजने के लिए उप-ट्री के नोड्स को पार करके और उप-ट्री के मूल के रूप में मध्यिका को पुनरावर्ती रूप से चुनकर समय में किया जा सकता है।
जैसा कि पुनर्संतुलन संचालन में लगता है समय (उपट्री के नोड्स की संख्या पर निर्भर), सम्मिलन में समय प्रदर्शन निकृष्टतम् है। हालाँकि, क्योंकि ये निकृष्टतम् फैली हुई है, सम्मिलन में परिशोधित समय लगता है।
प्रविष्टि की लागत के लिए प्रमाण का स्केच
किसी नोड के असंतुलन को परिभाषित करें v इसके बाएं नोड और दाएं नोड के बीच माप में अंतर का पूर्ण मान शून्य से 1, या 0, जो भी अधिक हो। दूसरे शब्दों में:
v, I(v) = 0 पर निहित सबट्री के पुनर्निर्माण के तुरंत बाद।
लेम्मा: सबट्री के पुनर्निर्माण से ठीक पहले v,
पर मूल किया गया
( बिग ओमेगा संकेतन है।)
लेम्मा का प्रमाण:
मान लीजिये पुनर्निर्माण के तुरंत बाद क सबट्री की मूल बनें। , यदि वहाँ पतित सम्मिलन (अर्थात, जहां प्रत्येक सम्मिलित नोड ऊंचाई 1 से बढ़ाता है), फिर
,
और
.
तब से पुनर्निर्माण से पहले, वहाँ पर निहित सबट्री में सम्मिलन थे जिसके परिणामस्वरूप पुनर्निर्माण नहीं हुआ। इनमें से प्रत्येक सम्मिलन समय में किया जा सकता है। अंतिम सम्मिलन जो पुनर्निर्माण लागत का कारण बनता है, समग्र विश्लेषण का उपयोग करने से यह स्पष्ट हो जाता है कि किसी प्रविष्टि की परिशोधित लागत है :
विलोपन
स्कैप्गोट ट्री इस मायने में असामान्य है कि सम्मिलन की तुलना में हटाना आसान है। विलोपन को सक्षम करने के लिए, स्कैप्गोट ट्री को ट्री डेटा संरचना के साथ अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है। यह गुण, जिसे हम मैक्सनोडकाउंट कहेंगे, केवल उच्चतम प्राप्त नोडकाउंट का प्रतिनिधित्व करती है। जब भी पूरा ट्री पुनर्संतुलित होता है तो इसे नोडकाउंट पर सेट किया जाता है, और सम्मिलन के बाद अधिकतम (मैक्सनोडकाउंट, नोडकाउंट) पर सेट किया जाता है।
विलोपन करने के लिए, हम बस नोड को हटा देते हैं जैसे आप साधारण बाइनरी सर्च ट्री में करते हैं, लेकिन यदि
NodeCount ≤ α*MaxNodeCount
फिर हम पूरे ट्री को मूल के बारे में पुनर्संतुलित करते हैं, मैक्सनोडकाउंट को नोडकाउंट पर सेट करना याद रखते हैं।
यह विलोपन को समय निकृष्टतम् वाला प्रदर्शन देता है, जबकि परिशोधित समय है
विलोपन की लागत के लिए प्रमाण का स्केच
मान लीजिए कि स्कैप्गोट ट्री के पास तत्व है और अभी इसका पुनर्निर्माण किया गया है (दूसरे शब्दों में, यह पूर्ण बाइनरी ट्री है)। अधिक से अधिक ट्री को फिर से बनाने से पहले हटाया जा सकता है। इनमें से प्रत्येक विलोपन समय (तत्व को खोजने और उसे हटाए गए के रूप में चिह्नित करने के लिए समय की मात्रा) लेता है । h> विलोपन के कारण ट्री का पुनर्निर्माण होता है और (या केवल ) समय लेता है। समग्र विश्लेषण का उपयोग करने से यह स्पष्ट हो जाता है कि विलोपन की परिशोधित लागत है :
व्युत्पत्ति
स्कैपगोट ट्री नाम "[...]" सामान्य ज्ञान पर आधारित है कि, जब कुछ गलत होता है, तो सबसे पहले लोग जो करते हैं वह किसी को दोष देने के लिए (स्कैप्गोट ट्री) ढूंढना होता है। [3] बाइबिल में, स्कैप्गोट ट्री एक ऐसा जानवर है जिस पर अनुष्ठानिक रूप से दूसरों के पापों का बोझ डाला जाता है और फिर उसे भगा दिया जाता है।
यह भी देखें
- सप्लाय ट्री
- ट्री डेटा संरचना
- ट्री परिभ्रमण
- एवीएल ट्री
- बी-ट्री
- टी- ट्री
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Galperin, Igal; Rivest, Ronald L. (1993). बलि का बकरा पेड़ (PDF). Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics. pp. 165–174. CiteSeerX 10.1.1.309.9376. ISBN 0-89871-313-7.
- ↑ Andersson, Arne (1989). सरल संतुलन मानदंड का उपयोग करके आंशिक पुनर्निर्माण में सुधार करना. Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms. Springer-Verlag. pp. 393–402. CiteSeerX 10.1.1.138.4859. doi:10.1007/3-540-51542-9_33.
- ↑ Morin, Pat. "Chapter 8 - Scapegoat Trees". डेटा संरचनाएँ खोलें (छद्म कोड में) (0.1G β ed.). Retrieved 2017-09-16.
बाहरी संबंध
- Galpern, Igal (September 1996). On Consulting a Set of Experts and Searching (PDF) (Ph.D. thesis). MIT.
- Morin, Pat. "Chapter 8 - Scapegoat Trees". Open Data Structures (in pseudocode) (0.1G β ed.). Retrieved 2017-09-16.