Binary search tree (BST)

১ · BST-এর নিয়ম — বাঁয়ে ছোট, ডানে বড়

পর্ব ১৮-এ binary search দেখেছেন: সাজানো অ্যারের মাঝখানে তাকান, খোঁজা মানটি ছোট হলে বাঁ অর্ধেক, বড় হলে ডান অর্ধেক — প্রতি ধাপে অর্ধেক বাদ, তাই O(log n). কিন্তু সমস্যা হলো পরিবর্তন. সাজানো অ্যারের মাঝখানে নতুন একটি মান ঢোকাতে বা সরাতে পেছনের সবাইকে এক ঘর সরাতে হয় — O(n). একটি মোবাইল ব্যাংকিং অ্যাপের কথা ভাবুন, যেখানে প্রতি সেকেন্ডে নতুন গ্রাহক যোগ হচ্ছেন, কেউ অ্যাকাউন্ট বন্ধ করছেন, আর একই সাথে নম্বর ধরে খোঁজাও চলছে। সাজানো অ্যারেতে খোঁজা দ্রুত, বদলানো ধীর; অসাজানো অ্যারেতে উল্টো। দুটোই দ্রুত চাই।

পর্ব ২৬-এ tree-র পরিভাষা দেখেছেন: node, root, leaf, আর প্রতিটি node-এর সর্বোচ্চ দুটি সন্তানের binary tree. কোনো node আর তার নিচের সব বংশধর মিলে হয় সেই node-এর subtree. এখন একটি binary tree-কে binary search tree (BST) বলা হয়, যদি প্রতিটি node x-এর জন্য এই BST property সত্য হয়:

সাবধান — নিয়মটি পুরো subtree নিয়ে, শুধু সরাসরি সন্তান নিয়ে নয়। নিচের দুটি tree দেখুন। দুটিতেই প্রতিটি parent তার বাঁ সন্তানের চেয়ে বড় আর ডান সন্তানের চেয়ে ছোট। কিন্তু ডানেরটি BST নয়: 6 আছে 10-এর ডান subtree-তে, অথচ 6 < 10. কেউ 6 খুঁজলে root-এ 6 < 10 দেখে বাঁয়ে যাবে, আর কখনো পাবে না। অংশ ৭-এ এই ফাঁদটিই BST যাচাইয়ের সবচেয়ে প্রচলিত ভুল হিসেবে ফিরে আসবে।

   বৈধ BST                       BST নয়
       10                            10
      /  \                          /  \
     5    15                       5    15
         /  \                          /  \
       12    20                       6    20
                                     ^
                    6 < 15 ঠিক আছে, কিন্তু 6 < 10 — অথচ সে 10-এর ডান দিকে

প্রতিটি node-এ সাধারণত থাকে একটি key (যার ওপর তুলনা হয়), দরকার হলে সাথের তথ্য (value — যেমন ফোনবুকে নামের সাথে নম্বর), আর দুটি pointer: left ও right. সন্তান না থাকলে pointer-টি null. কোনো কোনো বাস্তবায়নে parent-এর দিকেও একটি pointer থাকে (অংশ ৪), আর কখনো subtree-র আকার (অংশ ৮)।

Key-এর ক্রম আর ডুপ্লিকেটের নীতি

BST কাজ করে যেকোনো key-তে, যদি দুটি key-এর মধ্যে “কে আগে” তা সবসময় সুসংগতভাবে বলা যায় — সংখ্যা, string-এর অভিধান-ক্রম, বা তারিখ। পর্ব ২৫-এ দেখা comparator আর strict weak ordering-এর শর্তগুলো এখানেও লাগে; comparator অসংগত হলে tree-র ভেতরের ক্রম নষ্ট হয়, আর খোঁজা নিঃশব্দে ভুল ফল দেয়।

সমান key এলে কী হবে, তা আগেই ঠিক করে নিতে হয়। তিনটি প্রচলিত নীতি:

• প্রত্যাখ্যান বা উপেক্ষা — key আগে থেকে থাকলে নতুন কিছু যোগ হয় না (বড়জোর value হালনাগাদ হয়)। std::set, std::map আর এই পর্বের কোড এভাবে চলে। এখানে নিয়মটি কঠোর: বাঁয়ে <, ডানে >.
• প্রতিটি node-এ একটি count — একই key আবার এলে শুধু সংখ্যা বাড়ে। tree ছোট থাকে, আর delete মানে count কমানো।
• সমানকে সবসময় একই দিকে পাঠানো — যেমন “সমান হলে ডানে”. তখন নিয়ম হয় বাঁ < x ≤ ডান। std::multiset এভাবে চলে: নতুন সমান key বসে আগের সমানগুলোর পরে। তবে এতে একই key-এর অনেক কপি একটি লম্বা শিকল বানাতে পারে।

কোন নীতি নিচ্ছেন, তা কোডের প্রতিটি অংশে — insert, search, delete আর validate — একই থাকতে হবে। একটিতে < আর অন্যটিতে ≤ লিখলেই খুঁজে না পাওয়ার মতো সূক্ষ্ম bug হয়।

২ · Search আর min/max — প্রতিটি তুলনায় একটি দিক বাদ

খোঁজার নিয়ম সরাসরি BST property থেকে আসে। root থেকে শুরু করুন। খোঁজা key k যদি বর্তমান node-এর key-এর সমান হয়, পাওয়া গেল। ছোট হলে k থাকতে পারে শুধু বাঁ subtree-তে — ডানের সবাই আরও বড় — তাই বাঁয়ে যান; বড় হলে ডানে। null-এ পৌঁছালে k tree-তে নেই। প্রতিটি তুলনায় একটি পুরো subtree বাদ পড়ে, ঠিক binary search-এর মতো।

Pseudocode — BST search, min, max (iterative; null = no node)

search(t, k):
    while t != null and k != t.key:
        if k < t.key: t = t.left
        else:         t = t.right
    return t                          // the node with key k, or null

minimum(t):  while t.left  != null: t = t.left;   return t    // t != null
maximum(t):  while t.right != null: t = t.right;  return t

এই পর্বের প্রধান উদাহরণ tree বানানো হয়েছে 50, 30, 70, 20, 40, 60, 80, 35, 45 ক্রমে insert করে। এতে 45 খুঁজে দেখুন, তারপর 65 — যা tree-তে নেই:

