রেড-ব্ল্যাক ট্রি হল একটি সেলফ-ব্যালেন্সড বাইনারি সার্চ ট্রি যেখানে ট্রির প্রতিটি নোড হয় রেড বা ব্ল্যাক রঙে রঙিন। রেড-ব্ল্যাক ট্রিতে আমরা তিন ধরনের অপারেশন পারফর্ম করতে পারি − সার্চিং, ইন্সারশন এবং ডিলিশন।
ধরি আমাদের নিচের রেড-ব্ল্যাক ট্রিতে একটি উপাদান ইন্সার্ট করতে হবে।
রেড-ব্ল্যাক ট্রিতে একটি উপাদান ইন্সার্ট করার ধারণা খুব সহজ − আমরা ঠিক যেমন রেগুলার বাইনারি ট্রিতে ইন্সার্ট করি তেমনই করি। আমরা রুট নোড থেকে শুরু করে নোডের রঙ চেক করে একটি নির্দিষ্ট পজিশনে ইন্সার্ট করি। যাইহোক, রেড-ব্ল্যাক ট্রিতে একটি উপাদান ইন্সার্ট করার জন্য কিছু অতিরিক্ত প্রসেস রয়েছে।
যাইহোক, আমাদের জানা উচিত যে একটি রেড-ব্ল্যাক ট্রি ব্যালেন্সড থাকে যখন এটি নিচের শর্তগুলো মেনে চলে −
প্রতিটি রুট নোড ব্ল্যাক হতে হবে।
প্রতিটি নোড হয় রেড অথবা ব্ল্যাক।
যদি একটি নোড রেড হয়, তবে তার চাইল্ডগুলো ব্ল্যাক হতে হবে।
রুট থেকে শেষ পর্যন্ত পথে সমান সংখ্যক ব্ল্যাক নোড থাকতে হবে।
যদি আমরা একটি নতুন নোড রেড-ব্ল্যাক ট্রিতে ইন্সার্ট করতে চাই, তবে আমরা ইন্সারশন ধাপগুলো দেখে করতে পারি।
রেড-ব্ল্যাক ট্রিতে উপাদান ইন্সার্ট করার ধাপ −
চেক করুন ট্রি খালি কিনা। যদি ট্রি খালি হয়, তবে একটি নতুন নোড ইন্সার্ট করুন এবং সেটিকে ব্ল্যাক রঙ দিন। (কারণ রুট নোড সবসময় ব্ল্যাক হতে হবে)
অন্যথায় যদি ট্রি খালি না হয়, তবে নতুন নোডটি লিফ নোড হিসেবে শেষে ইন্সার্ট করুন এবং সেটিকে রেড রঙ দিন।
যদি নতুন নোডের পেরেন্ট রেড হয় এবং তার নেighbour (পেরেন্টের) নোডও রেড হয় তবে উভয় নেighbour এবং পেরেন্ট এবং গ্র্যান্ডপেরেন্টের রঙ ফ্লিপ করুন (যদি সেটি রুট নোড না হয় অন্যথায় শুধু পেরেন্ট এবং নেighbour-এর রঙ ফ্লিপ করুন) অর্থাৎ ব্ল্যাক করুন।
যদি নতুন নোডের পেরেন্ট রেড হয় এবং তার নেighbour (পেরেন্টের) নোড খালি বা NULL হয়, তবে নতুন নোড এবং পেরেন্টকে রোটেট করুন (লেফট-লেফট বা লেফট-রাইট রোটেশন)।
দুটি ধরনের রোটেশন প্রয়োগ করা হবে- লেফট-লেফট রোটেশন এবং লেফট-রাইট রোটেশন। রোটেশন কিছু শর্তে প্রয়োগ করা হবে। শর্তগুলো হল −
যদি নতুন নোডের পেরেন্ট রেড হয় এবং নেighbour নোড খালি বা 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
