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

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 में इगल गैल्परिन और रोनाल्ड एल. रिवेस्ट द्वारा किया गया था। यह निकृष्‍टतम् ${\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 = मूल और माप (भाई-बहन) ही एकमात्र फ़ंक्शन कॉल है जो वास्तव में आवश्यक है।

एक बार जब स्कैप्गोट ट्री मिल जाता है, तो स्कैप्गोट में निहित सबट्री को पूरी तरह से संतुलित करने के लिए फिर से बनाया जाता है।यह सबट्री के नोड्स को क्रमबद्ध क्रम में उनके मान को खोजने के लिए उप-ट्री के नोड्स को पार करके और उप-ट्री के मूल के रूप में मध्यिका को पुनरावर्ती रूप से चुनकर $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)$

विलोपन

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

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

NodeCount ≤ α*MaxNodeCount

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

यह विलोपन को $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.