स्कैप्गोट ट्री: Difference between revisions

Scapegoat tree
Scapegoat tree
Type	tree
Invented	1989
Invented by	Arne Andersson, Igal Galperin, Ronald L. Rivest
Complexities in big O notation
Space
Space complexity
Space
Time complexity
Function
Search
Insert
Delete

Revision as of 10:34, 17 July 2023

कंप्यूटर विज्ञान में, स्कैप्गोट ट्री एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री है, जिसका आविष्कार 1989 में अर्ने एंडरसन^[2]द्वारा और फिर 1993 में इगल गैल्परिन और रोनाल्ड एल. रिवेस्ट द्वारा किया गया था।^[1] यह निकृष्‍टतम् ${\color {Blue}O(\log n)}$ परीक्षण समय (प्रविष्टियों की संख्या के रूप में आर के साथ) और $n$ प्रविष्टियों की संख्या के रूप में) और $O(\log n)$ परिशोधन विश्लेषण और विलोपन समय प्रदान करता है।

अधिकांश अन्य सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री के विपरीत, जो निकृष्‍टतम् $O(\log n)$ भी प्रदान करते हैं परीक्षण समय, नियमित बाइनरी सर्च ट्री की तुलना में स्कैप्गोट ट्री में कोई अतिरिक्त प्रति-नोड मेमोरी उपरि नहीं होता है: कीय और मान के अलावा, एक नोड चाइल्ड नोड्स में केवल दो पॉइंटर्स संग्रहीत करता है। इससे स्कैप्गोट ट्री लागू करना आसान हो जाता है और डेटा संरचना संरेखण के कारण, नोड उपरि को एक तिहाई तक कम किया जा सकता है।

अधिकांश संतुलित ट्री एल्गोरिदम द्वारा उपयोग किए जाने वाले छोटे वृद्धिशील पुनर्संतुलन संचालन के बजाय, स्कैप्गोट ट्री शायद ही कभी लेकिन महंगा रूप से स्कैप्गोट ट्री चुनते हैं और "स्कैप्गोट" में निहित सबट्री को पूर्ण बाइनरी ट्री में पूरी तरह से पुनर्निर्माण करते हैं। इस प्रकार, स्कैप्गोट ट्री $O(n)$ निकृष्‍टतम् में अद्यतन प्रदर्शन है।

सिद्धांत

बाइनरी सर्च ट्री को भारित-संतुलित कहा जाता है यदि आधे नोड्स मूल के बाईं ओर और आधे दाईं ओर होंते हैं। α-भार-संतुलित नोड को विश्रांत भारित संतुलन मानदंड को पूरा करने के रूप में परिभाषित किया गया है:

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. उच्च α मान के परिणामस्वरूप कम संतुलन होता है, जिससे सम्मिलन तेज हो जाता है लेकिन परीक्षण और विलोपन धीमा हो जाता है, और कम α के लिए इसका विपरीत होता है। इसलिए व्यावहारिक अनुप्रयोगों में, इन क्रियाओं को कितनी बार किया जाना चाहिए, इसके आधार पर एक α चुना जा सकता है।

संचालन

परीक्षण

परीक्षण को मानक बाइनरी सर्च ट्री से संशोधित नहीं किया गया है, और इसकी निकृष्‍टतम् $O(\log n)$ है, यह उन ट्री के विपरीत है जिनकी निकृष्‍टतम् $O(n)$ होती है। अन्य सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में कम नोड मेमोरी उपरि संदर्भ और कैशिंग की स्थानीयता में और सुधार कर सकता है।

सम्मिलन

सम्मिलन को बाइनरी सर्च ट्री के समान मूल विचारों के साथ, हालाँकि कुछ महत्वपूर्ण परिवर्तनों के साथ कार्यान्वित किया जाता है।

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

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

स्कैप्गोट ट्री प्रतिलब्धि का एक तरीका है, नए नोड से वापस मूल तक उन्नति और पहले नोड का चयन करना जो α-भार-संतुलित नहीं है।

मूल तक वापस उन्नति $O(\log n)$ की आवश्यकता है भंडारण स्थान, आमतौर पर स्टैक, या पैरेंट पॉइंटर्स पर आवंटित किया जाता है। वास्तव में इससे बचा जा सकता है, जब आप नीचे जाते समय प्रत्येक बच्चे को उसके माता-पिता की ओर इशारा करते हैं, और वापस ऊपर जाते समय मरम्मत करते हैं।

यह निर्धारित करने के लिए कि क्या संभावित नोड व्यवहार्य स्कैप्गोट ट्री है, हमें इसकी α-भार-संतुलित गुण की जांच करने की आवश्यकता है। ऐसा करने के लिए हम परिभाषा पर वापस जा सकते हैं:

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 = मूल और माप (भाई-बहन) ही एकमात्र फ़ंक्शन कॉल है जो वास्तव में आवश्यक है।

