Red-black tree আর ভারসাম্যপূর্ণ tree-এর তুলনা

১ · AVL-এর পরে আরেকটি নিয়ম কেন — “যথেষ্ট ভালো” ভারসাম্য

পর্ব ২৭-এ দেখেছেন, একটি সাধারণ binary search tree (BST) সাজানো ক্রমে ইনপুট পেলে একটি লম্বা লাঠির মতো হয়ে যায় — উচ্চতা n − 1, আর প্রতিটি খোঁজা O(n). পর্ব ২৮-এর AVL tree এর সমাধান দিয়েছে কঠোর একটি নিয়মে: প্রতিটি node-এর বাঁ আর ডান subtree-র উচ্চতার পার্থক্য সর্বোচ্চ ১। নিয়ম ভাঙলেই rotation করে ঠিক করা হয়।

AVL চমৎকার কাজ করে, কিন্তু তার কঠোরতার একটি দাম আছে। প্রতিটি insert বা delete-এর পর পথের প্রতিটি node-এর উচ্চতা হালনাগাদ করতে হয়, আর delete-এর পর rotation-এর একটি ঢেউ root পর্যন্ত চলতে পারে — সবচেয়ে খারাপ ক্ষেত্রে O(log n) টি rotation. যে প্রোগ্রামে প্রতি সেকেন্ডে লাখো insert আর delete হয় (যেমন operating system-এর scheduler, বা একটি ব্যস্ত সার্ভারের timer-তালিকা), সেখানে প্রশ্ন জাগে: এত নিখুঁত ভারসাম্য কি সত্যিই দরকার? যদি উচ্চতা “সর্বোচ্চ দ্বিগুণ” হলেও চলে, কিন্তু প্রতিটি পরিবর্তন সস্তা হয়?

এই “ঢিলেঢালা কিন্তু নিশ্চিত” ভারসাম্যই red-black tree-র মূল কথা। এটি একটি self-balancing BST: প্রতিটি node-এ শুধু একটি বাড়তি bit (লাল না কালো), উচ্চতা সবসময় 2 log₂(n+1)-এর মধ্যে, আর প্রতিটি insert-এ সর্বোচ্চ ২টি ও delete-এ সর্বোচ্চ ৩টি rotation. রং বদল (recoloring) কখনো কখনো ওপরের দিকে চলে, কিন্তু সেটি শুধু একটি bit উল্টানো — pointer বদলানোর চেয়ে অনেক সস্তা। এই কারণেই C++ আর Java-র লাইব্রেরি, আর Linux kernel — তিনটিই red-black tree বেছে নিয়েছে।

২ · পাঁচটি নিয়ম — লাল, কালো আর NIL

Red-black tree একটি সাধারণ BST — বাঁয়ে ছোট, ডানে বড় — যার প্রতিটি node-এ একটি রং আছে। CLRS-এর ধারায় একটি সুবিধাজনক কল্পনা করা হয়: যেখানে কোনো সন্তান নেই, সেখানে একটি কাল্পনিক “খালি leaf” বসানো, যাকে বলে NIL leaf. ফলে প্রতিটি আসল node-এর ঠিক দুটি সন্তান থাকে (আসল বা NIL), আর সব পথ শেষ হয় NIL-এ। বাস্তব কোডে NIL হয় nullptr/None, অথবা CLRS-এর মতো একটি একক কালো sentinel node.

পঞ্চম নিয়মের সংখ্যাটির একটি নাম আছে: black-height, লেখা হয় bh(x) — x থেকে নিচের যেকোনো NIL পর্যন্ত পথে কালো node-এর সংখ্যা, x-কে বাদ দিয়ে, NIL-কে ধরে। নিয়ম ৫ বলে এই সংখ্যা পথ বাছাইয়ের ওপর নির্ভর করে না, তাই সংজ্ঞাটি অর্থবহ। নিচের tree-টি দেখুন (R = লাল, B = কালো, ছোট NIL-গুলো কালো):

                  20B
               /       \
          10B             30B
         /    \          /    \
      5R       15R    25R      NIL
     /  \     /  \    /  \
   NIL  NIL NIL  NIL NIL  NIL

bh(20) = 2   যেমন পথ 20 → 10 → 5 → NIL:  কালো 10, NIL  = 2
             পথ 20 → 30 → NIL:          কালো 30, NIL  = 2
bh(10) = 1,  bh(30) = 1,  bh(5) = bh(15) = bh(25) = 1

লক্ষ করুন, পথগুলোর দৈর্ঘ্য আলাদা: 20 → 30 → NIL পথে মাত্র ২টি ধাপ, 20 → 10 → 5 → NIL পথে ৩টি। কিন্তু দুটিতেই কালো node ২টি — পার্থক্য তৈরি করছে শুধু লাল node. নিয়ম ৪ লাল node-এর সংখ্যা সীমিত রাখে: কোনো পথে লাল node কালো node-এর চেয়ে বেশি হতে পারে না, কারণ প্রতিটি লালের ঠিক নিচে একটি কালো আছে।

কোনটি বৈধ নয় — তিনটি সাধারণ ভুল

৩ · উচ্চতা কেন 2 log₂(n+1)-এর বেশি নয় — black-height দিয়ে প্রমাণ