কেন ঠিক — invariant. লুপের পুরো সময় একটি কথা সত্য: “k যদি tree-তে থাকে, তাহলে সেটি বর্তমান node t-এর subtree-তে আছে।” শুরুতে t = root, তাই সত্য। k < t.key হলে BST property অনুযায়ী ডান subtree আর t নিজে বাদ, তাই k থাকলে বাঁ subtree-তে — t = t.left করার পরও কথাটি সত্য। লুপ থামে হয় k পেয়ে, নয়তো t = null-এ — খালি subtree-তে k নেই, তাই tree-তেই নেই। এটি পর্ব ০৩-এর loop invariant-এর সরাসরি প্রয়োগ।

খরচ. প্রতিটি ধাপে এক স্তর নিচে নামি, আর একটি পথে সর্বোচ্চ h + 1 টি node (h = tree-র উচ্চতা, root থেকে সবচেয়ে গভীর leaf পর্যন্ত edge-এর সংখ্যা)। তাই সময় O(h). লুপ দিয়ে লিখলে বাড়তি জায়গা O(1); recursion দিয়ে লিখলে call stack-এ O(h). লক্ষ করুন, খরচ n দিয়ে নয়, h দিয়ে লেখা — h কত বড় হতে পারে, সেটিই এই পর্বের কেন্দ্রীয় প্রশ্ন (অংশ ৬)।

Min আর max আরও সহজ: সবচেয়ে ছোট key সবসময় root থেকে শুধু বাঁয়ে বাঁয়ে গিয়ে শেষ node-এ (এখানে 20), সবচেয়ে বড়টি শুধু ডানে ডানে (80). কারণ কোনো node-এর বাঁ সন্তান থাকলে তার চেয়ে ছোট কেউ আছে; যার বাঁ সন্তান নেই আর যে পথটি সবসময় বাঁয়ে গেছে, তার চেয়ে ছোট কেউ থাকতে পারে না। খরচও O(h). লক্ষ করুন, সবচেয়ে ছোট node-টি leaf না-ও হতে পারে — তার ডান সন্তান থাকতে পারে, শুধু বাঁ সন্তান থাকে না। Delete-এ এই তথ্যটি কাজে লাগবে।

৩ · Insert — ব্যর্থ খোঁজার শেষে নতুন leaf

নতুন key কোথায় বসবে? যেখানে থাকলে খোঁজা তাকে খুঁজে পেত। তাই insert মানে প্রথমে key-টি খোঁজা; খোঁজা ব্যর্থ হয়ে যে null ঘরে থামে, সেখানে একটি নতুন node বসানো। নতুন node সবসময় একটি leaf হয়ে যোগ হয় — পুরোনো কোনো node সরাতে হয় না, কোনো pointer-এর জট খুলতে হয় না।

খরচ: খোঁজার মতোই O(h) সময়; লুপে লিখলে O(1) বাড়তি জায়গা, recursion-এ O(h). Recursive রূপটি খুব ছোট, আর কোডে আমরা সেটিই ব্যবহার করব: insert(t, k) নতুন subtree-র root ফেরত দেয় — t null হলে নতুন node, নইলে t নিজেই, আর পথে t.left = insert(t.left, k) লিখে সংযোগ বসানো হয়।

Insert-এর ক্রমই আকার ঠিক করে. একই key-গুলো ভিন্ন ক্রমে insert করলে ভিন্ন আকারের tree হয়। প্রথম key সবসময় root হয়ে থাকে (delete না করা পর্যন্ত)। 2, 1, 3 ক্রমে দিলে সুন্দর একটি তিন-node-এর tree; 1, 2, 3 দিলে ডান দিকে হেলে থাকা একটি শিকল। ৩টি key দিয়ে মোট ৫টি আলাদা আকারের BST হয় — insert-এর ৬টি ক্রমের মধ্যে 2, 1, 3 আর 2, 3, 1 একই tree দেয়। (n টি key-এর BST আকারের সংখ্যা একটি Catalan number — ভাবনার প্রশ্ন ৫ দেখুন।)

৪ · Inorder traversal সাজানো ক্রম দেয় — আর successor/predecessor

পর্ব ২৬-এ inorder traversal দেখেছেন: আগে বাঁ subtree, তারপর node নিজে, তারপর ডান subtree. এক অদ্ভুত সুন্দর তথ্য: BST-তে inorder ক্রম ঠিক ছোট থেকে বড় সাজানো ক্রম. উদাহরণের tree-তে inorder: 20 30 35 40 45 50 60 65 70 80. কোনো সর্ট চালানো হয়নি — ক্রমটি tree-র আকারের মধ্যেই লুকিয়ে ছিল।

প্রমাণ — node সংখ্যার ওপর induction

দাবি: n টি node-এর যেকোনো BST-এর inorder traversal তার key-গুলোকে ছোট থেকে বড় ক্রমে দেয়। প্রমাণ strong induction দিয়ে, n-এর ওপর (পর্ব ০৩)।

• ভিত্তি (n = 0): খালি tree-র inorder খালি ক্রম, যা সাজানো। (n = 1 হলে একটি key, তাও সাজানো।)
• Inductive hypothesis: ধরে নিই, n-এর চেয়ে কম node-এর প্রতিটি BST-এর জন্য দাবিটি সত্য।
• Inductive step: n টি node-এর BST নিন, root r, বাঁ subtree L, ডান subtree R. L আর R নিজেরাও BST (BST property প্রতিটি node-এর জন্য, তাই subtree-তেও সত্য), আর দুটিতেই n-এর চেয়ে কম node. Hypothesis অনুযায়ী inorder(L) সাজানো, inorder(R) সাজানো। Inorder(T) = inorder(L), তারপর r.key, তারপর inorder(R). BST property বলে L-এর সব key < r.key < R-এর সব key. তিনটি সাজানো টুকরো, আর প্রতিটি টুকরোর সব মান পরেরটির সব মানের চেয়ে ছোট — জোড়া দিলেও সাজানো। ∎

