लाल-काले पेड़ संतुलन - तीन मामले

बाइनरी सर्च ट्री त्वरित खोज क्षमताओं के साथ वस्तुओं को संग्रहीत करने के लिए एक डेटा संरचना है। विचार सरल और सरल है: "कम बचा है, अधिक सही है।" यह वह जगह है जहां सादगी समाप्त होती है और एक पेड़ को संतुलित करने के जटिल प्रश्न शुरू होते हैं ताकि यह एक लंबी शाखा में बदल न जाए।

---

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



लाल-काला पेड़ एक स्व-संतुलन द्विआधारी खोज पेड़ है जो नोड्स की संख्या से पेड़ की ऊंचाई के लघुगणक विकास और खोज पेड़ के बुनियादी संचालन के त्वरित निष्पादन की गारंटी देता है: एक नोड को जोड़ना, हटाना और खोजना।

लाल-काला पेड़ पूरी तरह से संतुलित नहीं है, कुछ स्थानों पर इसकी ऊंचाई लगभग दो बार भिन्न हो सकती है। इस तरह की धारणा तत्वों की खोज की गति को असामयिक रूप से प्रभावित नहीं करती है, लेकिन नए तत्वों की नियुक्ति में महत्वपूर्ण रूप से तेजी लाती है, क्योंकि आपको हर बार तत्वों को जोड़ने के लिए पेड़ को "हिला" करने की आवश्यकता नहीं होती है, कभी-कभी यह दूसरों को स्पर्श किए बिना और "काली ऊंचाई" बदले बिना लाल तत्व जोड़ने के लिए पर्याप्त नहीं है। ।

तत्वों को लाल-काले पेड़ में रखने के नियम

1. प्रत्येक नोड या तो लाल या काला होता है; NIL के पत्ते हमेशा काले होते हैं।
2. पेड़ की जड़ हमेशा काली होती है
3. प्रत्येक लाल नोड के दोनों वंशज काले हैं
4. किसी भी नोड से किसी भी वंशज पत्ती के नीचे के मार्ग में समान संख्या में काले नोड होते हैं।

जब आप एक नया तत्व सम्मिलित करते हैं, तो उसे एक लाल रंग दिया जाता है। पहले दो नियमों को पूरा करने के लिए, बस वांछित रंगों में नए सिरे को दोहराएं।

3 और 4 अंक के कार्यान्वयन के लिए संतुलन नियमों पर विचार करें।
प्रत्येक आंकड़े में, यह माना जाता है कि हमने पहले ही एक तत्व एक्स को जोड़ दिया है जो 3 नियम का उल्लंघन करता है, हमें पेड़ की संरचना को बदलने की आवश्यकता है ताकि 3 नियम निष्पादित हो, और 4 का उल्लंघन न हो।

कोने की किंवदंती:

• एक्स - एक जोड़ा तत्व जो नियमों के 3 पैराग्राफ का उल्लंघन करता है।
• पी - डैड आइटम एक्स
• जी - तत्व एक्स के दादा, तत्व पी के पिता
• U तत्व X का चाचा है, तत्व P का भाई, तत्व G का दूसरा पुत्र है।

केस एक - लाल अंकल

यदि पिता और चाचा दोनों लाल हैं, तो हम दादाजी के स्तर से पिता के स्तर तक काले रंग को "कम" कर सकते हैं और नोड्स को फिर से दिखा सकते हैं, जैसा कि आंकड़े में दिखाया गया है। इस मामले में, "काली ऊंचाई" समान रहेगी, हालांकि, तत्व जी के लिए नियम 3 का उल्लंघन संभव है, इसलिए, इस नोड के लिए आगे संतुलन को फिर से कॉल करना आवश्यक है।

केस दो - एक काले चाचा - अलग-अलग दिशाओं में पिताजी और दादा।

इस संरचना को तीसरे मामले में लाया जाना चाहिए, जब पिताजी और दादा एक ही दिशा में जाते हैं। ऐसा करने के लिए, आपको बेटे एक्स से उसके पिता के लिए एक छोटा मोड़ बनाने की जरूरत है (इस आलेख में घुमाव के नियमों पर विचार नहीं किया गया है) और तत्व आर के लिए 3 मामलों को कॉल करें।

केस थ्री - ब्लैक अंकल - एक ही तरफ डैड और दादा

इस मामले में, हम पहले से ही दादा के माध्यम से पिता से काले चाचा और काले और जी में लाल रंग में पी से बड़ा बदलाव कर सकते हैं। इस रोटेशन के परिणामस्वरूप, 3-नियम संतुष्ट हो जाएगा।

सुनिश्चित करें कि 4 वां नियम भी संतुष्ट है। मान लीजिए कि बड़े मोड़ से पहले, तत्व G की काली ऊंचाई N + 2 थी। फिर "निलंबित" तत्वों की ऊंचाई इस प्रकार होगी:

ए = एन + 1,
बी = एन + 1,
सी = एन + 1,
डी = एन
ई = एन।

खुद के लिए देखें कि सभी नियमों के लिए 4-नियम को चालू करने के बाद।

ठोस उदाहरण

अब हम तत्वों 1, 2, 3, 4, 5 और 6 के अनुक्रमिक सम्मिलन के साथ लाल-काले पेड़ बनाने की प्रक्रिया पर विचार करेंगे।



चूंकि तत्व 1 मूल है, हम नियम 1 को पूरा करने के लिए इसे केवल दोहराते हैं।



तत्व 2 को जोड़ने के बाद, सभी नियमों को निष्पादित किया जाता है।



तत्व 3 को जोड़ते समय, हमने नियम 3 का उल्लंघन किया। चूंकि हमारे एक हाथ में एक काला चाचा, और दादा और पिता हैं, इसलिए हम तीसरे मामले का उपयोग करते हैं - हम एक मोड़ और दमनकारी बनाते हैं।



तत्व 4 को जोड़ते समय, हमने फिर से नियम 3 का उल्लंघन किया। इस बार हमारे चाचा लाल हैं, इसलिए हम पहले मामले को निरस्त करने के साथ लागू करते हैं - पेड़ की काली ऊंचाई में वृद्धि होगी 1. कृपया ध्यान दें। यह कि एल्गोरिथ्म को दादाजी के लिए अतिरिक्त रूप से लॉन्च किया गया है - तत्व 2, जो जड़ की तरह, बस काले रंग में पुन: अंकित है।



तत्व 5 को सम्मिलित करते समय, हम फिर से 3 केस लगाते हैं - हम एक बड़ा मोड़ बनाते हैं और कोने को दोहराते हैं। ध्यान दें कि काली ऊंचाई नहीं बदली है।



तत्व 6 को जोड़ते समय, हमने फिर से नियम 3 का उल्लंघन किया। चूंकि हमारे चाचा लाल हैं, हम पहले मामले को दोहराते हुए लागू करते हैं, काली ऊंचाई नहीं बदली है। 4 तत्वों के लिए संतुलन कॉल ने पेड़ में कुछ भी नहीं बदला, क्योंकि यह तत्व नियमों का उल्लंघन नहीं करता है।

इसलिए, हम लाल-काले पेड़ को संतुलित करने के मुद्दों से परिचित हुए, अधिक विस्तार से और इस विषय के एल्गोरिदम के उदाहरणों के साथ-साथ अन्य द्विआधारी खोज पेड़ों की किस्मों के साथ, हम पाठ्यक्रम "डेवलपर्स के लिए एल्गोरिदम" पर विचार करते हैं।