डेटा स्ट्रक्चर में रेड ब्लैक ट्री में इंसर्शन

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

मान लें कि हमें निम्नलिखित लाल काले पेड़ में एक तत्व डालना है।

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

हालांकि, हमें पता होना चाहिए कि एक लाल-काला पेड़ तभी संतुलित होता है जब वह शर्तों का पालन करता है -

• प्रत्येक रूट नोड काला होना चाहिए।

• प्रत्येक नोड या तो लाल या काला होता है।

• यदि कोई नोड लाल है, तो उसके बच्चे काले होने चाहिए।

• जड़ से अंत तक के पथ में समान संख्या में काले नोड होने चाहिए।

यदि हम लाल-काले पेड़ में एक नया नोड सम्मिलित करना चाहते हैं, तो हम सम्मिलन चरणों को देखकर कर सकते हैं।

लाल काले पेड़ में तत्व डालने के चरण -

• जांचें कि पेड़ खाली है या नहीं। यदि पेड़ खाली है, तो एक नया नोड डालें और इसे काले रंग में रंग दें। (क्योंकि रूट नोड हमेशा काले रंग का होना चाहिए)'

• अन्यथा यदि ट्री खाली नहीं है तो नए नोड को लीफ नोड के रूप में अंत तक डालें और इसे लाल रंग में रंग दें।

• यदि नए नोड का माता-पिता लाल है और उसके पड़ोसी (माता-पिता) का नोड भी लाल है, तो दोनों पड़ोसी और माता-पिता और दादा-दादी का रंग पलटें (यदि यह रूट नोड नहीं है अन्यथा केवल माता-पिता और पड़ोसी का रंग पलटें) यानी। , काला।

• अगर नए नोड का पैरेंट लाल है और उसके पड़ोसी (पैरेंट का) नोड खाली या NULL है, तो नए नोड और पैरेंट को घुमाएं (बाएं-बाएं या बाएं-दाएं रोटेशन)।

दो प्रकार के रोटेशन हैं जो लागू होंगे- लेफ्ट लेफ्ट रोटेशन और लेफ्ट राइट रोटेशन। रोटेशन कुछ शर्तों में ही लागू होगा। शर्तें हैं -

• यदि नए नोड का पैरेंट लाल है और पड़ोसी नोड खाली या NULL है, तो बाएँ या दाएँ घुमाएँ।

• बाएँ-बाएँ घुमाव में माता-पिता और दादा-दादी का रंग फ़्लिप करें। माता-पिता को दादा-दादी और दादा-दादी को बच्चा बनाएं।

एल्गोरिदम

RBTreeInsertion(root, key)

//The color of the inserted new node is Red
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 the parent of the new node is Red(if there is Grandparent instead
root Node) Flip the color.
   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]
      //When parent of new node has the red color and its sibling is NULL
   LeftRotate(root,key)
   color(p[key]) ← Black
   color(p[p[key]]) ← Red
RotateRight(root,p[p[key]])
else exchange then left and right elements to make it balance.
color(root)← Black