এর উল্টোটাও সত্য (আলাদা key ধরে): কোনো binary tree-র inorder ক্রম কঠোরভাবে বাড়তে থাকলে tree-টি BST. তাই “BST কি না” যাচাইয়ের একটি সঠিক উপায় হলো inorder-এ হেঁটে দেখা প্রতিটি মান আগেরটির চেয়ে বড় কি না (অংশ ৭)। আরেকটি ফল: n টি সংখ্যা একে একে BST-তে insert করে inorder পড়লেই সর্ট হয়ে যায় — একে বলে tree sort. এর খরচ insert-গুলোর খরচ, যা tree-র আকারের ওপর নির্ভর করে: ভারসাম্য থাকলে O(n log n), শিকল হলে O(n²) — অংশ ৬-এ দেখবেন কেন এটি quicksort-এর সাথে অদ্ভুতভাবে মেলে।

পুরো inorder traversal-এর খরচ Θ(n): প্রতিটি node একবার ছাপা হয়, আর প্রতিটি edge ঠিক দুবার পার হয় (একবার নামতে, একবার উঠতে)। Recursion-এ বাড়তি জায়গা O(h).

Successor আর predecessor — দুটি অবস্থা

কোনো node x-এর inorder successor হলো সাজানো ক্রমে x-এর ঠিক পরের key — অর্থাৎ x-এর চেয়ে বড় key-গুলোর মধ্যে সবচেয়ে ছোট। Predecessor ঠিক আগেরটি। পুরো inorder না চালিয়েই এটি O(h)-এ পাওয়া যায়, দুটি অবস্থা আলাদা করে:

• অবস্থা ১ — x-এর ডান subtree আছে: successor = ডান subtree-র minimum. একবার ডানে, তারপর যতক্ষণ পারেন বাঁয়ে। কারণ x-এর চেয়ে বড় কিন্তু কাছের সবাই ওই ডান subtree-তেই আছে।
• অবস্থা ২ — ডান subtree নেই: তখন x যে subtree-র “সবচেয়ে বড়” সদস্য, সেই subtree-র ওপরের প্রথম পূর্বপুরুষটিই উত্তর। নিয়ম: ওপরে উঠতে থাকুন, যতক্ষণ আপনি ডান সন্তান হিসেবে উঠছেন; প্রথমবার যখন কোনো node-এর বাঁ সন্তান হিসেবে তার কাছে পৌঁছান, সেই node-ই successor. এমন কেউ না থাকলে x-ই সবচেয়ে বড় — successor নেই।

অবস্থা ২-এ ওপরে উঠতে হয়, কিন্তু সাধারণ BST node-এ শুধু নিচের দিকের pointer আছে। দুটি সমাধান: (ক) প্রতিটি node-এ একটি parent pointer রাখা — ওঠা সহজ, কিন্তু প্রতিটি insert, delete-এ সেটিও ঠিক রাখতে হয়, আর node-প্রতি একটি বাড়তি pointer-এর জায়গা লাগে; (খ) root থেকে আবার x খোঁজা, আর পথে যেখানেই বাঁয়ে গেছেন সেই node-টি মনে রাখা — শেষ যে node-এ বাঁয়ে গেছেন, সেটিই successor. দুটিই O(h).

Predecessor হুবহু আয়নার মতো: বাঁ subtree থাকলে তার maximum; না থাকলে ওপরে উঠুন যতক্ষণ বাঁ সন্তান হিসেবে উঠছেন, প্রথম যেখানে ডান সন্তান হিসেবে পৌঁছান সেটিই উত্তর। যেমন pred(60) = 50 (60-এর বাঁ subtree নেই; 60 হলো 70-এর বাঁ সন্তান, 70 হলো 50-এর ডান সন্তান → 50).

৫ · Delete — তিনটি অবস্থা

Insert সবসময় leaf যোগ করে, তাই সহজ। Delete কঠিন, কারণ মুছতে হতে পারে tree-র মাঝখানের কোনো node, যার নিচে পুরো একটি পরিবার ঝুলে আছে। প্রথমে key-টি খুঁজে node z বের করুন (O(h)), তারপর z-এর সন্তান-সংখ্যা দেখে তিনটি অবস্থা।

অবস্থা ১ — z একটি leaf

সবচেয়ে সহজ: parent-এর যে pointer z-কে দেখাচ্ছিল, সেটিকে null করুন, আর z-এর মেমরি ছেড়ে দিন। বাকি কারও সম্পর্ক বদলায় না, তাই BST property অটুট।

অবস্থা ২ — z-এর একটিমাত্র সন্তান

z-এর একমাত্র সন্তানকে (তার পুরো subtree-সহ) z-এর জায়গায় তুলে দিন: parent-এর pointer এখন সরাসরি সেই সন্তানকে দেখাবে। পর্ব ১২-এর linked list থেকে একটি node বাদ দেওয়ার মতো — আগেরটিকে পরেরটির সাথে জুড়ে দেওয়া। কেন BST property ভাঙে না? z-এর subtree-টি তার parent-এর যে দিকে ছিল, ওপরে ওঠা subtree-টিও সেই একই দিকে থাকে, আর তার সব key আগেও z-এর subtree-র অংশ ছিল — তাই parent ও সব পূর্বপুরুষের সাথে সম্পর্ক বদলায় না।

অবস্থা ৩ — z-এর দুটি সন্তান

এখানে z-কে সরিয়ে দিলে দুটি subtree ঝুলে থাকে, আর parent-এর কাছে জায়গা একটিই। কৌশলটি ১৯৬২ সালে Thomas Hibbard প্রকাশ করেন, তাই একে কখনো Hibbard deletion বলে: z-এর জায়গায় বসান এমন একটি key, যা বাঁ subtree-র সবার চেয়ে বড় আর ডান subtree-র সবার চেয়ে ছোট। এমন key আছে দুটি — z-এর inorder successor (ডান subtree-র minimum) আর predecessor (বাঁ subtree-র maximum). প্রচলিতভাবে successor s নেওয়া হয়:

1. s = z-এর ডান subtree-র minimum (একবার ডানে, তারপর বাঁয়ে বাঁয়ে)।
2. s-এর key (আর value) z-এ কপি করুন।
3. এবার ডান subtree থেকে s-এর পুরোনো node-টি মুছুন। s-এর কখনো বাঁ সন্তান থাকে না — থাকলে সে আরও ছোট হতো, minimum হতো না। তাই এই দ্বিতীয় delete সবসময় অবস্থা ১ বা ২ — সহজ।