পাঁচটি নিয়মের পুরো উদ্দেশ্য একটিই: উচ্চতা O(log n) রাখা। প্রমাণটি সুন্দর আর ছোট, আর বিশ্ববিদ্যালয় বা চাকরির লিখিত পরীক্ষায় প্রায়ই চাওয়া হয়। এখানে n = আসল (internal) node-এর সংখ্যা, NIL বাদে; আর h = root থেকে সবচেয়ে দূরের NIL পর্যন্ত edge-এর সংখ্যা।

দাবি ১ (induction): যেকোনো node x-এর subtree-তে কমপক্ষে 2^bh(x) − 1 টি আসল node আছে।

• ভিত্তি: x যদি NIL হয়, bh(x) = 0, আর 2⁰ − 1 = 0 — ঠিক, NIL-এর subtree-তে আসল node শূন্য।
• ধাপ: x একটি আসল node, bh(x) = b. x-এর প্রতিটি সন্তান c-এর black-height হয় b (c লাল হলে, কারণ c নিজে কালো গোনায় আসে না) অথবা b − 1 (c কালো হলে)। দুই ক্ষেত্রেই bh(c) ≥ b − 1. সন্তানের subtree x-এর চেয়ে ছোট, তাই induction-এর অনুমান অনুযায়ী প্রতিটিতে কমপক্ষে 2^b−1 − 1 টি node. x-কে যোগ করে মোট কমপক্ষে 2(2^b−1 − 1) + 1 = 2^b − 1. ∎

দাবি ২ (লাল নিয়ম থেকে): bh(root) ≥ h/2. সবচেয়ে লম্বা পথটি নিন — root-এর পরে তাতে h টি node (শেষটি NIL). নিয়ম ৪ বলে দুটি লাল পরপর নেই, আর NIL কালো; তাই এই h টি node-এর কমপক্ষে অর্ধেক কালো। সুতরাং bh(root) ≥ h/2.

জোড়া লাগাই: দাবি ১-এ x = root বসিয়ে n ≥ 2^bh(root) − 1 ≥ 2^h/2 − 1. দুই দিকে ১ যোগ করে log নিলে log₂(n + 1) ≥ h/2, অর্থাৎ

এর সরাসরি ফল: খোঁজা, সর্বনিম্ন/সর্বোচ্চ, আগের/পরের key (successor) — যেকোনো কাজ যা একটি পথ ধরে চলে, worst case-এ O(log n) সময় নেয়। আর এর জন্য বাড়তি জায়গা প্রতি node-এ মাত্র এক bit, মোট Θ(n). তুলনা করে দেখুন সংখ্যায় কেমন দাঁড়ায় (স্তর = root থেকে সবচেয়ে গভীর node পর্যন্ত পথের node-সংখ্যার সর্বোচ্চ সীমা):

এগুলো সর্বোচ্চ সীমা। বাস্তবে এলোমেলো ইনপুটে red-black tree-র উচ্চতা নিখুঁত ভারসাম্যের খুব কাছাকাছি থাকে। আর worst case-এও ১০০ কোটি key-তে ৫৯টি তুলনা — সাধারণ BST-এর ১০০ কোটির সাথে তুলনাই চলে না।

৪ · 2-3-4 tree-র ছদ্মবেশ — লাল link মানে জোড়া লাগানো node

পাঁচটি নিয়ম প্রথমে খামখেয়ালি মনে হয়। কেন লাল-কালো? কেন ঠিক এই নিয়মগুলো? উত্তরটি লুকিয়ে আছে আরেকটি tree-তে: 2-3-4 tree. এতে প্রতিটি node-এ ১, ২ বা ৩টি key থাকতে পারে (তাই সন্তান ২, ৩ বা ৪টি) — এদের বলে 2-node, 3-node আর 4-node. আর এর একটি কঠোর নিয়ম: সব leaf একই গভীরতায়. অর্থাৎ 2-3-4 tree সবসময় নিখুঁতভাবে ভারসাম্যপূর্ণ। এটি আসলে পর্ব ৩০-এর B-tree-র সবচেয়ে ছোট রূপ।

নিচের ডায়াগ্রামে একই tree দুই রূপে দেখুন। 2-3-4 রূপ থেকে red-black রূপে যাওয়ার নিয়ম সরল: 2-node → একটি কালো node; 3-node → একটি কালো node আর একটি লাল সন্তান; 4-node → মাঝের key কালো, দুই পাশের key লাল সন্তান।

এই সম্পর্কটি শুধু সুন্দর নয়, কাজেরও। 2-3-4 tree-র উচ্চতা স্পষ্টতই O(log n) (প্রতিটি node-এর কমপক্ষে ২টি সন্তান, আর সব leaf এক স্তরে)। Red-black tree-তে শুধু কালো node গুনলে সেই 2-3-4 tree-র স্তর পাওয়া যায়, আর লাল node প্রতিটি স্তরে বড়জোর একটি বাড়তি ধাপ যোগ করে — অংশ ৩-এর “সর্বোচ্চ দ্বিগুণ” এখান থেকেই। পরের অংশে দেখবেন, insert-এর প্রতিটি কেসও একটি 2-3-4 ঘটনা: “uncle লাল” মানে একটি 4-node ভেঙে মাঝের key ওপরে পাঠানো, আর rotation মানে একটি 3-node-কে 4-node বানানোর সময় আকৃতি ঠিক করা।

৫ · Insert — লাল node বসান, তারপর সারান (fix-up)