एक बार जब स्कैप्गोट ट्री मिल जाता है, तो स्कैप्गोट में निहित सबट्री को पूरी तरह से संतुलित करने के लिए फिर से बनाया जाता है।^[1] इस $O(n)$ में किया जा सकता है क्रमबद्ध क्रम में उनके मान को खोजने के लिए उप-ट्री के नोड्स को पार करके और उप-ट्री के मूल के रूप में मध्यिका को पुनरावर्ती रूप से चुनकर।

जैसा कि पुनर्संतुलन संचालन में लगता है $O(n)$ समय (उपट्री के नोड्स की संख्या पर निर्भर), सम्मिलन का प्रदर्शन सबसे खराब है $O(n)$ समय। हालाँकि, क्योंकि ये निकृष्‍टतम् फैली हुई है, सम्मिलन होता है $O(\log n)$ परिशोधित समय.

प्रविष्टि की लागत के लिए प्रमाण का स्केच

किसी नोड के असंतुलन को परिभाषित करें v इसके बाएं नोड और दाएं नोड के बीच माप में अंतर का पूर्ण मान शून्य से 1, या 0, जो भी अधिक हो। दूसरे शब्दों में:

$I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)$ v पर निहित सबट्री के पुनर्निर्माण के तुरंत बाद, I(v) = 0।

'लेम्मा:' सबट्री के पुनर्निर्माण से ठीक पहले v,
पर रूट किया गया $I(v)\in \Omega (|v|)$
( $\Omega$ बिग ओमेगा संकेतन है।)

लेम्मा का प्रमाण:

होने देना $v_{0}$ पुनर्निर्माण के तुरंत बाद एक सबट्री की मूल बनें। $h(v_{0})=\log(|v_{0}|+1)$ . अगर वहाँ $\Omega (|v_{0}|)$ पतित सम्मिलन (अर्थात, जहां प्रत्येक सम्मिलित नोड ऊंचाई 1 से बढ़ाता है), फिर
$I(v)\in \Omega (|v_{0}|)$ ,
$h(v)=h(v_{0})+\Omega (|v_{0}|)$ और
$\log(|v|)\leq \log(|v_{0}|+1)+1$ .

तब से $I(v)\in \Omega (|v|)$ पुनर्निर्माण से पहले, वहाँ थे $\Omega (|v|)$ पर निहित सबट्री में सम्मिलन $v$ जिसके परिणामस्वरूप पुनर्निर्माण नहीं हुआ। इनमें से प्रत्येक सम्मिलन को निष्पादित किया जा सकता है $O(\log n)$ समय। अंतिम सम्मिलन जो पुनर्निर्माण लागत का कारण बनता है $O(|v|)$ . समग्र विश्लेषण का उपयोग करने से यह स्पष्ट हो जाता है कि किसी प्रविष्टि की परिशोधित लागत कितनी है $O(\log n)$ :

${\Omega (|v|)O(\log n)+O(|v|) \over \Omega (|v|)}=O(\log n)$

विलोपन

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

विलोपन करने के लिए, हम बस नोड को हटा देते हैं जैसे आप एक साधारण बाइनरी सर्च ट्री में करते हैं, लेकिन यदि

नोडकाउंट ≤ α*मैक्सनोडकाउंट

फिर हम पूरे ट्री को मूल के बारे में पुनर्संतुलित करते हैं, MaxNodeCount को NodeCount पर सेट करना याद रखते हैं।

यह विलोपन को निकृष्‍टतम् वाला प्रदर्शन देता है $O(n)$ समय, जबकि परिशोधित समय है $O(\log n)$ .

हटाने की लागत के लिए सबूत का स्केच

मान लीजिए कि स्कैप्गोट ट्री ट्री के पास है $n$ तत्वों और अभी इसका पुनर्निर्माण किया गया है (दूसरे शब्दों में, यह एक पूर्ण बाइनरी ट्री है)। अधिक से अधिक $n/2-1$ ट्री को फिर से बनाने से पहले हटाया जा सकता है। इनमें से प्रत्येक विलोपन लेता है $O(\log n)$ समय (तत्व को खोजने और उसे हटाए गए के रूप में चिह्नित करने के लिए समय की मात्रा)। $n/2$ h> विलोपन के कारण ट्री का पुनर्निर्माण होता है और लेता है $O(\log n)+O(n)$ (या केवल $O(n)$ ) समय। समग्र विश्लेषण का उपयोग करने से यह स्पष्ट हो जाता है कि विलोपन की परिशोधित लागत कितनी है $O(\log n)$ :

${\sum _{1}^{n/2}O(\log n)+O(n) \over n/2}={{n \over 2}O(\log n)+O(n) \over n/2}=O(\log n)\$

व्युत्पत्ति

