std :: नक्शे में जाना जाता है-स्थिति मिटाएं परिशोधित जटिलता और लाल-काले ट्री Recolorings

Question

की संख्या std::map::erase(iterator) की जटिलता परिशोधित है हे (1) (here देखते हैं, उदाहरण के लिए)। जबकि मानक पुस्तकालय कार्यान्वयन को निर्देशित नहीं करता है, यह वास्तविक तथ्य यह है कि लाल-काले पेड़ के लिए पुनर्विक्रय संचालन की संख्या को ओ (1) को अमूर्त किया गया है। वास्तव में, लाल-काले पेड़ों seems to confirm this पर विकिपीडिया प्रविष्टि:

लाल-काले गुण पुनर्स्थापित कर रहा है एक छोटी संख्या की आवश्यकता है (ओ (लॉग n) या परिशोधित हे (1)) रंग में परिवर्तन के (बहुत जल्दी कर रहे हैं जो अभ्यास में) और तीन पेड़ घूर्णन (सम्मिलन के लिए दो) से अधिक नहीं।

लेकिन प्रतीत होता है कि एक लिंक के बिना (और मुझे इसे अन्य स्थानों में नहीं मिला)।

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

Answer 1

मैं इस जवाब में मानता हूं कि आप अमूर्त विश्लेषण से परिचित हैं और बैंकर की विधि से सहज हैं। मैं आपको लाल-काले पेड़ के आविष्कारों को भी मानूंगा।

संक्षिप्त उत्तर कुछ छोटे स्थिर के लिए है, हर काले नोड पर के सिक्के डाल दें जिसमें बिल्कुल एक लाल बच्चा नहीं है।

ध्यान दें कि लाल-काले पेड़ में हटाने के लिए कई अलग-अलग एल्गोरिदम हैं। एक इटरेटर के साथ मिटाने के लिए स्पष्ट रूप से नीचे-नीचे एल्गोरिदम की आवश्यकता होती है। विश्लेषण यहाँ मानता है कि एल्गोरिथ्म मोटे तौर पर करता है इस प्रकार है:

1. Traverse ऊपर की ओर जब तक एक काले रंग की नोड पाया जाता है। यह हमेशा संभव है, चूंकि जड़ काला है, और इसमें दो से अधिक हॉप नहीं लगते हैं क्योंकि लाल नोड्स में लाल बच्चे नहीं हो सकते हैं।

2. उस काले नोड पर रूट किए गए उपट्री पर ओ (1) समय में "फिक्सअप" ऑपरेशन करें। यदि फिक्सअप उपट्री की ऊंचाई को कम करता है या रूट के रंग को काले से लाल रंग में बदल देता है, तो रूट की तरफ एक और कदम पार करें और # 1 पर वापस जाएं।

यह देखने के लिए कुछ काम लगता है कि # 2 संभव है। वास्तव में, इसकी जटिलता सेडगेविक के बाएं झुकाव वाले लाल-काले पेड़ के लिए प्रेरणाओं में से एक है। यह ज्यादातर मामलों को गिनने का सवाल है, एक सिंगल या डबल रोटेशन कर रहा है, फिर ध्यान से जांच कर रहा है कि आपने किसी भी इनवेरिएंट का उल्लंघन नहीं किया है।

Fixup आपरेशन से एक संस्करण (है कि यदि आप पहले से ही किसी अन्य मान्य संस्करण है खोजने के लिए कठिन नहीं है) ट्रेवर्सल ऊपर पेड़ के दौरान दो अतिरिक्त अपरिवर्तनशीलताओं को बरकरार रखता है:

1. जब ऊंचाई उपट्री के 1 से कम हो जाता है, उपट्री (ए) की मूल रूप से दो काले बच्चे (बी) में वास्तव में एक लाल बच्चा होता है।

2. उपखंड कभी काला से लाल रंग में नहीं बदलता है।

इस प्रकार, ट्रेवर्सल के हर कदम, के लिए या तो