Insert দুই ধাপে। প্রথমে সাধারণ BST-এর মতো key-টি জায়গামতো একটি leaf হিসেবে বসান। তারপর তার রং ঠিক করুন — আর এখানেই প্রথম বুদ্ধি: নতুন node সবসময় লাল. কেন? কালো বসালে ওই একটি পথে কালো node একটি বেড়ে যেত, আর নিয়ম ৫ ভাঙত পুরো tree জুড়ে — সারানো কঠিন। লাল বসালে কোনো পথের কালো সংখ্যা বদলায় না; ভাঙতে পারে শুধু দুটি নিয়ম: নিয়ম ২ (নতুন node যদি root হয়) আর নিয়ম ৪ (যদি তার parent-ও লাল হয়)। নিয়ম ২ সারানো সহজ — শেষে root কালো করে দিন। বাকি থাকে শুধু “লাল–লাল” সমস্যা।

প্রথমে মনে করুন — rotation

পর্ব ২৮-এ AVL-এ rotation দেখেছেন। এটি একটি স্থানীয় পুনর্বিন্যাস: একটি সন্তানকে ওপরে তোলা আর parent-কে নিচে নামানো, এমনভাবে যে BST-এর ক্রম (inorder traversal-এ a < x < b < y < c) অটুট থাকে। মাত্র তিনটি pointer বদলায়, তাই সময় O(1).

        x                               y
       / \       left-rotate(x)        / \
      a   y      ------------->       x   c
         / \     <-------------      / \
        b   c    right-rotate(y)    a   b

inorder দুই দিকেই: a, x, b, y, c   (b-এর subtree শুধু x-এর এক পাশ থেকে অন্য পাশে যায়)

তিনটি কেস — সব নির্ভর করে “uncle”-এর রঙের ওপর

ধরুন z হলো লাল node, যার parent p-ও লাল। p লাল, তাই p root নয় (root কালো), সুতরাং p-এর parent g (grandparent) আছে, আর g অবশ্যই কালো (কারণ fix-up শুরুর আগে tree বৈধ ছিল)। এখন দেখুন g-এর অন্য সন্তান — z-এর uncle u. ধরি p হলো g-এর বাঁ সন্তান (ডান হলে সব কিছু আয়নার মতো উল্টো):

Pseudocode — RB-INSERT (CLRS-style; NIL leaves are black)

RB-INSERT(T, z):
    BST-INSERT(T, z)                     // ordinary BST insert at a leaf position
    z.color = RED
    while z.p.color == RED:              // the only possible violation: red z, red parent
        if z.p == z.p.p.left:
            u = z.p.p.right              // uncle
            if u.color == RED:                         // case 1: recolour
                z.p.color = BLACK;  u.color = BLACK
                z.p.p.color = RED;  z = z.p.p          // the problem moves two levels up
            else:
                if z == z.p.right:                     // case 2: triangle -> line
                    z = z.p;  LEFT-ROTATE(T, z)
                z.p.color = BLACK;  z.p.p.color = RED  // case 3: line
                RIGHT-ROTATE(T, z.p.p)
        else: the same with "left" and "right" exchanged
    T.root.color = BLACK

প্রথমে uncle কালো হওয়ার কেস দেখি। একটি ছোট উদাহরণ: tree-তে আছে 10 (কালো) আর তার ডান সন্তান 20 (লাল); এখন 15 insert করুন। এখানে p = 20 হলো g-এর ডান সন্তান, তাই টেবিলের আয়না-রূপ খাটবে: ত্রিভুজ মানে z হলো p-এর বাঁ সন্তান।

এবার uncle লাল হওয়ার কেস। এখানে rotation লাগে না, শুধু রং বদল — কিন্তু সমস্যাটি দুই স্তর ওপরে সরে যেতে পারে। উদাহরণ হিসেবে সবচেয়ে কঠিন ইনপুট নিই: সাজানো ক্রম। 1, 2, …, 7 insert করার পর tree যেমন দাঁড়ায়, সেখানে 8 insert করা দেখুন (সাধারণ BST হলে এতক্ষণে উচ্চতা 7 হয়ে যেত)।

কেন এটি ঠিক, আর কত সময় লাগে

Invariant. fix-up লুপের প্রতিটি ধাপের শুরুতে তিনটি কথা সত্য: (ক) z লাল; (খ) নিয়ম ৫ পুরো tree-তে ঠিক আছে; (গ) সর্বোচ্চ একটি নিয়ম ভাঙা থাকতে পারে — হয় z root আর লাল (নিয়ম ২), নয় z আর তার parent দুজনেই লাল (নিয়ম ৪)। কেস ১-এ g-এর নিচে কালো একটি কমে আর একটি বাড়ে — তাই (খ) টেকে, আর ভাঙা জায়গাটি g-তে সরে। কেস ২ আর ৩-এর rotation inorder ক্রম রাখে, আর রং এমনভাবে বদলায় যে g-এর জায়গায় বসা নতুন node কালো, তার দুই সন্তান লাল — প্রতিটি পথের কালো সংখ্যা আগের মতো, আর ওপরের দিকে আর কোনো লাল নেই, তাই লুপ শেষ। এটি পর্ব ০৩-এর loop invariant পদ্ধতি।