स्कैपगोट ट्री नाम [...] सामान्य ज्ञान पर आधारित है कि, जब कुछ गलत होता है, तो सबसे पहले लोग जो करते हैं वह किसी को दोष देने के लिए (स्कैप्गोट ट्री) ढूंढना होता है। ^[3] बाइबिल में, स्कैप्गोट ट्री एक ऐसा जानवर है जिस पर अनुष्ठानिक रूप से दूसरों के पापों का बोझ डाला जाता है और फिर उसे भगा दिया जाता है।

यह भी देखें

छींटे का ट्री
ट्री डेटा संरचना
ट्री परिभ्रमण
एवीएल ट्री
बी-ट्री
टी ट्री

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 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.

[galperin_rivest-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 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.

[anderson1-2] 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.

[opendatastructures-3] Morin, Pat. "Chapter 8 - Scapegoat Trees". डेटा संरचनाएँ खोलें (छद्म कोड में) (0.1G β ed.). Retrieved 2017-09-16.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{Short description|Type of balanced binary search tree}}
-{{multiple issues|
-{{more footnotes|date=March 2014}}
-{{refimprove|date=March 2014}}
-}}
 {{Infobox data structure-amortized
 |name=Scapegoat tree
@@ Line 18: / Line 14: @@
 }}
-[[कंप्यूटर विज्ञान]] में, बलि का बकरा वृक्ष एक [[स्व-संतुलन द्विआधारी खोज वृक्ष]] है, जिसका आविष्कार आर्ने एंडरसन (कंप्यूटर वैज्ञानिक) ने किया था।<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> 1989 में और फिर 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> यह सबसे खराब स्थिति में बड़ा O नोटेशन प्रदान करता है|<math>{\color{Blue}O(\log n)}</math>लुकअप समय (के साथ) <math>n</math> प्रविष्टियों की संख्या के रूप में) और <math>O(\log n)</math> [[परिशोधन विश्लेषण]] सम्मिलन और विलोपन समय।
+[[कंप्यूटर विज्ञान]] में, स्कैप्गोट ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष|सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] है, जिसका आविष्कार 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(\log n)</math> भी प्रदान करते हैं परीक्षण समय, नियमित [[बाइनरी सर्च ट्री]] की तुलना में स्कैप्गोट ट्री में कोई अतिरिक्त प्रति-नोड मेमोरी उपरि नहीं होता है: कीय और मान के अलावा, एक नोड चाइल्ड नोड्स में केवल दो पॉइंटर्स संग्रहीत करता है। इससे स्कैप्गोट ट्री लागू करना आसान हो जाता है और [[डेटा संरचना संरेखण]] के कारण, नोड उपरि को एक तिहाई तक कम किया जा सकता है।
-अधिकांश संतुलित वृक्ष एल्गोरिदम द्वारा उपयोग किए जाने वाले छोटे वृद्धिशील पुनर्संतुलन संचालन के बजाय, बलि का बकरा पेड़ शायद ही कभी लेकिन महंगा रूप से एक बलि का बकरा चुनते हैं और बलि के बकरे में निहित उपवृक्ष को एक पूर्ण बाइनरी पेड़ में पूरी तरह से पुनर्निर्माण करते हैं। इस प्रकार, बलि का बकरा पेड़ है <math>O(n)</math> सबसे खराब स्थिति में अद्यतन प्रदर्शन।
+अधिकांश संतुलित ट्री एल्गोरिदम द्वारा उपयोग किए जाने वाले छोटे वृद्धिशील पुनर्संतुलन संचालन के बजाय, स्कैप्गोट ट्री शायद ही कभी लेकिन महंगा रूप से स्कैप्गोट ट्री चुनते हैं और "स्कैप्गोट" में निहित सबट्री को पूर्ण बाइनरी ट्री में पूरी तरह से पुनर्निर्माण करते हैं। इस प्रकार, स्कैप्गोट ट्री <math>O(n)</math> निकृष्‍टतम् में अद्यतन प्रदर्शन है।
 ==सिद्धांत==