এবার পুরো BST কোডে — insert, search, delete, প্রতিটি কাজের পর inorder ছাপা, আর শেষে অংশ ৭-এর যাচাই (এখনই না বুঝলে সমস্যা নেই, অংশ ৭ পড়ে ফিরে আসুন)। Delete-এর তিনটি অবস্থা কোডে মাত্র দুটি শাখা: “কোনো একটি সন্তান null” শাখাটি leaf আর এক-সন্তান দুটোই সামলায় — leaf হলে অন্য সন্তানটিও null, তাই null-ই ফেরত যায়।

#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct Node { int key; Node *l = nullptr, *r = nullptr; };

Node* insert(Node* t, int k) {
    if (!t) return new Node{k};
    if (k < t->key) t->l = insert(t->l, k);
    else if (k > t->key) t->r = insert(t->r, k);       // duplicate keys are ignored
    return t;
}
bool search(Node* t, int k, string& path) {
    for (; t; t = k < t->key ? t->l : t->r) {
        path += " " + to_string(t->key);
        if (t->key == k) return true;
    }
    return false;
}
Node* erase(Node* t, int k) {
    if (!t) return nullptr;
    if (k < t->key) t->l = erase(t->l, k);
    else if (k > t->key) t->r = erase(t->r, k);
    else if (!t->l || !t->r) { Node* c = t->l ? t->l : t->r; delete t; return c; } // leaf or one child
    else {
        Node* s = t->r;
        while (s->l) s = s->l;                          // inorder successor = min of right subtree
        t->key = s->key; t->r = erase(t->r, s->key);
    }
    return t;
}
void inorder(Node* t, string& out) { if (t) { inorder(t->l, out); out += " " + to_string(t->key); inorder(t->r, out); } }
int height(Node* t) { return t ? 1 + max(height(t->l), height(t->r)) : -1; }
bool naiveOk(Node* t) {                                 // WRONG: compares a node only with its children
    if (!t) return true;
    if ((t->l && t->l->key >= t->key) || (t->r && t->r->key <= t->key)) return false;
    return naiveOk(t->l) && naiveOk(t->r);
}
bool valid(Node* t, long long lo = LLONG_MIN, long long hi = LLONG_MAX) {   // right: key in (lo, hi)
    return !t || (lo < t->key && t->key < hi && valid(t->l, lo, t->key) && valid(t->r, t->key, hi));
}
void show(const string& label, Node* t) { string s; inorder(t, s); cout << label << string(22 - label.size(), ' ') << "->" << s << '\n'; }
int main() {
    Node* root = nullptr;
    for (int k : vector{50, 30, 70, 20, 40, 60, 80, 35, 45}) root = insert(root, k);
    show("insert 9 keys", root); cout << "height " << height(root) << '\n';
    for (int k : vector{45, 65}) {
        string path; bool ok = search(root, k, path);
        cout << "search " << k << ": " << (ok ? "found" : "not found") << ", path" << path << '\n';
    }
    root = insert(root, 65); show("insert 65", root);
    for (auto [k, why] : vector<pair<int, string>>{{20, "leaf"}, {30, "one child"}, {50, "two kids"}}) {
        root = erase(root, k); show("delete " + to_string(k) + " (" + why + ")", root);
    }
    cout << "root " << root->key << " height " << height(root) << '\n';
    Node a{6}, b{20}, c{5}, d{15, &a, &b}, bad{10, &c, &d};      // the tricky tree of section 7
    for (auto [name, t] : vector<pair<string, Node*>>{{"final tree", root}, {"tricky tree", &bad}})
        cout << name << ": naive says " << (naiveOk(t) ? "BST" : "not BST") << ", bounds say " << (valid(t) ? "BST" : "not BST") << '\n';
}

insert 9 keys         -> 20 30 35 40 45 50 60 70 80
height 3
search 45: found, path 50 30 40 45
search 65: not found, path 50 70 60
insert 65             -> 20 30 35 40 45 50 60 65 70 80
delete 20 (leaf)      -> 30 35 40 45 50 60 65 70 80
delete 30 (one child) -> 35 40 45 50 60 65 70 80
delete 50 (two kids)  -> 35 40 45 60 65 70 80
root 60 height 2
final tree: naive says BST, bounds say BST
tricky tree: naive says BST, bounds say not BST

class Node:
    def __init__(self, key, l=None, r=None): self.key, self.l, self.r = key, l, r

def insert(t, k):
    if t is None: return Node(k)
    if k < t.key: t.l = insert(t.l, k)
    elif k > t.key: t.r = insert(t.r, k)          # duplicate keys are ignored
    return t

def search(t, k):
    path = []
    while t and t.key != k:
        path.append(t.key); t = t.l if k < t.key else t.r
    return t is not None, path + ([k] if t else [])

def erase(t, k):
    if t is None: return None
    if k < t.key: t.l = erase(t.l, k)
    elif k > t.key: t.r = erase(t.r, k)
    elif t.l is None or t.r is None: return t.l or t.r   # leaf or one child
    else:
        s = t.r
        while s.l: s = s.l                        # inorder successor = min of right subtree
        t.key = s.key; t.r = erase(t.r, s.key)
    return t

inorder = lambda t: inorder(t.l) + [t.key] + inorder(t.r) if t else []
height = lambda t: 1 + max(height(t.l), height(t.r)) if t else -1

def naive_ok(t):                                  # WRONG: compares a node only with its children
    if t is None: return True
    if (t.l and t.l.key >= t.key) or (t.r and t.r.key <= t.key): return False
    return naive_ok(t.l) and naive_ok(t.r)

def valid(t, lo=float("-inf"), hi=float("inf")):  # right: every key must lie in (lo, hi)
    return t is None or (lo < t.key < hi and valid(t.l, lo, t.key) and valid(t.r, t.key, hi))

show = lambda label, t: print(f"{label:<22}-> {' '.join(map(str, inorder(t)))}")
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35, 45]: root = insert(root, k)
show("insert 9 keys", root); print("height", height(root))
for k in [45, 65]:
    ok, path = search(root, k)
    print(f"search {k}: {'found' if ok else 'not found'}, path {' '.join(map(str, path))}")
