ডেটা স্ট্রাকচারে লাল কালো গাছের সন্নিবেশ

রেড ব্ল্যাক ট্রি হল একটি স্ব-ভারসাম্যপূর্ণ বাইনারি সার্চ ট্রি যেখানে গাছের প্রতিটি নোড লাল বা কালো দিয়ে রঙিন করা হয়। লাল কালো গাছে আমরা তিন ধরনের অপারেশন করতে পারি – অনুসন্ধান, সন্নিবেশ এবং মুছে ফেলা।

ধরুন আমাদের নিচের লাল কালো গাছে একটি উপাদান সন্নিবেশ করতে হবে।

একটি লাল-কালো গাছে একটি উপাদান সন্নিবেশ করার ধারণাটি খুবই সহজ - আমরা একটি নিয়মিত বাইনারি গাছের মতোই সন্নিবেশ করি। আমরা নোডের রঙ পরীক্ষা করে রুট নোড থেকে শুরু করি এবং একটি নির্দিষ্ট অবস্থানে প্রবেশ করি। যাইহোক, একটি লাল-কালো গাছে একটি উপাদান সন্নিবেশ করার জন্য কিছু অতিরিক্ত পদ্ধতি থাকা উচিত।

যাইহোক, আমাদের জানা উচিত যে একটি লাল-কালো গাছ ভারসাম্যপূর্ণ হয় যখন এটি শর্তগুলি অনুসরণ করে -

• প্রতিটি রুট নোড কালো হতে হবে।

• প্রতিটি নোড হয় লাল বা কালো।

• যদি একটি নোড লাল হয়, তাহলে এর বাচ্চাদের অবশ্যই কালো হতে হবে।

• রুট থেকে শেষ পর্যন্ত পাথে অবশ্যই সমান সংখ্যক কালো নোড থাকতে হবে।

আমরা যদি একটি লাল-কালো গাছে একটি নতুন নোড সন্নিবেশ করতে চাই, তাহলে আমরা সন্নিবেশের ধাপগুলি দেখে তা করতে পারি৷

একটি লাল কালো গাছে একটি উপাদান সন্নিবেশ করার পদক্ষেপগুলি -

• গাছটি খালি আছে কি না তা পরীক্ষা করুন। যদি গাছটি খালি থাকে তবে একটি নতুন নোড প্রবেশ করান এবং এটিকে কালো হিসাবে রঙ করুন। (কারণ রুট নোড সবসময় কালো রঙের হতে হবে)’

• অন্যথায় যদি গাছটি খালি না থাকে তবে নতুন নোডটিকে একটি পাতার নোড হিসাবে শেষ পর্যন্ত প্রবেশ করান এবং এটিকে লাল রঙ করুন৷

• যদি নতুন নোডের অভিভাবক লাল হয় এবং এর প্রতিবেশী (পিতামাতার) নোডটিও লাল হয় তবে প্রতিবেশী এবং পিতামাতা এবং দাদা-দাদি উভয়ের রঙটি ফ্লিপ করুন (যদি এটি রুট নোড না হয় অন্যথায় শুধুমাত্র পিতামাতা এবং প্রতিবেশীর রঙ ফ্লিপ করুন) যেমন। , কালো।

• যদি নতুন নোডের প্যারেন্ট লাল হয় এবং এর প্রতিবেশী (পিতামাতার) নোড খালি বা 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