-एक बाइनरी सर्च ट्री को वजन-संतुलित कहा जाता है यदि आधे नोड्स जड़ के बाईं ओर और आधे दाईं ओर हों।
+बाइनरी सर्च ट्री को भारित-संतुलित कहा जाता है यदि आधे नोड्स मूल के बाईं ओर और आधे दाईं ओर होंते हैं। α-भार-संतुलित नोड को विश्रांत भारित संतुलन मानदंड को पूरा करने के रूप में परिभाषित किया गया है:
-एक α-भार-संतुलित नोड को एक आरामदायक वजन संतुलन मानदंड को पूरा करने के रूप में परिभाषित किया गया है:
+  size(left) ≤ α*size(node)
-  आकार(बाएं) ≤ α*आकार(नोड)
+  size(right) ≤ α*size(node)
-  आकार(दाएं) ≤ α*आकार(नोड)
+जहां  माप को पुनरावर्ती रूप से परिभाषित किया जा सकता है:
-जहां आकार को पुनरावर्ती रूप से परिभाषित किया जा सकता है:
+  '''function''' size(node) '''is'''
-  फ़ंक्शन का आकार (नोड) है
+      '''if''' node = nil '''then'''
-      यदि नोड = शून्य तो
+          '''return''' 0
-          वापसी 0
+      '''else
-      अन्य
+          return''' size(node->left) + size(node->right) + 1
-          वापसी का आकार(नोड->बाएं) + आकार(नोड->दाएं) + 1
+      '''end if
-      अगर अंत
+  end function'''
-  अंत समारोह
-यहां तक कि एक पतित वृक्ष (लिंक्ड सूची) भी इस शर्त को संतुष्ट करता है यदि α=1, जबकि एक α=0.5 केवल बाइनरी ट्री#बाइनरी पेड़ों के प्रकार से मेल खाएगा।
+यहां तक कि पतित ट्री (लिंक्ड सूची) भी इस शर्त को संतुष्ट करता है यदि α=1, जबकि α=0.5 केवल बाइनरी ट्री के प्रकार से बराबर होगा।
-एक द्विआधारी खोज वृक्ष जो α-भार-संतुलित है, उसे α-ऊंचाई-संतुलित भी होना चाहिए, अर्थात
+बाइनरी सर्च ट्री जो α-भार-संतुलित है, उसे α-ऊंचाई-संतुलित भी होना चाहिए, अर्थात
-  ऊंचाई (पेड़) ≤ मंजिल (लॉग<sub>1/α</sub>(आकार(पेड़)))
+  height(tree) ≤ floor(log1/α(size(tree)))
-विरोधाभास द्वारा, एक पेड़ जो α-ऊंचाई-संतुलित नहीं है, वह α-भार-संतुलित नहीं है।
+विरोधाभास द्वारा, ट्री जो α-ऊंचाई-संतुलित नहीं है, वह α-भार-संतुलित नहीं है।
-बलि का बकरा पेड़ हर समय α-भार-संतुलन बनाए रखने की गारंटी नहीं देता है, लेकिन इसमें हमेशा α-ऊंचाई-संतुलित होता है
+स्कैप्गोट ट्री हर समय α-भार-संतुलन बनाए रखने की गारंटी नहीं देता है, लेकिन इसमें हमेशा α-ऊंचाई-संतुलित होता है
-  ऊँचाई (बलि का बकरा पेड़) ≤ मंजिल (लॉग<sub>1/α</sub>(आकार(पेड़))) + 1.
+  height(scapegoat tree) ≤ floor(log1/α(size(tree))) + 1.
-इस ऊंचाई संतुलन की स्थिति के उल्लंघन का पता प्रविष्टि के समय लगाया जा सकता है, और इसका अर्थ यह है कि वजन संतुलन की स्थिति का उल्लंघन अवश्य होना चाहिए।
+इस ऊंचाई संतुलन की स्थिति के उल्लंघन का पता प्रविष्टि के समय लगाया जा सकता है, और इसका अर्थ यह है कि भारित संतुलन की स्थिति का उल्लंघन अवश्य होना चाहिए।
-यह बलि के पेड़ों को लाल-काले पेड़ों के समान बनाता है, क्योंकि उन दोनों की ऊंचाई पर प्रतिबंध है। हालाँकि वे यह निर्धारित करने के अपने कार्यान्वयन में बहुत भिन्न हैं कि घुमाव (या बलि के बकरे के पेड़ों के मामले में, पुनर्संतुलन) कहाँ होते हैं। जबकि लाल-काले पेड़ स्थान निर्धारित करने के लिए प्रत्येक नोड में अतिरिक्त 'रंग' जानकारी संग्रहीत करते हैं, बलि का बकरा पेड़ एक बलि का बकरा ढूंढते हैं जो पुनर्संतुलन ऑपरेशन करने के लिए α-भार-संतुलित नहीं होता है। यह [[एवीएल पेड़]]ों के समान है, जिसमें वास्तविक घुमाव नोड्स के 'संतुलन' पर निर्भर करते हैं, लेकिन संतुलन निर्धारित करने के साधन बहुत भिन्न होते हैं। चूंकि एवीएल पेड़ प्रत्येक प्रविष्टि/विलोपन पर शेष मूल्य की जांच करते हैं, इसलिए इसे आम तौर पर प्रत्येक नोड में संग्रहीत किया जाता है; बलि का बकरा पेड़ केवल आवश्यकतानुसार ही इसकी गणना करने में सक्षम होते हैं, जो केवल तब होता है जब बलि का बकरा ढूंढने की आवश्यकता होती है।
+यह स्कैप्गोट ट्री को रेड–ब्लैक ट्री के समान बनाता है, क्योंकि उन दोनों की ऊंचाई पर प्रतिबंध है। हालाँकि वे यह निर्धारित करने के अपने कार्यान्वयन में बहुत भिन्न हैं कि घुमाव (या स्कैप्गोट ट्री के मामले में, पुनर्संतुलन) कहाँ होते हैं। जबकि रेड–ब्लैक ट्री स्थान निर्धारित करने के लिए प्रत्येक नोड में अतिरिक्त 'रंग' जानकारी संग्रहीत करते हैं, स्कैप्गोट ट्री, '''स्कैप्गोट ट्री''' ढूंढते हैं जो पुनर्संतुलन संचालन करने के लिए α-भार-संतुलित नहीं होता है। यह [[एवीएल पेड़|एवीएल ट्री]] के समान है, जिसमें वास्तविक घुमाव नोड्स के 'संतुलन' पर निर्भर करते हैं, लेकिन संतुलन निर्धारित करने के साधन बहुत भिन्न होते हैं। चूंकि एवीएल ट्री प्रत्येक प्रविष्टि/विलोपन पर शेष मान की जांच करते हैं, इसलिए इसे आम तौर पर प्रत्येक नोड में संग्रहीत किया जाता है; स्कैप्गोट ट्री केवल आवश्यकतानुसार ही इसकी गणना करने में सक्षम होते हैं, जो केवल तब होता है जब स्कैप्गोट ट्री प्रतिलब्धि की आवश्यकता होती है।
-अधिकांश अन्य स्व-संतुलन खोज पेड़ों के विपरीत, बलि का बकरा पेड़ अपने संतुलन के मामले में पूरी तरह से लचीले होते हैं। वे किसी भी α का समर्थन करते हैं जैसे कि 0.5 < α < 1. उच्च α मान के परिणामस्वरूप कम संतुलन होता है, जिससे सम्मिलन तेज हो जाता है लेकिन लुकअप और विलोपन धीमा हो जाता है, और कम α के लिए इसका विपरीत होता है। इसलिए व्यावहारिक अनुप्रयोगों में, इन क्रियाओं को कितनी बार किया जाना चाहिए, इसके आधार पर एक α चुना जा सकता है।
+अधिकांश अन्य स्व-संतुलन खोज ट्री के विपरीत, स्कैप्गोट ट्री अपने संतुलन के मामले में पूरी तरह से लचीले होते हैं। वे किसी भी α का समर्थन करते हैं जैसे कि 0.5 < α < 1. उच्च α मान के परिणामस्वरूप कम संतुलन होता है, जिससे सम्मिलन तेज हो जाता है लेकिन परीक्षण और विलोपन धीमा हो जाता है, और कम α के लिए इसका विपरीत होता है। इसलिए व्यावहारिक अनुप्रयोगों में, इन क्रियाओं को कितनी बार किया जाना चाहिए, इसके आधार पर एक α चुना जा सकता है।
 ==संचालन==
