स्कैप्गोट ट्री

Scapegoat tree
Type	tree
Invented	1989
Invented by	Arne Andersson, Igal Galperin, Ronald L. Rivest
Complexities in big O notation
Space complexity Space $O(n)$ Time complexity Function Amortized Worst Case Search $O(\log n)$ $O(\log n)$ Insert $O(\log n)$ $O(n)$ Delete $O(\log n)$ $O(n)$

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

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

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

सिद्धांत

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

आकार(बाएं) ≤ α*आकार(नोड)
आकार(दाएं) ≤ α*आकार(नोड)

जहां आकार को पुनरावर्ती रूप से परिभाषित किया जा सकता है:

फ़ंक्शन का आकार (नोड) है
    यदि नोड = शून्य तो
        वापसी 0
    अन्य
        वापसी का आकार(नोड->बाएं) + आकार(नोड->दाएं) + 1
    अगर अंत
अंत समारोह

यहां तक ​​कि एक पतित वृक्ष (लिंक्ड सूची) भी इस शर्त को संतुष्ट करता है यदि α=1, जबकि एक α=0.5 केवल बाइनरी ट्री#बाइनरी पेड़ों के प्रकार से मेल खाएगा।

एक द्विआधारी खोज वृक्ष जो α-भार-संतुलित है, उसे α-ऊंचाई-संतुलित भी होना चाहिए, अर्थात

ऊंचाई (पेड़) ≤ मंजिल (लॉग1/α(आकार(पेड़)))

विरोधाभास द्वारा, एक पेड़ जो α-ऊंचाई-संतुलित नहीं है, वह α-भार-संतुलित नहीं है।

बलि का बकरा पेड़ हर समय α-भार-संतुलन बनाए रखने की गारंटी नहीं देता है, लेकिन इसमें हमेशा α-ऊंचाई-संतुलित होता है

ऊँचाई (बलि का बकरा पेड़) ≤ मंजिल (लॉग1/α(आकार(पेड़))) + 1.

इस ऊंचाई संतुलन की स्थिति के उल्लंघन का पता प्रविष्टि के समय लगाया जा सकता है, और इसका अर्थ यह है कि वजन संतुलन की स्थिति का उल्लंघन अवश्य होना चाहिए।

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

अधिकांश अन्य स्व-संतुलन खोज पेड़ों के विपरीत, बलि का बकरा पेड़ अपने संतुलन के मामले में पूरी तरह से लचीले होते हैं। वे किसी भी α का समर्थन करते हैं जैसे कि 0.5 < α < 1. उच्च α मान के परिणामस्वरूप कम संतुलन होता है, जिससे सम्मिलन तेज हो जाता है लेकिन लुकअप और विलोपन धीमा हो जाता है, और कम α के लिए इसका विपरीत होता है। इसलिए व्यावहारिक अनुप्रयोगों में, इन क्रियाओं को कितनी बार किया जाना चाहिए, इसके आधार पर एक α चुना जा सकता है।

संचालन

लुकअप

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

सम्मिलन

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

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

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

बलि का बकरा ढूंढने का एक तरीका है, नए नोड से वापस जड़ तक चढ़ना और पहले नोड का चयन करना जो α-भार-संतुलित नहीं है।

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

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

आकार(बाएं) ≤ α*आकार(नोड)
आकार(दाएं) ≤ α*आकार(नोड)

हालाँकि, यह महसूस करके एक बड़ा अनुकूलन किया जा सकता है कि हम पहले से ही तीन में से दो आकारों को जानते हैं, केवल तीसरे की गणना करना बाकी है।

इसे प्रदर्शित करने के लिए निम्नलिखित उदाहरण पर विचार करें। यह मानते हुए कि हम जड़ तक वापस चढ़ रहे हैं:

आकार (मूल) = आकार (नोड) + आकार (भाई-बहन) + 1

परंतु जैसे:

आकार (सम्मिलित नोड) = 1.

मामले को निम्न स्तर तक महत्वहीन बना दिया गया है:

आकार[x+1] = आकार[x] + आकार(भाई-बहन) + 1

जहां x = यह नोड, x + 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)\$

व्युत्पत्ति

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

यह भी देखें

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

बाहरी संबंध

• 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.