খরচ. BST insert নিজে O(log n) (উচ্চতা অংশ ৩ অনুযায়ী)। কেস ১ প্রতিবার z-কে দুই স্তর ওপরে তোলে, তাই সর্বোচ্চ O(log n) বার ঘটতে পারে, প্রতিবার O(1). কেস ২ বা ৩ একবার ঘটলেই লুপ শেষ — তাই একটি insert-এ সর্বোচ্চ ২টি rotation. মোট সময় O(log n), বাড়তি জায়গা O(1) (লুপ ওপরে ওঠে parent pointer ধরে, recursion ছাড়া)। আরও ভালো খবর: অনেকগুলো insert আর delete মিলিয়ে গড়লে রং বদলের সংখ্যাও প্রতি কাজে amortized O(1) — অর্থাৎ লম্বা রং-বদলের ঢেউ মাঝে মাঝে আসে, প্রতিবার নয়।

৬ · পুরো trace আর কোড — 10, 20, 30, 15, 25, 5

এবার শূন্য থেকে একটি tree বানাই, প্রতিটি insert-এর পর ছবি দেখে। একই ক্রম নিচের C++ আর Python প্রোগ্রামেও চলবে, তাই ডায়াগ্রামের প্রতিটি ধাপ আউটপুটের এক লাইনের সাথে মিলিয়ে নিতে পারবেন।

এখন কোড। এটি CLRS-এর অ্যালগরিদম, দুটি ছোট কৌশলসহ: বাঁ/ডান সন্তান রাখা হয়েছে ch[0]/ch[1] অ্যারেতে, যাতে একটি rotate(x, d) ফাংশনই দুই দিকের কাজ করে, আর fix-up-এর “আয়না” কেসগুলো আলাদা করে লিখতে না হয়; আর NIL হলো nullptr, যাকে red() ফাংশন কালো হিসেবে ধরে। শেষে bh() ফাংশন পুরো tree ঘুরে নিয়ম ৪ আর ৫ যাচাই করে আর black-height ফেরত দেয়।

#include <iostream>
#include <string>
#include <initializer_list>
using namespace std;
struct Node { int key; bool red = true; Node* ch[2] = {nullptr, nullptr}; Node* p = nullptr; };
Node* root = nullptr;
bool red(Node* x) { return x && x->red; }                  // NIL (nullptr) is black
void rotate(Node* x, int d) {         // d=0: left rotation (x->ch[1] moves up), d=1: right
    Node* y = x->ch[!d];
    x->ch[!d] = y->ch[d]; if (y->ch[d]) y->ch[d]->p = x;
    y->p = x->p;
    if (!x->p) root = y; else x->p->ch[x == x->p->ch[1]] = y;
    y->ch[d] = x; x->p = y;
}
string insert(int k) {
    Node *z = new Node{k}, *y = nullptr, *x = root; string log;
    while (x) { y = x; x = x->ch[k > x->key]; }              // ordinary BST insert
    z->p = y; (y ? y->ch[k > y->key] : root) = z;
    while (red(z->p)) {                                      // fix-up: red parent = violation
        Node *p = z->p, *g = p->p; int d = (p == g->ch[1]);   // d = side of the parent
        if (Node* u = g->ch[!d]; red(u)) {                   // case 1: red uncle -> recolour
            p->red = u->red = false; g->red = true; z = g; log += " case1"; continue;
        }
        if (z == p->ch[!d]) { z = p; rotate(z, d); p = z->p; log += " case2"; }  // triangle
        p->red = false; g->red = true; rotate(g, !d); log += " case3";          // case 3
    }
    root->red = false;
    return log.empty() ? "no fix-up" : log.substr(1);
}
string show(Node* x) {
    if (!x) return "-";
    string s = to_string(x->key) + (x->red ? "R" : "B");
    return x->ch[0] || x->ch[1] ? s + "(" + show(x->ch[0]) + "," + show(x->ch[1]) + ")" : s;
}
int bh(Node* x, bool& ok) {      // black nodes below x down to NIL; ok = false on a violation
    if (!x) return 0;
    if (x->red && (red(x->ch[0]) || red(x->ch[1]))) ok = false;       // red node, red child
    int a = bh(x->ch[0], ok) + !red(x->ch[0]), b = bh(x->ch[1], ok) + !red(x->ch[1]);
    if (a != b) ok = false;                                            // unequal black counts
    return a;
}
int main() {
    for (int k : {10, 20, 30, 15, 25, 5}) {
        string c = insert(k);
        cout << "insert " << k << " [" << c << "]: " << show(root) << '\n';
    }
    bool ok = !red(root); int h = bh(root, ok);
    cout << "root black, no red-red, equal black-height: " << (ok ? "yes" : "no") << '\n';
    cout << "black-height(root) = " << h << '\n';
}

insert 10 [no fix-up]: 10B
insert 20 [no fix-up]: 10B(-,20R)
insert 30 [case3]: 20B(10R,30R)
insert 15 [case1]: 20B(10B(-,15R),30B)
insert 25 [no fix-up]: 20B(10B(-,15R),30B(25R,-))
insert 5 [no fix-up]: 20B(10B(5R,15R),30B(25R,-))
root black, no red-red, equal black-height: yes
black-height(root) = 2

class Node:
    def __init__(self, key):
        self.key, self.red, self.ch, self.p = key, True, [None, None], None
root = None
def red(x): return x is not None and x.red              # NIL (None) is black
def rotate(x, d):          # d=0: left rotation (x.ch[1] moves up), d=1: right
    global root
    y = x.ch[1 - d]
    x.ch[1 - d] = y.ch[d]
    if y.ch[d]: y.ch[d].p = x
    y.p = x.p
    if not x.p: root = y
    else: x.p.ch[x is x.p.ch[1]] = y
    y.ch[d], x.p = x, y