root = insert(root, 65); show("insert 65", root)
for k, why in [(20, "leaf"), (30, "one child"), (50, "two kids")]:
    root = erase(root, k); show(f"delete {k} ({why})", root)
print("root", root.key, "height", height(root))
bad = Node(10, Node(5), Node(15, Node(6), Node(20)))
for name, t in [("final tree", root), ("tricky tree", bad)]:
    print(f"{name}: naive says {'BST' if naive_ok(t) else 'not BST'}, bounds say {'BST' if valid(t) else 'not BST'}")

insert 9 keys         -> 20 30 35 40 45 50 60 70 80
height 3
search 45: found, path 50 30 40 45
search 65: not found, path 50 70 60
insert 65             -> 20 30 35 40 45 50 60 65 70 80
delete 20 (leaf)      -> 30 35 40 45 50 60 65 70 80
delete 30 (one child) -> 35 40 45 50 60 65 70 80
delete 50 (two kids)  -> 35 40 45 60 65 70 80
root 60 height 2
final tree: naive says BST, bounds say BST
tricky tree: naive says BST, bounds say not BST

৬ · খরচ O(h) — ভারসাম্যে log n, সাজানো ইনপুটে n

এ পর্যন্ত প্রতিটি কাজ O(h). এবার h-এর সীমা বের করি। n টি node-এর binary tree-তে depth i-এ সর্বোচ্চ 2ⁱ টি node থাকতে পারে, তাই উচ্চতা h হলে n ≤ 1 + 2 + 4 + … + 2^h = 2^h+1 − 1, অর্থাৎ h ≥ ⌈log₂(n + 1)⌉ − 1 = ⌊log₂ n⌋. আর ওপরের সীমা স্পষ্ট: প্রতিটি স্তরে অন্তত একটি node, তাই h ≤ n − 1.

১০ লাখ key-তে ভারসাম্যপূর্ণ tree-র উচ্চতা মাত্র ১৯ — প্রতিটি খোঁজায় সর্বোচ্চ ২০টি তুলনা। কিন্তু খারাপতম ক্ষেত্রে উচ্চতা ৯,৯৯,৯৯৯ — তখন BST আসলে একটি linked list. আর এই খারাপতম ক্ষেত্রটি দুর্লভ নয়; সবচেয়ে সাধারণ ইনপুটটিই এটি তৈরি করে — আগে থেকে সাজানো ডেটা. রোল নম্বর, তারিখ, ক্রমিক লেনদেন নম্বর — বাস্তবের অনেক ডেটা এমনিতেই বাড়তে থাকা ক্রমে আসে।

এলোমেলো ক্রমে insert করলে — গড় উচ্চতা O(log n)

যদি n টি আলাদা key-এর সব n! ক্রম সমান সম্ভাব্য হয় (একে বলে random BST), তাহলে ফলাফল অনেক ভালো। দুটি বিখ্যাত ফল (প্রমাণ এখানে নয়, শুধু বক্তব্য):

• গড় depth: একটি node-এর প্রত্যাশিত depth প্রায় 2 ln n ≈ 1.39 log₂ n. অর্থাৎ সফল খোঁজায় গড়ে ভারসাম্যপূর্ণ tree-র চেয়ে মাত্র প্রায় ৩৯% বেশি তুলনা।
• প্রত্যাশিত উচ্চতা: Θ(log n); আরও সূক্ষ্মভাবে প্রায় 4.311 ln n ≈ 2.99 log₂ n (Luc Devroye, ১৯৮৬)। সবচেয়ে গভীর পথ গড় পথের চেয়ে লম্বা, কিন্তু তবু logarithmic.

গড় depth-এর ফলটির পেছনে একটি সুন্দর মিল আছে: BST-তে insert করার সময় যে তুলনাগুলো হয়, ঠিক সেগুলোই হয় quicksort-এ, যদি প্রতিবার প্রথম উপাদানকে pivot নেওয়া হয় (পর্ব ২২) — root-ই প্রথম pivot, তার বাঁ আর ডান subtree দুটি partition. তাই BST বানানোর মোট খরচ আর quicksort-এর তুলনা-সংখ্যা একই, গড়ে প্রায় 2n ln n (ভাবনার প্রশ্ন ২)।

কিন্তু এই “গড়” নির্ভর করে ইনপুটের এলোমেলোতার ওপর, অ্যালগরিদমের নিজের ওপর নয়। ইনপুট কে দেবে, আপনি জানেন না — সাজানো ডেটা, বা ইচ্ছে করে বানানো খারাপ ইনপুট (anti-test) এলে O(n). দুটি পথ আছে: tree-কে নিজেই ভারসাম্যে রাখতে বাধ্য করা (AVL, red-black — পর্ব ২৮–২৯), অথবা এলোমেলোতা নিজে তৈরি করা (treap — পর্ব ৩৮), যাতে গড়টি ইনপুটের ওপর নয়, নিজের মুদ্রা-নিক্ষেপের ওপর নির্ভর করে।

নিজে চালিয়ে দেখুন — BST visualiser

নিচের টুলে “চালিয়ে দেখুন” চাপুন। একটি key লিখে insert চাপলে সেটি যে পথে নামল তা লাল হয়ে জ্বলবে; delete চাপলে কোন অবস্থা (leaf, one child, two children) ঘটল তা নিচে লেখা আসবে। প্রতিটি node-এর আনুভূমিক অবস্থান তার inorder ক্রম — তাই বাঁ থেকে ডানে পড়লেই সাজানো ক্রম। sorted বোতামে 10, 20, …, 80 সাজানো ক্রমে ঢুকিয়ে শিকলটি দেখুন, তারপর কয়েকবার random চেপে তুলনা করুন উচ্চতা কত হয়।