1. सबट्री की जड़ एक या दो लाल बच्चे हैं। हम ओ (1) काम करते हैं, अधिकतर ओ (1) सिक्कों को जोड़ते हैं, और

2. हम ओ (1) काम करते हैं, दो काले बच्चों के साथ नोड को बदलकर ओ (1) सिक्के वापस प्राप्त करें एक लाल बच्चे, और साथ नोड जारी रखने के

प्रकरण # 2 परिशोधित मुक्त, जब तक सिक्कों की संख्या काफी बड़ी पुनर्गठन की लागत को कवर करने के लिए है के रूप में और # 2 मामले में recoloring है। इस प्रकार, डिलीट की कुल अमूर्त लागत एक ही डिलीवरी ऑपरेशन में केस # 1 को हिट करने की संख्या है, जो कि सबसे अधिक है, क्योंकि जब हम इसे दबाते हैं तो हम रुक जाते हैं।

---

हालांकि यह स्पष्टीकरण की गणित की प्रक्रिया को कवर, यह वास्तव में स्पष्ट नहीं होता क्यों हटाना परिशोधित है हे (1)।

छात्रों को कभी-कभी अमूर्त लागत के बारे में सिखाया जाता है, यह बाइनरी संख्याओं को बढ़ाने का मामला है। सबसे खराब मामले में लागत Ω (एलजी एन) है, लेकिन ओ (1) अमूर्त अर्थ में, प्रत्येक '1' अंक पर लगातार संख्या में सिक्के डालकर।

इसी प्रकार, प्रत्येक '0' अंकों पर लगातार संख्या में सिक्के डालकर एम (1) को कम किया गया है। हालांकि, दोनों मिश्रणों को प्रत्येक लागत Ω (एलजी एन) बनाता है, यहां तक ​​कि एक अमूर्त सेटिंग में भी, क्योंकि अमूर्त विश्लेषण सभी ट्रैवर्सल चरणों पर निर्भर करता है, आखिरकार सिक्कों की निरंतर संख्या को छोड़कर।

यह ट्रैवर्सल-फ्री-बाय-यू-स्टॉप थीम उपरोक्त लाल-काले पेड़ विश्लेषण के समान है। अंक जो सिक्के को रखा जाना चाहिए वे अंक हैं जो संरचनात्मक समायोजन का प्रतिनिधित्व करते हैं जो बनने वाले हैं। भौतिक विज्ञानी की विधि का उपयोग करके, इस तरह के प्रत्येक अंक के लिए संरचना में संभावित ऊर्जा को जोड़ा जाता है।

बाइनरी संख्याओं के एक अलग प्रतिनिधित्व पर विचार करें जिसमें अंक 0, 1, या 2 हो सकते हैं (लेकिन अंक d_i अभी भी d_i * 2^i का प्रतिनिधित्व करता है)। इसे अनावश्यक बाइनरी कहा जाता है। अब, आप सभी 0 या 2 अंकों पर लगातार संख्या में सिक्के रख सकते हैं और निरंतर निरंतर समय वृद्धि और कमी प्राप्त कर सकते हैं। इसका कारण यह है कि एक कैस्केडिंग वृद्धि या कमी 0s या 2s से 1s में बदल जाती है, और इसलिए हमेशा सिक्कों को वापस ले जाता है।

तो, दो अंकों के साथ, वृद्धि या कमी ओ (1) amortized है, लेकिन दोनों नहीं, और तीन के साथ, दोनों ओ (1) amortized किया जा सकता है।

इसी तरह, या तो प्रविष्टि या विलोपन (लेकिन दोनों) परिशोधित है हे (1) के सभी में:

1. लाल-काले पेड़ों जिसमें काला नोड्स केवल एक लाल बच्चे

2. हो सकता है

   ए.ए. पेड़

3. 2-3 पेड़

4. (एक, 2 ए -1) पेड़, किसी भी एक> 1 के लिए।

हालांकि ये दोनों ही प्रविष्टि और विलोपन हे (1) लाल काला पेड़ों में परिशोधित, (2,4) पेड़ हैं, और (एक, 2 ए) किसी भी एक> 1.