def insert(k):
    global root
    z, y, x, log = Node(k), None, root, []
    while x: y, x = x, x.ch[k > x.key]                    # ordinary BST insert
    z.p = y
    if not y: root = z
    else: y.ch[k > y.key] = z
    while red(z.p):                                       # fix-up: red parent = violation
        p = z.p; g = p.p; d = int(p is g.ch[1])           # d = side of the parent
        u = g.ch[1 - d]                                   # uncle
        if red(u):                                        # case 1: red uncle -> recolour
            p.red = u.red = False; g.red = True; z = g; log.append("case1"); continue
        if z is p.ch[1 - d]:                              # case 2: triangle -> line
            z = p; rotate(z, d); p = z.p; log.append("case2")
        p.red = False; g.red = True; rotate(g, 1 - d); log.append("case3")   # case 3
    root.red = False
    return " ".join(log) or "no fix-up"
def show(x):
    if not x: return "-"
    s = f"{x.key}{'R' if x.red else 'B'}"
    return f"{s}({show(x.ch[0])},{show(x.ch[1])})" if x.ch[0] or x.ch[1] else s
def bh(x, ok):             # black nodes below x down to NIL; ok[0] = False on a violation
    if not x: return 0
    if x.red and (red(x.ch[0]) or red(x.ch[1])): ok[0] = False      # red node, red child
    a, b = (bh(c, ok) + (not red(c)) for c in x.ch)
    if a != b: ok[0] = False                                        # unequal black counts
    return a
for k in [10, 20, 30, 15, 25, 5]:
    c = insert(k)
    print(f"insert {k} [{c}]: {show(root)}")
ok = [not red(root)]
h = bh(root, ok)
print("root black, no red-red, equal black-height:", "yes" if ok[0] else "no")
print("black-height(root) =", h)

insert 10 [no fix-up]: 10B
insert 20 [no fix-up]: 10B(-,20R)
insert 30 [case3]: 20B(10R,30R)
insert 15 [case1]: 20B(10B(-,15R),30B)
insert 25 [no fix-up]: 20B(10B(-,15R),30B(25R,-))
insert 5 [no fix-up]: 20B(10B(5R,15R),30B(25R,-))
root black, no red-red, equal black-height: yes
black-height(root) = 2

নিজে চালিয়ে দেখুন — red-black tree visualiser

নিচের টুলে “চালিয়ে দেখুন” চাপুন। একটি সংখ্যা লিখে insert চাপলে tree আঁকা হবে — লাল বৃত্ত লাল node, কালো বৃত্ত কালো node — আর নিচে লেখা থাকবে কোন কেস চলল, উচ্চতা, black-height আর সব নিয়ম ঠিক কি না। 1 থেকে 15 ক্রমে বোতামটি চেপে দেখুন সাজানো ইনপুটে সাধারণ BST-এর মতো লাঠি হয় কি না।

let T = null;                                     // root of the red-black tree
const $ = id => document.getElementById(id);
const isRed = x => !!x && x.red;                  // NIL (null) is black
function rot(x, d) {                              // d=0: left rotation, d=1: right rotation
  const y = x.c[1 - d]; x.c[1 - d] = y.c[d]; if (y.c[d]) y.c[d].p = x;
  y.p = x.p; if (!x.p) T = y; else x.p.c[x === x.p.c[1] ? 1 : 0] = y;
  y.c[d] = x; x.p = y;
}
function add(k) {
  let y = null, x = T, z = { k, red: true, c: [null, null], p: null }; const log = [];
  while (x) { if (k === x.k) return `insert ${k}: already present`; y = x; x = x.c[k > x.k ? 1 : 0]; }
  z.p = y; if (!y) T = z; else y.c[k > y.k ? 1 : 0] = z;
  while (isRed(z.p)) {
    let p = z.p; const g = p.p, d = p === g.c[1] ? 1 : 0, u = g.c[1 - d];
    if (isRed(u)) { p.red = u.red = false; g.red = true; z = g; log.push("case1"); continue; }
    if (z === p.c[1 - d]) { z = p; rot(z, d); p = z.p; log.push("case2"); }
    p.red = false; g.red = true; rot(g, 1 - d); log.push("case3");
  }
  T.red = false; return `insert ${k}: ${log.join(" ") || "no fix-up"}`;
}
function chk(x) {                                 // black-height below x, or -1 if a rule breaks
  if (!x) return 0;
  const [a, b] = x.c.map(c => { const h = chk(c); return h < 0 ? -1 : h + (isRed(c) ? 0 : 1); });
  return a < 0 || a !== b || (x.red && x.c.some(isRed)) ? -1 : a;
}
function draw(msg) {
  const ns = []; let H = 0;                       // in-order position = x, depth = y
  (function walk(x, dep) { if (!x) return; walk(x.c[0], dep + 1); x.i = ns.length; x.d = dep; H = Math.max(H, dep); ns.push(x); walk(x.c[1], dep + 1); })(T, 0);
  const X = x => x.i * 40 + 20, Y = x => x.d * 50 + 20, W = Math.max(ns.length, 1) * 40;
  let s = `<svg viewBox="0 0 ${W} ${H * 50 + 40}" width="${W}" style="max-width:100%;height:auto">`;
  for (const x of ns) if (x.p) s += `<line x1="${X(x.p)}" y1="${Y(x.p)}" x2="${X(x)}" y2="${Y(x)}" stroke="#94a3b8" stroke-width="2"/>`;
  for (const x of ns) s += `<circle cx="${X(x)}" cy="${Y(x)}" r="16" fill="${x.red ? "#dc2626" : "#111827"}" stroke="#94a3b8"/><text x="${X(x)}" y="${Y(x) + 5}" fill="#fff" text-anchor="middle" font-size="13">${x.k}</text>`;
  $("tv").innerHTML = s + "</svg>";
  const b = chk(T), out = `${msg} | n=${ns.length} height=${T ? H : -1} black-height=${b} ${b >= 0 && !isRed(T) ? "valid" : "INVALID"}`;
  $("st").textContent = out; console.log(out);
}
$("bi").onclick = () => draw(add(Number($("kv").value)));
$("bs").onclick = () => { T = null; for (let k = 1; k <= 15; k++) draw(add(k)); };
$("br").onclick = () => { T = null; for (let k = 0; k < 12; k++) draw(add(1 + Math.floor(Math.random() * 99))); };
for (const k of [10, 20, 30, 15, 25, 5]) draw(add(k));