let bst = null;                                   // node = {k, l, r}
const $ = id => document.getElementById(id);
function ins(t, k, path) {
  if (!t) return { k, l: null, r: null };
  path.push(t.k);
  if (k < t.k) t.l = ins(t.l, k, path); else if (k > t.k) t.r = ins(t.r, k, path);
  return t;                                        // equal key: ignored
}
function del(t, k, info) {
  if (!t) return null;
  if (k < t.k) t.l = del(t.l, k, info); else if (k > t.k) t.r = del(t.r, k, info);
  else if (!t.l || !t.r) { info.c = t.l || t.r ? "one child" : "leaf"; return t.l || t.r; }
  else {
    let s = t.r; while (s.l) s = s.l;              // inorder successor
    info.c = "two children, successor " + s.k; t.k = s.k; t.r = del(t.r, s.k, {});
  }
  return t;
}
const inord = (t, a = []) => (t && (inord(t.l, a), a.push(t.k), inord(t.r, a)), a);
const ht = t => t ? 1 + Math.max(ht(t.l), ht(t.r)) : -1;
function draw(msg, hot = []) {
  const pos = new Map(); let x = 0;                // x = inorder rank, y = depth
  (function walk(t, d) { if (t) { walk(t.l, d + 1); pos.set(t, [x++, d]); walk(t.r, d + 1); } })(bst, 0);
  let svg = "", nodes = "";
  for (const [t, [px, py]] of pos) {
    for (const c of [t.l, t.r]) if (c) { const [cx, cy] = pos.get(c);
      svg += `<line x1="${px * 34 + 16}" y1="${py * 46 + 16}" x2="${cx * 34 + 16}" y2="${cy * 46 + 16}"/>`; }
    nodes += `<div class="nd${hot.includes(t.k) ? " hl" : ""}" style="left:${px * 34}px;top:${py * 46}px">${t.k}</div>`;
  }
  const h = ht(bst), box = $("bd");
  box.style.width = Math.max(1, x) * 34 + "px"; box.style.height = (h + 1) * 46 + "px";
  box.innerHTML = `<svg>${svg}</svg>${nodes}`;
  const line = `${msg} | inorder: ${inord(bst).join(" ") || "(empty)"} | height ${h}`;
  $("msg").textContent = line; console.log(line);
}
function add(k) { const path = []; bst = ins(bst, k, path); draw(`insert ${k}, path ${path.join(">") || "-"}`, [...path, k]); }
function remove(k) { const info = { c: "not found" }; bst = del(bst, k, info); draw(`delete ${k} (${info.c})`); }
$("bi").onclick = () => add(Number($("bv").value));
$("bx").onclick = () => remove(Number($("bv").value));
$("bs").onclick = () => { bst = null; for (let k = 1; k <= 8; k++) add(k * 10); };
$("br").onclick = () => { bst = null; for (let i = 0; i < 12; i++) add(1 + Math.floor(Math.random() * 99)); };
for (const k of [50, 30, 70, 20, 40, 60, 80, 35, 45]) add(k);
remove(30);

insert 50, path - | inorder: 50 | height 0
insert 30, path 50 | inorder: 30 50 | height 1
insert 70, path 50 | inorder: 30 50 70 | height 1
insert 20, path 50>30 | inorder: 20 30 50 70 | height 2
insert 40, path 50>30 | inorder: 20 30 40 50 70 | height 2
insert 60, path 50>70 | inorder: 20 30 40 50 60 70 | height 2
insert 80, path 50>70 | inorder: 20 30 40 50 60 70 80 | height 2
insert 35, path 50>30>40 | inorder: 20 30 35 40 50 60 70 80 | height 3
insert 45, path 50>30>40 | inorder: 20 30 35 40 45 50 60 70 80 | height 3
delete 30 (two children, successor 35) | inorder: 20 35 40 45 50 60 70 80 | height 3

৭ · এটি কি BST? — যাচাইয়ের ভুল আর সঠিক উপায়

“একটি binary tree দেওয়া আছে, এটি BST কি না বলুন” — ইন্টারভিউ আর পরীক্ষার খুব প্রচলিত প্রশ্ন, আর এর প্রথম সমাধানটি প্রায় সবাই ভুল লেখেন। ভুলটি হলো প্রতিটি node-কে শুধু তার সরাসরি সন্তানের সাথে মেলানো: left.key < node.key < right.key, তারপর recursion. এটি দেখতে ঠিক, ছোট উদাহরণে উত্তরও ঠিক দেয়। কিন্তু অংশ ১-এর tree-টি দেখুন:

        10          node 10:  5 < 10 < 15     ঠিক
       /  \         node 15:  6 < 15 < 20     ঠিক
      5    15
          /  \      কিন্তু 6 আছে 10-এর ডান subtree-তে,
         6    20    তাই 6-কে অবশ্যই 10-এর চেয়ে বড় হতে হতো।

সঠিক উপায় ১ — সীমা নিয়ে নামা. প্রতিটি node-এর key একটি খোলা ব্যবধি (lo, hi)-এর মধ্যে থাকতে হবে, যেটি তার সব পূর্বপুরুষ মিলে ঠিক করে। root-এর জন্য (−∞, +∞). বাঁয়ে নামলে ওপরের সীমা হয় node-এর key (বাঁ দিকের সবাই এর চেয়ে ছোট), ডানে নামলে নিচের সীমা। Tricky tree-তে: 10-এর ব্যবধি (−∞, ∞) ✓; 15-এর (10, ∞) ✓; 6-এর (10, 15) — 6 < 10, ✗. ধরা পড়ল।

Pseudocode — validate a BST (distinct keys, strict order)

valid(t, lo, hi):                      // call valid(root, -inf, +inf)
    if t == null: return true
    if not (lo < t.key < hi): return false
    return valid(t.left, lo, t.key) and valid(t.right, t.key, hi)

// alternative: inorder walk, every key must be greater than the previous one
validInorder(t):  prev = -inf;  for each key k in inorder(t): if k <= prev: return false; prev = k
                  return true

সঠিক উপায় ২ — inorder-এ হাঁটা. অংশ ৪-এর প্রমাণ অনুযায়ী (আলাদা key ধরে) tree-টি BST ঠিক তখনই, যখন inorder ক্রম কঠোরভাবে বাড়ে। শুধু আগের মানটি মনে রেখে হাঁটলেই চলে, পুরো তালিকা রাখার দরকার নেই। দুই পদ্ধতিতেই প্রতিটি node একবার: সময় Θ(n) (খারাপ tree আগেই ধরা পড়লে কম), বাড়তি জায়গা recursion-এর জন্য O(h).