-===लुकअप===
+===परीक्षण===
-लुकअप को मानक बाइनरी सर्च ट्री से संशोधित नहीं किया गया है, और इसकी सबसे खराब स्थिति है <math>O(\log n)</math>. यह उन पेड़ों के विपरीत है जिनकी स्थिति सबसे खराब होती है <math>O(n)</math>. अन्य स्व-संतुलन बाइनरी खोज पेड़ों की तुलना में कम नोड मेमोरी ओवरहेड संदर्भ और कैशिंग की स्थानीयता में और सुधार कर सकता है।
+परीक्षण को मानक बाइनरी सर्च ट्री से संशोधित नहीं किया गया है, और इसकी निकृष्‍टतम्<math>O(\log n)</math> है, यह उन ट्री के विपरीत है जिनकी निकृष्‍टतम् <math>O(n)</math> होती है। अन्य सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में कम नोड मेमोरी उपरि संदर्भ और कैशिंग की स्थानीयता में और सुधार कर सकता है।
 ===सम्मिलन===
-सम्मिलन को बाइनरी सर्च ट्री#सम्मिलन के समान मूल विचारों के साथ कार्यान्वित किया जाता है, हालाँकि कुछ महत्वपूर्ण परिवर्तनों के साथ।
+सम्मिलन को बाइनरी सर्च ट्री के समान मूल विचारों के साथ, हालाँकि कुछ महत्वपूर्ण परिवर्तनों के साथ कार्यान्वित किया जाता है।
-सम्मिलन बिंदु ढूंढते समय, नए नोड की गहराई भी दर्ज की जानी चाहिए। इसे एक साधारण काउंटर के माध्यम से कार्यान्वित किया जाता है जो लुकअप के प्रत्येक पुनरावृत्ति के दौरान बढ़ता है, रूट और सम्मिलित नोड के बीच किनारों की संख्या को प्रभावी ढंग से गिनता है। यदि यह नोड α-ऊंचाई-संतुलन संपत्ति (ऊपर परिभाषित) का उल्लंघन करता है, तो पुनर्संतुलन की आवश्यकता होती है।
+सम्मिलन बिंदु ढूंढते समय, नए नोड की गहराई भी दर्ज की जानी चाहिए। इसे साधारण काउंटर के माध्यम से कार्यान्वित किया जाता है जो परीक्षण के प्रत्येक पुनरावृत्ति के दौरान बढ़ता है, रूट और सम्मिलित नोड के बीच किनारों की संख्या को प्रभावी ढंग से गिनता है। यदि यह नोड α-ऊंचाई-संतुलन गुण (ऊपर परिभाषित) का उल्लंघन करता है, तो पुनर्संतुलन की आवश्यकता होती है।
-पुनर्संतुलन के लिए, बलि के बकरे पर आधारित संपूर्ण उपवृक्ष को एक संतुलन ऑपरेशन से गुजरना पड़ता है। बलि के बकरे को सम्मिलित नोड के पूर्वज के रूप में परिभाषित किया गया है जो α-भार-संतुलित नहीं है। ऐसा कम से कम एक पूर्वज हमेशा रहेगा। उनमें से किसी को भी पुनर्संतुलित करने से α-ऊंचाई-संतुलित संपत्ति बहाल हो जाएगी।
+पुनर्संतुलन के लिए, '''स्कैप्गोट''' पर आधारित संपूर्ण सबट्री को संतुलन संचालन से गुजरना पड़ता है। स्कैप्गोट को सम्मिलित नोड के पूर्वज के रूप में परिभाषित किया गया है जो α-भार-संतुलित नहीं है। ऐसा कम से कम एक पूर्वज हमेशा रहेगा। उनमें से किसी को भी पुनर्संतुलित करने से α-ऊंचाई-संतुलित गुण बहाल हो जाएगी।
-बलि का बकरा ढूंढने का एक तरीका है, नए नोड से वापस जड़ तक चढ़ना और पहले नोड का चयन करना जो α-भार-संतुलित नहीं है।
+स्कैप्गोट ट्री प्रतिलब्धि का एक तरीका है, नए नोड से वापस मूल तक उन्नति और पहले नोड का चयन करना जो α-भार-संतुलित नहीं है।
-जड़ तक वापस चढ़ने की आवश्यकता है <math>O(\log n)</math> भंडारण स्थान, आमतौर पर स्टैक, या पैरेंट पॉइंटर्स पर आवंटित किया जाता है। वास्तव में इससे बचा जा सकता है, जब आप नीचे जाते समय प्रत्येक बच्चे को उसके माता-पिता की ओर इशारा करते हैं, और वापस ऊपर जाते समय मरम्मत करते हैं।
+मूल तक वापस उन्नति <math>O(\log n)</math> की आवश्यकता है भंडारण स्थान, आमतौर पर स्टैक, या पैरेंट पॉइंटर्स पर आवंटित किया जाता है। वास्तव में इससे बचा जा सकता है, जब आप नीचे जाते समय प्रत्येक बच्चे को उसके माता-पिता की ओर इशारा करते हैं, और वापस ऊपर जाते समय मरम्मत करते हैं।
-यह निर्धारित करने के लिए कि क्या एक संभावित नोड एक व्यवहार्य बलि का बकरा है, हमें इसकी α-भार-संतुलित संपत्ति की जांच करने की आवश्यकता है। ऐसा करने के लिए हम परिभाषा पर वापस जा सकते हैं:
+यह निर्धारित करने के लिए कि क्या संभावित नोड व्यवहार्य स्कैप्गोट ट्री है, हमें इसकी α-भार-संतुलित गुण की जांच करने की आवश्यकता है। ऐसा करने के लिए हम परिभाषा पर वापस जा सकते हैं:
-  आकार(बाएं) ≤ α*आकार(नोड)
+  size(left) ≤ α*size(node)
-  आकार(दाएं) ≤ α*आकार(नोड)
+  size(right) ≤ α*size(node)
-हालाँकि, यह महसूस करके एक बड़ा अनुकूलन किया जा सकता है कि हम पहले से ही तीन में से दो आकारों को जानते हैं, केवल तीसरे की गणना करना बाकी है।
+हालाँकि, यह महसूस करके बड़ा अनुकूलन किया जा सकता है कि हम पहले से ही तीन में से दो आकारों को जानते हैं, केवल तीसरे की गणना करना बाकी है।
-इसे प्रदर्शित करने के लिए निम्नलिखित उदाहरण पर विचार करें। यह मानते हुए कि हम जड़ तक वापस चढ़ रहे हैं:
+इसे प्रदर्शित करने के लिए निम्नलिखित उदाहरण पर विचार करें। यह मानते हुए कि हम मूल तक वापस चढ़ रहे हैं:
-  आकार (मूल) = आकार (नोड) + आकार (भाई-बहन) + 1
+  size(parent) = size(node) + size(sibling) + 1
 परंतु जैसे:
- आकार (सम्मिलित नोड) = 1.
+  size(inserted node) = 1.
 मामले को निम्न स्तर तक महत्वहीन बना दिया गया है:
- आकार[x+1] = आकार[x] + आकार(भाई-बहन) + 1
+  size[x+1] = size[x] + size(sibling) + 1
-जहां x = यह नोड, x + 1 = मूल और आकार (भाई-बहन) ही एकमात्र फ़ंक्शन कॉल है जो वास्तव में आवश्यक है।
+जहां x = यह नोड, x + 1 = मूल और  माप (भाई-बहन) ही एकमात्र फ़ंक्शन कॉल है जो वास्तव में आवश्यक है।
-एक बार जब बलि का बकरा मिल जाता है, तो बलि के बकरे में निहित उपवृक्ष को पूरी तरह से संतुलित करने के लिए फिर से बनाया जाता है।<ref name=galperin_rivest/>  इसमें किया जा सकता है <math>O(n)</math> क्रमबद्ध क्रम में उनके मूल्यों को खोजने के लिए उप-वृक्ष के नोड्स को पार करके और उप-वृक्ष के मूल के रूप में मध्यिका को पुनरावर्ती रूप से चुनकर।
+एक बार जब स्कैप्गोट ट्री मिल जाता है, तो स्कैप्गोट में निहित सबट्री को पूरी तरह से संतुलित करने के लिए फिर से बनाया जाता है।<ref name=galperin_rivest/> इस <math>O(n)</math> में किया जा सकता है क्रमबद्ध क्रम में उनके मान को खोजने के लिए उप-ट्री के नोड्स को पार करके और उप-ट्री के मूल के रूप में मध्यिका को पुनरावर्ती रूप से चुनकर।
-जैसा कि पुनर्संतुलन संचालन में लगता है <math>O(n)</math> समय (उपट्री के नोड्स की संख्या पर निर्भर), सम्मिलन का प्रदर्शन सबसे खराब है <math>O(n)</math> समय। हालाँकि, क्योंकि ये सबसे खराब स्थिति फैली हुई है, सम्मिलन होता है <math>O(\log n)</math> परिशोधित समय.
+जैसा कि पुनर्संतुलन संचालन में लगता है <math>O(n)</math> समय (उपट्री के नोड्स की संख्या पर निर्भर), सम्मिलन का प्रदर्शन सबसे खराब है <math>O(n)</math> समय। हालाँकि, क्योंकि ये निकृष्‍टतम् फैली हुई है, सम्मिलन होता है <math>O(\log n)</math> परिशोधित समय.
 ====प्रविष्टि की लागत के लिए प्रमाण का स्केच====
