रेड ब्लैक ट्री एक सेल्फ-बैलेंस्ड बाइनरी सर्च ट्री (Self-Balanced Binary Search Tree) है जिसमें ट्री के प्रत्येक नोड को या तो लाल (Red) या काले (Black) रंग से रंगा जाता है। रेड ब्लैक ट्री पर हम तीन प्रकार के संक्रियाएँ कर सकते हैं - खोज, सम्मिलन और विलोपन।
मान लीजिए हमें निम्नलिखित रेड ब्लैक ट्री में एक तत्व सम्मिलित करना है।
रेड-ब्लैक ट्री में एक तत्व सम्मिलित करने का विचार बहुत सरल है - हम सम्मिलन ठीक वैसे ही करते हैं जैसे हम एक नियमित बाइनरी ट्री में सम्मिलित करते हैं। हम रूट नोड से शुरू करके नोड के रंग की जांच करते हैं और इसे एक विशेष स्थान पर सम्मिलित करते हैं। हालांकि, रेड-ब्लैक ट्री में एक तत्व सम्मिलित करने के लिए कुछ अतिरिक्त प्रक्रिया होनी चाहिए।
हमें पता होना चाहिए कि एक रेड-ब्लैक ट्री संतुलित होता है जब यह शर्तों का पालन करता है:
प्रत्येक रूट नोड काला होना चाहिए।
प्रत्येक नोड या तो लाल या काला होता है।
यदि एक नोड लाल है, तो उसके बच्चे काले होने चाहिए।
रूट से अंत तक का पथ में समान संख्या में काले नोड्स होने चाहिए।
यदि हम रेड-ब्लैक ट्री में एक नया नोड सम्मिलित करना चाहते हैं, तो हम सम्मिलन चरणों को देखकर ऐसा कर सकते हैं।
रेड ब्लैक ट्री में एक तत्व सम्मिलित करने के चरण –
जांचें कि ट्री खाली है या नहीं। यदि ट्री खाली है, तो एक नया नोड सम्मिलित करें और इसे काले रंग से रंगें। (क्योंकि रूट नोड हमेशा काले रंग का होना चाहिए)
अन्यथा यदि ट्री खाली नहीं है तो नए नोड को अंत में पत्ती नोड के रूप में सम्मिलित करें और इसे लाल रंग से रंगें।
यदि नए नोड का माता-पिता लाल है और उसका पड़ोसी (माता-पिता का) नोड भी लाल है तो दोनों पड़ोसी और माता-पिता और दादा-दादी (यदि यह रूट नोड नहीं है अन्यथा केवल माता-पिता और पड़ोसी का रंग बदलें) यानी काले रंग का करें।
यदि नए नोड का माता-पिता लाल है और उसका पड़ोसी (माता-पिता का) नोड खाली या NULL है, तो नए नोड और माता-पिता को घुमाएं (या तो बाएं-बाएं या बाएं-दाएं घुमाव)।
दो प्रकार के घूर्णन लागू होंगे - बाएं-बाएं घुमाव और बाएं-दाएं घुमाव। घुमाव केवल कुछ शर्तों में लागू होगा। शर्तें हैं:
यदि नए नोड का माता-पिता लाल है और पड़ोसी नोड खाली या NULL है, तो बाएं या दाएं घुमाव करें।
बाएं-बाएं घुमाव में माता-पिता और दादा-दादी का रंग बदलें। माता-पिता को दादा-दादी बनाएं और दादा-दादी को बच्चा बनाएं।
एल्गोरिदम
RBTreeInsertion(root,key)
// सम्मिलित नए नोड का रंग लाल है
color[key] <- Red
while(key ≠ root and color(p[key]) = Red) do
if p[key] = left(p[p[key]])
Then y ← right[p[p[key]] // यदि नए नोड का माता-पिता लाल है (यदि रूट नोड के बजाय दादा-दादी है) रंग बदलें।
if color[y] = Red
then color(p[key]) ← Black
color(p[p[key]]) ← Red
key ← p[p[key]]
else if key = right[p[key]]
then key ← p[key]
// जब नए नोड का माता-पिता लाल रंग का है और उसका सहोदर NULL है
LeftRotate(root,key)
color(p[key]) ← Black
color(p[p[key]]) ← Red
RotateRight(root,p[p[key]])
else left और right तत्वों का आदान-प्रदान करें ताकि यह संतुलित हो जाए।
color(root) ← Black
