রেড-ব্ল্যাক ট্রি (Red-Black Tree)
রেড-ব্ল্যাক ট্রি (Red-Black Tree) হলো এমন এক ধরনের সেলফ-ব্যালান্সিং বাইনারি সার্চ ট্রি (BST), যার প্রতিটা নোডে একটু বাড়তি তথ্য সেভ করা থাকে: আর সেটা হলো তার রঙ (color) — লাল অথবা কালো। এই রঙের সিস্টেমটার ভেতরেই এমন কিছু কড়া নিয়ম বা শর্ত লুকিয়ে আছে, যার কারণে ট্রি-টা কখনো একদিকে খুব বেশি হেলে পড়তে বা একদিকে লম্বা হয়ে যেতে পারে না।
বাস্তব দুনিয়ায় যত ধরনের অর্ডারিং ম্যাপ বা সেট (Ordered map/set) আছে, প্রায় সবকিছুরই ইঞ্জিন হিসেবে ভেতরে ভেতরে এই রেড-ব্ল্যাক ট্রি কাজ করে। উদাহরণস্বরূপ: java.util.TreeMap, সি++ (C++)-এর std::map, লিনাক্সের CFS scheduler, এমনকি nginx সার্ভারের টাইমার ম্যানেজমেন্টেও এই রেড-ব্ল্যাক ট্রি ব্যবহার করা হয়।
৫টা কড়া নিয়ম বা শর্ত
একটা জেনুইন রেড-ব্ল্যাক ট্রিতে নিচের এই ৫টা নিয়ম ১০০% মানতে হবে:
- প্রতিটি নোড হয় লাল হবে, নয়তো কালো হবে।
- মাথা বা রুট (Root) নোড সবসময় কালো হবে।
- সবগুলো পাতা (leaf) বা একেবারে শেষের নাল (null) নোডগুলো কালো হবে।
- যদি কোনো নোড লাল হয়, তবে তার দুটো বাচ্চাই অবশ্যই কালো হতে হবে। (অর্থাৎ, পরপর দুটো নোড কখনো লাল হতে পারবে না।)
- যেকোনো নোড থেকে নিচের দিকের যেকোনো পাতা (null leaf) পর্যন্ত যানয়ার সময় পথে সমান সংখ্যক কালো নোড পড়তে হবে। এই গুনে গুনে কালো নোড পাওয়ার সংখ্যাটাকে বলে ব্ল্যাক-হাইট (black-height)।
এই ৪ নম্বর আর ৫ নম্বর নিয়মটা একসাথে মিলে এই গ্যারান্টি দেয় যে, ট্রির সবচেয়ে লম্বা রুটটা কোনোভাবেই সবচেয়ে ছোট রুটের দ্বিগুণের (2x) বেশি লম্বা হতে পারবে না। এতে ট্রি-টা প্রায়-ব্যালান্সড থাকে এবং স্পিড সবসময় O(log n)-এর ঘরেই আটকে থাকে।
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
নতুন কিছু ঢোকানো বা ইনসার্ট করা
রেড-ব্ল্যাক ট্রিতে নতুন কাউকে ঢোকালে সে সবসময় লাল হয়েই ঢোকে। এতে অনেক সময় ৪ নম্বর নিয়মটা ভেঙে যায় (কার বাপও হয়তো লাল ছিল)। তখন তিনভাবে এই ভেজাল মেটানো যায়:
- চাচা বা আঙ্কেল যদি লাল হয় — বাপ আর চাচার রঙ পাল্টে কালো করে দিতে হয়, আর দাদুর রঙ করে দিতে হয় লাল। এতে ভেজালটা বাপের ওপর দিয়ে দাদুর ঘাড়ে আর ওপরের দিকে চলে যায়।
- চাচা যদি কালো হয় (ত্রিভুজ বা triangle কেস হলে) — বাপকে ধরে এমনভাবে ঘোরাতে বা রোটেট (rotate) করতে হয়, যাতে তারা এক লাইনে চলে আসে।
- চাচা যদি কালো হয় (লাইন বা line কেস হলে) — দাদুকে ধরে ঘোরাতে হয় এবং বাপ আর দাদুর রঙ অদলবদল করে দিতে হয়।
এই রঙ বদলানো আর ঘোরাঘুরির কাজটা বড়জোর ট্রির মাথা পর্যন্ত বা O(log n)-বার যায়, তাই ইনসার্ট করার মোট সময় O(log n)-ই থাকে।
রেড-ব্ল্যাক বনাম এভিএল (AVL): কোনটা ভালো?
দুটোই সব কাজে O(log n) গ্যারান্টি দেয়। কিন্তু বাস্তব পার্থক্য হলো:
- এভিএল ট্রি (AVL Tree) অনেক বেশি কষে ব্যালান্সড (উচ্চতা ≤ 1.44 log n, আর রেড-ব্ল্যাকের 2 log n)। তাই খুঁজলে বা সার্চ করলে একটু বেশি ফাস্ট উত্তর পাওয়া যায়। কিন্তু নতুন কিছু ঢোকাতে বা ডিলিট করতে গেলে তাকে বারবার রোটেট করতে হয়।
- রেড-ব্ল্যাক ট্রি ইনসার্ট বা ডিলিটের সময় অনেক কম রোটেশন করে (সর্বোচ্চ ৩ বার, যেখানে এভিএলে O(log n) বার লাগতে পারে)। তাই লেখার কাজ (write) অনেক ফাস্ট হয়। যেসব জায়গায় বারবার ডেটা ঢোকাতে হয়, সেখানে এটাই বেস্ট।
সাধারণ অ্যাপ বা সফ্টওয়্যারে খোঁজা এবং লেখা দুটোরই মিক্স থাকে বলে, রেড-ব্ল্যাক ট্রিই সবচেয়ে বেশি পছন্দের — এ কারণেই স্ট্যান্ডার্ড লাইব্রেরিগুলোতে এর এত রাজত্ব।
ব্ল্যাক-হাইট (Black-height) এবং ব্যালান্সিং-এর গ্যারান্টি
ট্রির ব্ল্যাক-হাইট মানে হলো মাথা থেকে পাতা পর্যন্ত যানয়ার পথে কয়টা কালো নোড পড়ল তার সংখ্যা (অবশ্য মাথা বা রুটকে বাদ দিয়ে গোনা হয়)। যেহেতু সব পথের ব্ল্যাক-হাইট সমান হতে হবে (৫ নম্বর নিয়ম), এবং পরপর দুটো লাল নোড বসতে পারবে না (৪ নম্বর নিয়ম), তাই চাইলেও ট্রির মোট উচ্চতা ২ × ব্ল্যাক-হাইট-এর চেয়ে বেশি করা সম্ভব না।
Complexity
ছোট কুইজ
পড়া চালিয়ে যান