-किसी नोड के असंतुलन को परिभाषित करें v इसके बाएं नोड और दाएं नोड के बीच आकार में अंतर का पूर्ण मान शून्य से 1, या 0, जो भी अधिक हो। दूसरे शब्दों में:
+किसी नोड के असंतुलन को परिभाषित करें v इसके बाएं नोड और दाएं नोड के बीच  माप में अंतर का पूर्ण मान शून्य से 1, या 0, जो भी अधिक हो। दूसरे शब्दों में:
 <math>I(v) = \operatorname{max}(|\operatorname{left}(v) - \operatorname{right}(v)| - 1, 0) </math>
-v पर निहित उपवृक्ष के पुनर्निर्माण के तुरंत बाद, I(v) = 0।
+v पर निहित सबट्री के पुनर्निर्माण के तुरंत बाद, I(v) = 0।
 'लेम्मा:' सबट्री के पुनर्निर्माण से ठीक पहले v, <br /> पर रूट किया गया
@@ Line 98: / Line 93: @@
 लेम्मा का प्रमाण:
-होने देना <math>v_0</math> पुनर्निर्माण के तुरंत बाद एक उपवृक्ष की जड़ बनें।  <math>h(v_0) = \log(|v_0| + 1) </math>. अगर वहाँ <math>\Omega (|v_0|)</math> पतित सम्मिलन (अर्थात, जहां प्रत्येक सम्मिलित नोड ऊंचाई 1 से बढ़ाता है), फिर <br />
+होने देना <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|)</math> पुनर्निर्माण से पहले, वहाँ थे <math>\Omega (|v|)</math> पर निहित उपवृक्ष में सम्मिलन <math>v</math> जिसके परिणामस्वरूप पुनर्निर्माण नहीं हुआ। इनमें से प्रत्येक सम्मिलन को निष्पादित किया जा सकता है <math>O(\log n)</math> समय। अंतिम सम्मिलन जो पुनर्निर्माण लागत का कारण बनता है <math>O(|v|)</math>. [[समग्र विश्लेषण]] का उपयोग करने से यह स्पष्ट हो जाता है कि किसी प्रविष्टि की परिशोधित लागत कितनी है <math>O(\log n)</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>
@@ Line 109: / Line 104: @@
 ===विलोपन===