• সীমার ফাঁদ: −∞/+∞ হিসেবে INT_MIN/INT_MAX নিলে, key নিজেই INT_MIN হলে কঠোর তুলনা lo < key মিথ্যা হয়ে বৈধ tree-কে অবৈধ বলবে। সমাধান: long long সীমা, অথবা “সীমা নেই” বোঝাতে null pointer বা std::optional.
• ডুপ্লিকেটের নীতি: অংশ ১-এর “সমান হলে ডানে” নীতি নিলে যাচাইও বদলায়: বাঁয়ে key < hi, ডানে key ≥ lo. যাচাই আর insert-এর নীতি এক না হলে যাচাই নিজেই ভুল।
• Subtree-র min/max ফেরত দেওয়া আরেকটি সঠিক পদ্ধতি (post-order-এ প্রতিটি subtree নিজের min, max আর বৈধতা ফেরত দেয়) — একই O(n).

৮ · BST-কে আরও কাজে লাগানো — floor/ceil, range query আর k-তম ছোট

Hash table (পর্ব ৩২) “k আছে কি?” প্রশ্নে BST-কে হারিয়ে দেয়। কিন্তু BST-র আসল শক্তি ক্রমের প্রশ্নে — যেগুলো hash table মোটেই পারে না।

Floor আর ceil

x-এর floor হলো tree-র x-এর সমান বা ছোট key-গুলোর মধ্যে সবচেয়ে বড়; ceil হলো x-এর সমান বা বড়গুলোর মধ্যে সবচেয়ে ছোট। যেমন বাসের ভাড়ার স্তর 20, 35, 50, 80 টাকার কোনটি একজন যাত্রীর কাছে থাকা 60 টাকার মধ্যে সর্বোচ্চ — floor(60) = 50. খোঁজার মতো নামুন, আর পথে প্রার্থী মনে রাখুন: floor-এর জন্য, t.key ≤ x হলে t একজন প্রার্থী (এবং আরও ভালো প্রার্থী থাকলে ডানে), নইলে বাঁয়ে যান। শেষ যে প্রার্থী মনে রেখেছেন, সেটিই উত্তর। এটি সাজানো অ্যারের lower_bound/upper_bound-এর (পর্ব ১৮) BST রূপ; std::set-এ এগুলো তৈরি আছে, সময় O(h).

উদাহরণ — অংশ ৫-এর শেষ tree (root 60; বাঁয়ে 40, তার সন্তান 35, 45; ডানে 70, তার সন্তান 65, 80)-এ floor(50): 60 > 50 → বাঁয়ে; 40 ≤ 50 → প্রার্থী 40, ডানে; 45 ≤ 50 → প্রার্থী 45, ডানে; null → উত্তর 45. ceil(50): 60 ≥ 50 → প্রার্থী 60, বাঁয়ে; 40 < 50 → ডানে; 45 < 50 → ডানে; null → উত্তর 60.

Range query — [l, r]-এর সব key

“ঢাকার যেসব গ্রাহকের বয়স ২০ থেকে ৩০” — অর্থাৎ l ≤ key ≤ r এমন সব key ছাপাতে হবে। Inorder traversal চালান, কিন্তু অপ্রয়োজনীয় দিক ছেঁটে দিন: t.key > l হলে বাঁ subtree-তে যান (সেখানে l-এর চেয়ে বড় কেউ থাকতে পারে), l ≤ t.key ≤ r হলে ছাপান, t.key < r হলে ডানে যান। খরচ O(h + k), যেখানে k হলো উত্তরে কয়টি key — সীমানার দুটি পথ ধরে O(h), আর বাকি সময় শুধু উত্তরের node-গুলোতে। Range query-র এই ধাঁচ ডেটাবেসের index-এ সবসময় চলে (সেখানে B+ tree, পর্ব ৩০)।

Subtree-র আকার রাখা — order-statistic tree

“k-তম ছোট key কোনটি?” বা “x-এর চেয়ে ছোট কয়টি key?” — প্রথমটি order statistic, দ্বিতীয়টি rank. সাধারণ BST-তে inorder-এ k টি পর্যন্ত গুনে O(h + k). কিন্তু প্রতিটি node-এ একটি বাড়তি সংখ্যা রাখুন — size = তার subtree-তে কয়টি node — তাহলে দুটোই O(h). এমন বাড়তি তথ্যসহ BST-কে বলে order-statistic tree, আর এটি augmented data structure-এর সবচেয়ে পরিচিত উদাহরণ।

Pseudocode — order statistics with subtree sizes (k is 1-based; size(null) = 0)

kth(t, k):                              // requires 1 <= k <= size(t)
    s = size(t.left)
    if k <= s:      return kth(t.left, k)
    if k == s + 1:  return t.key
    return kth(t.right, k - s - 1)      // skip the left subtree and t itself

rank(t, x):                             // how many keys are < x
    if t == null: return 0
    if x <= t.key: return rank(t.left, x)
    return size(t.left) + 1 + rank(t.right, x)

countInRange(l, r) = rank(root, r + 1) - rank(root, l)     // integer keys in [l, r]

উদাহরণ — একই শেষ tree-তে size: 35, 45, 65, 80 প্রতিটি 1; 40 আর 70 প্রতিটি 3; root 60-এর 7. kth(root, 5): বাঁয়ের size 3, 5 > 3 + 1 = 4, তাই ডানে k = 5 − 4 = 1; 70-এর বাঁয়ের size 1, k = 1 ≤ 1 → বাঁয়ে; 65-এর বাঁয়ে size 0, k = 1 = 0 + 1 → উত্তর 65. মিলিয়ে দেখুন: 35 40 45 60 65 — পঞ্চম। size ঠিক রাখার খরচ সামান্য: insert আর delete-এর পথে প্রতিটি node-এর size এক বাড়ে বা কমে, তাই খরচ O(h)-ই থাকে। আর countInRange দুটি rank-এর বিয়োগে [l, r]-এ কয়টি key, তাও O(h) — উত্তর যত বড়ই হোক।

৯ · কোনটি কখন — BST, সাজানো অ্যারে না hash table; আর ভারসাম্য কেন জরুরি

সিদ্ধান্তের সরল নিয়ম: ডেটা একবার বানিয়ে শুধু প্রশ্ন করবেন (বদলাবে না)? সাজানো অ্যারে + binary search — সবচেয়ে কম মেমরি আর cache-বান্ধব। শুধু “আছে কি / মান কত” প্রশ্ন, ক্রমের দরকার নেই? Hash table. বারবার বদলাবে আর ক্রমের প্রশ্নও লাগবে (successor, range, floor, k-তম)? ভারসাম্যপূর্ণ BST. আর সাধারণ, ভারসাম্যহীন BST? শেখা, বোঝা আর ছোট পরীক্ষার জন্য চমৎকার — কিন্তু অজানা ইনপুটের production বা কনটেস্টের কোডে বিপজ্জনক, কারণ অংশ ৬-এর শিকল।

ভারসাম্য — পরের দুই পর্বের প্রতিশ্রুতি

সমাধান হলো এমন BST, যা প্রতিটি insert আর delete-এর পর কয়েকটি ছোট পুনর্বিন্যাস (rotation) করে উচ্চতা O(log n)-এ বেঁধে রাখে — self-balancing BST. প্রথমটি AVL tree (১৯৬২, Georgy Adelson-Velsky আর Evgenii Landis): প্রতিটি node-এর দুই subtree-র উচ্চতার পার্থক্য সর্বোচ্চ ১ — পর্ব ২৮. পরে আসে red-black tree (১৯৭৮ সালে Leonidas Guibas আর Robert Sedgewick-এর রূপ, Rudolf Bayer-এর ১৯৭২ সালের কাজের ওপর ভিত্তি করে): ভারসাম্যের নিয়ম একটু ঢিলে, কিন্তু insert/delete-এ rotation কম — পর্ব ২৯. Search, successor, floor, range, k-তম — এই পর্বের প্রতিটি অ্যালগরিদম সেগুলোতে হুবহু একই থাকে; শুধু insert আর delete-এর শেষে সারানোর ধাপ যোগ হয়।

আপনি হয়তো ইতিমধ্যে ব্যবহার করছেন। পর্ব ১৫-এর std::set, std::map, std::multiset হলো ভারসাম্যপূর্ণ BST — C++ standard শুধু O(log n) চায়, আর প্রধান বাস্তবায়নগুলো (GCC-র libstdc++, LLVM-এর libc++, Microsoft-এর STL) red-black tree ব্যবহার করে। এই পর্বের কাজগুলোর নাম সেখানে: insert, find, erase, begin() (min), prev(end()) (max), iterator ++/-- (successor/predecessor), lower_bound(x) (ceil), upper_bound(x) আর এক ধাপ পেছনে (floor). Java-র TreeMap/TreeSet-ও red-black tree. Python-এর standard library-তে কোনো ভারসাম্যপূর্ণ BST নেই; প্রচলিত বিকল্প হলো bisect দিয়ে সাজানো list (insert O(n), কিন্তু ছোট n-এ দ্রুত) বা তৃতীয় পক্ষের sortedcontainers প্যাকেজ — কনটেস্টের judge-এ সাধারণত শুধু standard library থাকে।

#include <set>
std::set<int> s{35, 40, 45, 60, 65, 70, 80};      // a red-black tree inside
auto it = s.lower_bound(50);                       // ceil(50): first key >= 50 -> 60
auto fl = s.upper_bound(50);                       // first key > 50 ...
if (fl != s.begin()) --fl;                         // ... one step back: floor(50) -> 45
int lo = *s.begin(), hi = *s.rbegin();             // min 35, max 80  (set must be non-empty)
for (auto p = s.lower_bound(40); p != s.end() && *p <= 65; ++p) { /* range [40, 65] */ }
// std::distance(s.begin(), it) would give the rank, but it walks: O(n), not O(log n)

শেষ মন্তব্যটি গুরুত্বপূর্ণ: std::set-এ subtree-র size রাখা হয় না, তাই k-তম ছোট বা rank O(log n)-এ পাওয়া যায় না — std::distance বা std::next(begin, k) এক এক করে হাঁটে। কনটেস্টে এর জন্য GCC-র একটি এক্সটেনশন ব্যবহার করা হয় (নিচে “আরও গভীরে”), অথবা key-এর পরিসর ছোট হলে Fenwick tree বা segment tree (পর্ব ৩৪–৩৬)।

১০ · AI-এর যুগে BST — কোড চলে, নিয়ম ভাঙে

“একটি BST-র delete লিখে দাও” — AI প্রায় সবসময় পরিপাটি কোড দেবে, আর leaf মোছার ছোট পরীক্ষায় সেটি চলবেও। ভুলগুলো লুকিয়ে থাকে কম-ঘটা শাখায়: দুই-সন্তানের delete-এ successor-কে ডান subtree থেকে না মুছে আবার root থেকে মোছা (খোঁজা তখন কপি-করা key নিয়ে z-এর ঘরেই থামে — ভুল node মোছে বা recursion থামে না), root মুছলে নতুন root ফেরত না দেওয়া, বা BST যাচাইয়ে শুধু সন্তানের সাথে মেলানো। আর complexity জিজ্ঞেস করলে AI প্রায়ই নিশ্চিন্তে বলে “BST-তে search O(log n)” — শর্তটি (ভারসাম্য) বাদ দিয়ে।

BST-এর কোডে AI সাধারণত যেসব ভুল করে

BST-এর কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি কাজের পর inorder ছেপে দেখেছি সেটি কঠোরভাবে বাড়ছে, আর সীমা-ভিত্তিক isBST দিয়ে assert করেছি
• Delete-এর তিন অবস্থাই আলাদা করে চালিয়েছি — leaf, এক সন্তান (বাঁ ও ডান দুটোই), দুই সন্তান, আর root নিজে
• Edge case: খালি tree, এক node, ডুপ্লিকেট key, নেই এমন key মোছা, সাজানো ও উল্টো-সাজানো ইনপুট
• হাজারটি এলোমেলো insert/delete-এর পর ফলাফল std::set বা সাজানো list-এর সাথে মিলিয়েছি — stress testing
• k-তম ছোট বা range count-এর উত্তর সাজিয়ে গোনা brute force-এর সাথে মিলিয়েছি
• Complexity লেখার সময় h ব্যবহার করেছি, আর ভারসাম্যের শর্ত ছাড়া O(log n) দাবি করিনি