insert 10: no fix-up | n=1 height=0 black-height=1 valid
insert 20: no fix-up | n=2 height=1 black-height=1 valid
insert 30: case3 | n=3 height=1 black-height=1 valid
insert 15: case1 | n=4 height=2 black-height=2 valid
insert 25: no fix-up | n=5 height=2 black-height=2 valid
insert 5: no fix-up | n=6 height=2 black-height=2 valid

৭ · Delete — “double black”-এর ধারণা

Delete red-black tree-র সবচেয়ে কঠিন অংশ, আর পরীক্ষায় সাধারণত পুরো কোড নয়, ধারণাটি চাওয়া হয়। শুরুটা সাধারণ BST delete-এর মতো (পর্ব ২৭): যে node সরাতে হবে তার দুটি সন্তান থাকলে, তার inorder successor-কে (ডান subtree-র সবচেয়ে ছোটটি) তার জায়গায় আনুন — তাতে আসলে যে node tree থেকে বাদ পড়ে, তার সর্বোচ্চ একটি আসল সন্তান থাকে। এখন সমস্যা নির্ভর করে বাদ পড়া node-এর রঙের ওপর।

• বাদ পড়া node লাল: কোনো সমস্যা নেই। লাল node সরালে কোনো পথের কালো সংখ্যা বদলায় না, আর লাল–লাল তৈরি হয় না (লালের parent ও সন্তান দুজনেই কালো ছিল)।
• বাদ পড়া node কালো, আর তার জায়গায় আসা সন্তান লাল: সেই সন্তানকে কালো করে দিন — হারানো কালোটি ফিরে এল। শেষ।
• বাদ পড়া node কালো, আর জায়গায় আসা x-ও কালো (প্রায়ই NIL): এবার x-এর পথ দিয়ে যাওয়া প্রতিটি পথে একটি কালো কম — নিয়ম ৫ ভাঙা।

শেষ অবস্থার জন্য CLRS একটি চতুর কল্পনা ব্যবহার করে: x-কে একটি বাড়তি কালো “ঋণ” দেওয়া হয় — বলা হয় x এখন double black. হিসাবের খাতায় নিয়ম ৫ তাহলে ঠিক থাকে, কিন্তু “একটি node-এ দুটি কালো” নিয়ম ১ ভাঙে। Fix-up-এর কাজ এই বাড়তি কালোটিকে কোথাও “খরচ” করা: হয় ওপরে ঠেলে দেওয়া, যতক্ষণ না কোনো লাল node পাওয়া যায় (তাকে কালো করলেই ঋণ শোধ) বা root-এ পৌঁছায় (root-এ বাড়তি কালো ফেলে দেওয়া যায়, কারণ তাতে সব পথে সমানভাবে একটি কমে); নয়তো x-এর ভাই (sibling) w-এর দিক থেকে একটি node rotation করে এনে কালো করা।

খরচ insert-এর মতোই: double black সর্বোচ্চ উচ্চতা পর্যন্ত ওপরে উঠতে পারে, তাই O(log n) সময়; কিন্তু rotation হয় সর্বোচ্চ ৩টি, কারণ rotation-যুক্ত কেসগুলোর পরে লুপ এক-দুই ধাপেই থামে। AVL-এ delete-এর পর rotation O(log n) টি পর্যন্ত হতে পারে — এই পার্থক্যই বহু লাইব্রেরিকে red-black-এর দিকে টেনেছে। পুরো কেস-বিশ্লেষণ নিচের বাক্সে; প্রথম পড়ায় বাদ দিলেও কিছু হারাবেন না।

৮ · Left-leaning red-black tree — একই ধারণা, কম কেস

CLRS-ধাঁচের insert-এ তিনটি কেস আর তাদের আয়না-রূপ মিলিয়ে ছয়টি অবস্থা, delete-এ আটটি। ২০০৮ সালে Robert Sedgewick প্রস্তাব করেন left-leaning red-black tree (LLRB), যেখানে একটি বাড়তি নিয়ম যোগ করে কেসগুলো নাটকীয়ভাবে কমানো হয়: লাল link সবসময় বাঁ দিকে ঝুঁকে থাকে. অর্থাৎ কোনো node-এর ডান সন্তান কখনো লাল নয়। Sedgewick ও Wayne-এর Algorithms (৪র্থ সংস্করণ) বইয়ে যে রূপ শেখানো হয়, তাতে আবার কোনো node-এর দুই সন্তান একসাথে লাল থাকতে দেওয়া হয় না — ফলে এটি 4-node ছাড়া, 2-3 tree-র সাথে এক-এক সম্পর্কে মেলে: প্রতিটি 3-node-এর একটিই red-black রূপ (বড়টি কালো, ছোটটি তার বাঁ লাল সন্তান)।

Pseudocode — LLRB insert (Sedgewick 2008, 2-3 version; recursive)

put(h, key):                                   // returns the new root of this subtree
    if h == NIL: return new RED node(key)
    if key < h.key:   h.left  = put(h.left, key)
    elif key > h.key: h.right = put(h.right, key)
    if isRed(h.right) and not isRed(h.left):     h = rotateLeft(h)    // red leans right: fix
    if isRed(h.left) and isRed(h.left.left):     h = rotateRight(h)   // two reds in a row
    if isRed(h.left) and isRed(h.right):         flipColors(h)        // split a 4-node
    return h

insert(key):  root = put(root, key);  root.color = BLACK

rotateLeft(h):  x = h.right; h.right = x.left; x.left = h
                x.color = h.color; h.color = RED; return x      // rotateRight: mirror
flipColors(h):  h.color = RED; h.left.color = BLACK; h.right.color = BLACK

পুরো insert তিনটি if-এ! কারণ recursion থেকে ফেরার পথে প্রতিটি node-এ একই তিনটি স্থানীয় মেরামত চলে: ডানে ঝোঁকা লাল থাকলে বাঁয়ে ঘোরানো; পরপর দুটি বাঁ লাল থাকলে ডানে ঘোরানো; দুই সন্তান লাল হলে রং উল্টে মাঝের node-কে ওপরে পাঠানো — ঠিক 2-3 tree-তে একটি অস্থায়ী 4-node ভেঙে ফেলার মতো। CLRS-এর “uncle” ধারণাটিই লাগে না, parent pointer-ও লাগে না।

তবে LLRB সবকিছুতে জেতে না। বাড়তি নিয়মের কারণে এটি সাধারণ red-black tree-র চেয়ে বেশি rotation করে, আর delete সরল হলেও বোঝা সহজ নয়। কিছু প্রোগ্রামার মাপজোখ করে দেখিয়েছেন যে বাস্তবে এটি CLRS-ধাঁচের বাস্তবায়নের চেয়ে দ্রুত নয়। তাই বড় লাইব্রেরিগুলো এখনো ক্লাসিক রূপ ব্যবহার করে, আর LLRB টিকে আছে মূলত শেখানো আর ছোট, পরিষ্কার কোডের জন্য। একই ধরনের আরেকটি সরলীকরণ হলো Arne Andersson-এর ১৯৯৩ সালের AA tree, যেখানে লাল link শুধু ডান দিকে থাকতে পারে।

৯ · বাস্তবে কোথায়, আর কোন ভারসাম্যপূর্ণ tree কখন

যেখানে red-black tree প্রতিদিন কাজ করছে

• C++ std::map, std::set, multimap, multiset: standard শুধু O(log n) জটিলতা আর সাজানো ক্রম দাবি করে, কিন্তু GCC-র libstdc++ (ভেতরের নাম _Rb_tree), Clang-এর libc++ আর MSVC — তিনটি প্রধান বাস্তবায়নই red-black tree ব্যবহার করে। এর একটি সুবিধা: insert বা erase-এ অন্য উপাদানের iterator নষ্ট হয় না, কারণ node মেমরিতে সরে না, শুধু pointer বদলায়। পর্ব ১৫-এ এই associative container-গুলো ব্যবহার করেছেন; এখন জানেন ভেতরে কী আছে।
• Java TreeMap আর TreeSet: ডকুমেন্টেশনেই লেখা আছে এটি red-black tree, CLRS-এর অ্যালগরিদমের রূপান্তর। আর Java 8 থেকে HashMap-এর একটি bucket-এ অনেক key জমলে (৮টির বেশি, আর টেবিল যথেষ্ট বড় হলে) সেই bucket-এর linked list একটি ছোট red-black tree-তে বদলে যায় — hash table-এর worst case O(n) থেকে O(log n)-এ নামে (ভাবনার প্রশ্ন ৩)।
• Linux kernel: lib/rbtree.c-এ একটি সাধারণ rbtree আছে, যা kernel-এর বহু অংশ ব্যবহার করে। ২০০৭ সালে (Linux 2.6.23) আসা Completely Fair Scheduler (CFS) চলার-অপেক্ষায়-থাকা task-গুলোকে একটি rbtree-তে রাখত, যার key হলো task এ পর্যন্ত কতটা CPU সময় পেয়েছে; সবচেয়ে বাঁয়ের node — সবচেয়ে কম সময় পাওয়া task — পরের পালা পায়। Linux 6.6 থেকে নতুন EEVDF scheduler এসেছে, কিন্তু সেটিও rbtree-এর ওপরেই গড়া। epoll, timer আর আরও অনেক জায়গায়ও rbtree আছে।
• Python: standard library-তে কোনো balanced tree নেই। সাজানো map লাগলে মানুষ সাধারণত তৃতীয় পক্ষের sortedcontainers লাইব্রেরি ব্যবহার করেন — মজার ব্যাপার, সেটি tree নয়, ছোট ছোট সাজানো list-এর list, আর বাস্তবে বেশ দ্রুত।

ভারসাম্যপূর্ণ tree-এর তুলনা

একই কাজ — key সাজিয়ে রাখা, খোঁজা, insert, delete, ক্রমে ঘোরা — অনেকগুলো স্ট্রাকচার দিয়ে করা যায়। প্রত্যেকটির নিশ্চয়তা আর খরচ আলাদা। এই কোর্সে এদের বেশিরভাগ আলাদা পর্বে পাবেন:

Splay tree নিয়ে দুটি কথা, কারণ এই কোর্সে এর আলাদা পর্ব নেই। Daniel Sleator আর Robert Tarjan ১৯৮৫ সালে এটি প্রকাশ করেন। এর কোনো ভারসাম্যের নিয়ম বা রং নেই: যে node খোঁজা হয়, তাকে কয়েকটি বিশেষ rotation (zig, zig-zig, zig-zag) দিয়ে root পর্যন্ত তুলে আনা হয়। একটি একক কাজ O(n) পর্যন্ত লাগতে পারে, কিন্তু m টি কাজের মোট খরচ O((m + n) log n) — অর্থাৎ m ≥ n হলে প্রতি কাজে amortized O(log n) (পর্ব ৬০-এর potential পদ্ধতিতে প্রমাণ)। আর যে key বারবার চাওয়া হয়, সে root-এর কাছে থাকে বলে খুব দ্রুত পাওয়া যায় — একটি ক্যাশের মতো।

কোনটি কখন — সিদ্ধান্তের সংক্ষিপ্ত নির্দেশিকা

• সাধারণ কাজ, ভাষার লাইব্রেরি আছে: নিজে লিখবেন না — std::map/std::set, TreeMap ব্যবহার করুন। শুধু খোঁজা লাগলে, ক্রম লাগে না, তাহলে hash table (পর্ব ৩২) সাধারণত আরও দ্রুত।
• খোঁজা অনেক বেশি, পরিবর্তন খুব কম: AVL-এর কম উচ্চতা কাজে লাগে; আর ডেটা একবার বানিয়ে আর না বদলালে সাধারণ সাজানো অ্যারে আর binary search (পর্ব ১৮) প্রায়ই সবচেয়ে দ্রুত।
• insert আর delete অনেক, worst case-এর নিশ্চয়তা জরুরি: red-black tree — kernel আর real-time সিস্টেমের পছন্দ।
• ডেটা ডিস্কে বা মেমরির চেয়ে বড়: B-tree বা B+ tree — প্রতিটি ডিস্ক-পড়ায় অনেক key.
• কনটেস্টে split/merge, k-তম উপাদান, রেঞ্জ উল্টানো: treap, অথবা GNU-র policy-based tree দিয়ে বানানো ordered set কাঠামো।
• অনেক thread একসাথে লেখে: skip list — rotation না থাকায় lock ছাড়া বা কম lock-এ বানানো সহজ।
• কিছু key বারবার চাওয়া হয়: splay tree.

১০ · AI-এর যুগে red-black tree — কেস ঠিক, আয়না ভুল

“C++-এ একটি red-black tree লিখে দাও” — AI কয়েক সেকেন্ডে দেড়শো লাইন দেবে, আর ছোট পরীক্ষায় সেটি ঠিকঠাক চলবেও। সমস্যা হলো, red-black tree-র ভুল সাধারণত দুর্লভ কেসে লুকিয়ে থাকে: আয়না-রূপের একটি “left” যেখানে “right” হওয়ার কথা, rotation-এর পর parent pointer হালনাগাদ বাদ, বা delete-এর চারটি কেসের একটিতে ভুল রং। সাজানো ছোট ইনপুটে এই শাখাগুলো হয়তো কখনো চলেই না। আর তত্ত্বের প্রশ্নে AI প্রায়ই আত্মবিশ্বাসের সাথে ভুল সংখ্যা বলে — যেমন উচ্চতা “≤ log₂ n”, বা “insert-এ O(log n) rotation”.

Red-black tree-র কোডে AI সাধারণত যেসব ভুল করে

Red-black tree-র কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি insert-এর পর চালানো যায় এমন একটি যাচাই-ফাংশন লিখেছি: root কালো, লাল–লাল নেই, সব পথে black-height সমান, BST ক্রম ঠিক, parent pointer ঠিক
• বাড়তে থাকা, কমতে থাকা আর “zig-zag” (যেমন 10, 30, 20, 25, 22) ইনপুট দিয়ে চালিয়ে দুই দিকের সব কেস ছুঁয়েছি
• Edge case: খালি tree, এক node, সমান key, সব delete করে খালি করা
• এলোমেলো insert/delete-এর হাজারো ক্রমে std::set বা সাজানো list-এর সাথে মিলিয়ে stress testing করেছি — brute force উত্তর ধরে
• লাখটি সাজানো key insert করে উচ্চতা মেপেছি — 2 log₂(n+1)-এর নিচে আছে কি না
• AI-এর দেওয়া complexity বা rotation-সংখ্যার দাবি এই পর্বের প্রমাণের সাথে মিলিয়ে দেখেছি