रेड-ब्लैक ट्री में तत्वों का समावेश

परिचय

• रेड-ब्लैक ट्री के तत्वों को सम्मिलित करने की प्रक्रिया पर चर्चा।
• पिछले वीडियो में रेड-ब्लैक ट्री की विशेषताओं पर चर्चा की गई थी।

मूल सिद्धांत

• न्यू नोड को सम्मिलित करते समय उसका रंग हमेशा रेड होता है।
• यदि नया नोड रूट है, तो उसका रंग ब्लैक होना चाहिए।

उदाहरण: तत्वों का समावेश

1. पहला तत्व (10)
   • रंग: ब्लैक (क्योंकि यह रूट है)
2. दूसरा तत्व (20)
   • रंग: रेड
   • कोई रेड-रेड का संघर्ष नहीं है।
3. तीसरा तत्व (30)
   • रंग: रेड
   • रेड-रेड का संघर्ष है।
   • चाचा (uncle) का रंग चेक करें।
   • यदि चाचा का रंग ब्लैक है या नल है तो रोटेशन करें और री-कलरिंग करें।

संघर्ष के प्रकार

केस 1: Uncle का रंग ब्लैक

• नोड को रोटेट करें और रंग बदलें।

केस 2: Uncle का रंग रेड

• माता-पिता और चाचा के रंग को ब्लैक करें।
• दादा का रंग रेड करें।

अन्य तत्वों का सम्मिलित करना

• 15: रेड-रेड संघर्ष, चाचा चेक करें।
• 25: कोई संघर्ष नहीं है।
• 5: कोई संघर्ष नहीं है।
• 12: रेड-रेड संघर्ष, चाचा चेक करें।
• 35: कोई संघर्ष नहीं है।
• 40: रेड-रेड संघर्ष, चाचा चेक करें।
• 32: कोई संघर्ष नहीं है।
• 50: रेड-रेड संघर्ष, चाचा चेक करें।

संतुलन और ऊँचाई

• रेड-ब्लैक ट्री हमेशा संतुलित रहता है और इसकी ऊँचाई log(n) होती है।
• यदि n = 12, तो ऊँचाई 4 होगी।

निष्कर्ष

• रेड-ब्लैक ट्री का समावेश सरल और प्रभावी है।
• हमेशा याद रखें कि सभी नियमों का पालन करें ताकि ट्री संतुलित बना रहे।

नोट्स

• हमेशा सुनिश्चित करें कि रूट हमेशा ब्लैक हो।
• सभी संघर्षों को चेक करने के बाद ही आगे बढ़ें।
• रोटेशन और री-कलरिंग प्रक्रिया को सही से समझें।

धन्यवाद!