-बलि का बकरा पेड़ इस मायने में असामान्य है कि सम्मिलन की तुलना में हटाना आसान है। विलोपन को सक्षम करने के लिए, बलि का बकरा पेड़ों को पेड़ डेटा संरचना के साथ एक अतिरिक्त मूल्य संग्रहीत करने की आवश्यकता होती है। यह संपत्ति, जिसे हम MaxNodeCount कहेंगे, केवल उच्चतम प्राप्त NodeCount का प्रतिनिधित्व करती है। जब भी पूरा पेड़ पुनर्संतुलित होता है तो इसे नोडकाउंट पर सेट किया जाता है, और सम्मिलन के बाद अधिकतम (मैक्सनोडकाउंट, नोडकाउंट) पर सेट किया जाता है।
+स्कैप्गोट ट्री ट्री इस मायने में असामान्य है कि सम्मिलन की तुलना में हटाना आसान है। विलोपन को सक्षम करने के लिए, स्कैप्गोट ट्री ट्री को ट्री डेटा संरचना के साथ एक अतिरिक्त मान संग्रहीत करने की आवश्यकता होती है। यह गुण, जिसे हम MaxNodeCount कहेंगे, केवल उच्चतम प्राप्त NodeCount का प्रतिनिधित्व करती है। जब भी पूरा ट्री पुनर्संतुलित होता है तो इसे नोडकाउंट पर सेट किया जाता है, और सम्मिलन के बाद अधिकतम (मैक्सनोडकाउंट, नोडकाउंट) पर सेट किया जाता है।
 विलोपन करने के लिए, हम बस नोड को हटा देते हैं जैसे आप एक साधारण बाइनरी सर्च ट्री में करते हैं, लेकिन यदि
   नोडकाउंट ≤ α*मैक्सनोडकाउंट
-फिर हम पूरे पेड़ को जड़ के बारे में पुनर्संतुलित करते हैं, MaxNodeCount को NodeCount पर सेट करना याद रखते हैं।
+फिर हम पूरे ट्री को मूल के बारे में पुनर्संतुलित करते हैं, MaxNodeCount को NodeCount पर सेट करना याद रखते हैं।
-यह विलोपन को सबसे खराब स्थिति वाला प्रदर्शन देता है <math>O(n)</math> समय, जबकि परिशोधित समय है <math>O(\log n)</math>.
+यह विलोपन को निकृष्‍टतम् वाला प्रदर्शन देता है <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>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>
@@ Line 128: / Line 123: @@
 ==व्युत्पत्ति==
-स्कैपगोट ट्री नाम '' [...] सामान्य ज्ञान पर आधारित है कि, जब कुछ गलत होता है, तो सबसे पहले लोग जो करते हैं वह किसी को दोष देने के लिए (बलि का बकरा) ढूंढना होता है। ''<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> [[बाइबिल]] में, [[बलि का बकरा]] एक ऐसा जानवर है जिस पर अनुष्ठानिक रूप से दूसरों के पापों का बोझ डाला जाता है और फिर उसे भगा दिया जाता है।
+स्कैपगोट ट्री नाम '' [...] सामान्य ज्ञान पर आधारित है कि, जब कुछ गलत होता है, तो सबसे पहले लोग जो करते हैं वह किसी को दोष देने के लिए (स्कैप्गोट ट्री) ढूंढना होता है। ''<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> [[बाइबिल]] में, [[बलि का बकरा|स्कैप्गोट ट्री]] एक ऐसा जानवर है जिस पर अनुष्ठानिक रूप से दूसरों के पापों का बोझ डाला जाता है और फिर उसे भगा दिया जाता है।
 ==यह भी देखें==
-* छींटे का पेड़
+* छींटे का ट्री
-* [[वृक्ष डेटा संरचना]]
+* [[वृक्ष डेटा संरचना|ट्री डेटा संरचना]]
-* वृक्ष परिभ्रमण
+* ट्री परिभ्रमण
-*एवीएल वृक्ष
+*एवीएल ट्री
-*[[बी-वृक्ष]]
+*[[बी-वृक्ष|बी-ट्री]]
-* [[ टी पेड़ ]]
+* [[ टी पेड़ | टी ट्री]]
 ==संदर्भ==

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

Anonymous

Search

स्कैप्गोट ट्री: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:34, 17 July 2023

Contents

सिद्धांत

संचालन

परीक्षण

सम्मिलन

प्रविष्टि की लागत के लिए प्रमाण का स्केच

विलोपन

हटाने की लागत के लिए सबूत का स्केच

व्युत्पत्ति

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

स्कैप्गोट ट्री: Difference between revisions

Revision as of 10:34, 17 July 2023

सिद्धांत

संचालन

परीक्षण

सम्मिलन

प्रविष्टि की लागत के लिए प्रमाण का स्केच

विलोपन

हटाने की लागत के लिए सबूत का स्केच

व्युत्पत्ति

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories