ট্রি ও BST — ডেটাকে শাখা-প্রশাখায় সাজানো

১ · চারপাশে সবখানে ট্রি — ফোল্ডার থেকে উপজেলা পর্যন্ত

আগের দুটি পর্বে আমরা linked list, stack আর queue বানিয়েছি। তিনটিই এক সারির কাঠামো — একটির পরে আরেকটি। কিন্তু বাস্তবের অনেক তথ্য এক সারিতে সাজানো যায় না। আপনার কম্পিউটারের D: ড্রাইভ খুলুন। ভেতরে কয়েকটি ফোল্ডার, প্রতিটির ভেতরে আরও ফোল্ডার, তার ভেতরে ফাইল। এটি সারি নয় — এটি শাখা-প্রশাখা।

বাংলাদেশের প্রশাসনিক কাঠামোও ঠিক তাই। দেশ ভাগ হয়েছে ৮টি বিভাগে, বিভাগ ভাগ হয়েছে জেলায় (মোট ৬৪টি), জেলা ভাগ হয়েছে উপজেলায়, উপজেলা ইউনিয়নে। প্রতিটি জেলা ঠিক একটি বিভাগের অধীনে — কোনো জেলা একসাথে দুই বিভাগে থাকে না। এমন ওপর-নিচ সম্পর্ককে বলে hierarchy, আর কম্পিউটারে একে রাখার কাঠামোর নাম tree বা ট্রি।

বাংলাদেশ                      ← root (সবার ওপরে, কোনো parent নেই)
├── ঢাকা বিভাগ
│   ├── ঢাকা জেলা
│   │   ├── সাভার উপজেলা       ← leaf (এখানে আর ভাগ দেখানো হয়নি)
│   │   └── ধামরাই উপজেলা      ← leaf
│   └── গাজীপুর জেলা           ← leaf
└── রাজশাহী বিভাগ
    └── বগুড়া জেলা
        └── শাজাহানপুর উপজেলা  ← leaf

কম্পিউটারের ট্রি অবশ্য উল্টো করে আঁকা হয় — root থাকে ওপরে, পাতা নিচে। প্রকৃতির গাছের উল্টো, কিন্তু পরিবারের বংশতালিকার মতো: দাদা ওপরে, নাতি-নাতনি নিচে। ট্রির প্রতিটি ঘরকে বলে node, আর দুটি নোডের সংযোগকে বলে edge. নিচের শব্দগুলো এই পর্ব জুড়ে বারবার আসবে:

২ · C-তে একটি নোড — ডেটা আর দুটি pointer

সাধারণ ট্রিতে একটি নোডের যতখুশি child থাকতে পারে — ঢাকা বিভাগের নিচে ১৩টি জেলা। কিন্তু প্রোগ্রামিংয়ে সবচেয়ে বেশি ব্যবহৃত রূপটি হলো binary tree, যেখানে প্রতিটি নোডের সর্বোচ্চ দুটি child: একটি বাঁয়ে (left), একটি ডানে (right), এর বেশি নয়। পর্ব ৩৩-এর linked list-এর নোডে পরের নোডের ঠিকানা ছিল একটি; এখানে দুটি। ব্যস, এটুকুই পার্থক্য।

typedef struct Node {
    int key;               // নোডের ডেটা
    struct Node *left;     // বাঁ child-এর ঠিকানা (না থাকলে NULL)
    struct Node *right;    // ডান child-এর ঠিকানা (না থাকলে NULL)
} Node;

Node *root = NULL;         // খালি ট্রি = NULL pointer

এই কাঠামোটি struct — পর্ব ২২-এ শেখা। প্রতিটি নোড তৈরি হয় malloc দিয়ে, তাই নোডগুলো থাকে heap-এ, মেমরির নানা জায়গায় ছড়িয়ে। নোডগুলোকে একসাথে বেঁধে রাখে শুধু pointer. মেমরির ভেতরে ছোট একটি ট্রি দেখতে এমন (ঠিকানাগুলো কাল্পনিক):

খেয়াল করুন, ডান child-এর ঠিকানা (0x5a20) root-এর চেয়েও ছোট — heap-এ কোন নোড কোথায় বসবে তার কোনো ক্রম নেই। ট্রির “আকার” মেমরির অবস্থানে নেই, আছে শুধু pointer-গুলোর ভেতরে। আর দুটি NULL-ওয়ালা নোডগুলো leaf.

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

যেকোনো binary tree-তে মান যেখানে খুশি রাখা যায়। কিন্তু একটি ছোট নিয়ম যোগ করলেই ট্রিটি হয়ে ওঠে অসাধারণ দ্রুত একটি খোঁজার যন্ত্র। নিয়মটির নাম Binary Search Tree বা BST:

লক্ষ করুন “সব” শব্দটি। শুধু সরাসরি child নয়, নিচের পুরো বংশই নিয়ম মানবে। নতুন মান ঢোকানোর (insert) পদ্ধতি তাই খুব সহজ: root থেকে শুরু করুন। নতুন মান ছোট হলে বাঁয়ে নামুন, বড় হলে ডানে। যেখানে গিয়ে NULL পাবেন, সেখানেই নতুন নোড বসবে। নিচের ডায়াগ্রামে ৫০, ৩০, ৭০, ২০, ৪০, ৬০, ৮০ — এই ক্রমে সাতটি মান ঢোকানো দেখুন। লাল দাগ দেখাবে নতুন মানটি কোন পথে নেমেছে।

৪ · খোঁজা — প্রতিটি প্রশ্নে অর্ধেক বাদ

পর্ব ০২-এর সেই খেলাটি মনে আছে? বন্ধু ১ থেকে ১০০-এর মধ্যে একটি সংখ্যা ভেবেছিল, আর আপনি প্রতিবার মাঝখানের সংখ্যা বলে অর্ধেক সম্ভাবনা বাদ দিচ্ছিলেন — সাত প্রশ্নের মধ্যেই উত্তর। BST সেই খেলারই একটি স্থায়ী রূপ। প্রতিটি নোড একটি “মাঝখানের সংখ্যা”: খোঁজা মান ছোট হলে ডান দিকের পুরো অংশ এক তুলনাতেই বাদ, বড় হলে বাঁ দিকের পুরো অংশ বাদ। নিচে ৬০ খুঁজে দেখি, তারপর এমন একটি মান খুঁজব যা ট্রিতে নেই।

প্রতিবার মান দ্বিগুণ হলে BST-তে মাত্র একটি তুলনা বাড়ে। একে বলে logarithmic সময়, লেখা হয় O(log n) — পর্ব ৩৯-এ time complexity নিয়ে বিস্তারিত দেখব। এটি সেই binary search-এর গতি, কিন্তু একটি বড় সুবিধাসহ: সাজানো অ্যারেতে নতুন মান ঢোকাতে পেছনের সব ঘর এক ঘর করে সরাতে হয়, আর BST-তে শুধু একটি pointer বসালেই চলে।

৫ · ট্রি ঘুরে দেখা — চার রকম traversal

অ্যারে বা linked list-এর সব মান ছাপানো সহজ — শুরু থেকে শেষ পর্যন্ত হাঁটলেই হলো। কিন্তু ট্রির তো “শেষ” একটি নয়, অনেকগুলো শাখা। প্রতিটি নোডে ঠিক একবার যাওয়ার নিয়মকে বলে traversal. প্রতিটি নোডে তিনটি কাজ আছে — বাঁ subtree ঘোরা, নিজেকে ছাপা, ডান subtree ঘোরা। এই তিনটির ক্রম বদলালেই ভিন্ন traversal:

প্রথম তিনটির নাম inorder, preorder আর postorder — “নিজে” কাজটি কখন হচ্ছে (মাঝে, আগে, পরে) সেটি দিয়েই নাম। তিনটিই তিন লাইনের recursive ফাংশন। সবচেয়ে চমকপ্রদটি হলো inorder: BST-তে এটি সবসময় সাজানো ক্রম দেয়। কেন? কারণ প্রতিটি নোডে আমরা আগে তার বাঁ দিকের সব (যারা ছোট) ছাপি, তারপর নিজেকে, তারপর ডানের সব (যারা বড়)। ধাপে ধাপে দেখুন:

Level-order — যেখানে recursion নয়, queue লাগে

চতুর্থ traversal, level-order, একটু আলাদা। আগে root, তারপর তার দুই child, তারপর নাতি-নাতনিরা — স্তরে স্তরে। এটি recursion দিয়ে সহজে হয় না, কারণ recursion একটি শাখার গভীরে নেমে যায়। এখানে দরকার পর্ব ৩৪-এর queue: root-কে queue-তে রাখুন। তারপর বারবার — সামনের নোডটি বের করুন, ছাপুন, তার left আর right (যদি থাকে) queue-র পেছনে রাখুন। queue খালি হলে কাজ শেষ।

queue: [50]          → বের করি 50, ঢোকাই 30, 70
queue: [30, 70]      → বের করি 30, ঢোকাই 20, 40
queue: [70, 20, 40]  → বের করি 70, ঢোকাই 60, 80
queue: [20, 40, 60, 80] → চারটিই leaf, একে একে বের হয়
আউটপুট: 50 30 70 20 40 60 80

Queue “আগে এলে আগে যাবে” নিয়ম মানে বলে কাছের স্তরের নোড সবসময় দূরের স্তরের আগে বের হয়। গ্রাফে এই একই কৌশলের নাম BFS (Breadth-First Search) — পর্ব ৩৮-এ পুরোটা দেখব। বাস্তবে এটি কাজে লাগে যখন “সবচেয়ে কাছের” কিছু আগে চাই: যেমন একটি কোম্পানির org chart-এ “MD থেকে দুই ধাপ নিচে কারা আছেন?”

সব একসাথে — insert, inorder আর free

এবার পুরো ব্যাপারটি C-তে। নিচের প্রোগ্রামটি আটটি মান ঢোকায় (শেষের ৪০ ইচ্ছা করে দ্বিতীয়বার দেওয়া), inorder-এ ছাপে, তারপর পুরো ট্রি মুক্ত করে। চালিয়ে দেখুন:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int key; struct Node *left, *right; } Node;
Node *insert(Node *t, int key) {
    if (t == NULL) {                       // খালি জায়গা: এখানেই নতুন নোড
        Node *n = malloc(sizeof *n);
        if (n == NULL) exit(1);
        n->key = key; n->left = n->right = NULL;
        return n;
    }
    if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key) t->right = insert(t->right, key);
    return t;                              // সমান হলে: উপেক্ষা
}
void inorder(const Node *t) {
    if (t) { inorder(t->left); printf("%d ", t->key); inorder(t->right); }
}
void free_tree(Node *t) {                  // postorder: আগে সন্তান, পরে নিজে
    if (t) { free_tree(t->left); free_tree(t->right); free(t); }
}
int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80, 40}; Node *root = NULL;
    for (int i = 0; i < 8; i++) root = insert(root, keys[i]);
    inorder(root); printf("\n");
    free_tree(root); return 0;
}

৬ · মুছে ফেলা — তিনটি অবস্থা

Insert আর search সহজ, কারণ নতুন নোড সবসময় একটি খালি জায়গায় (leaf-এর নিচে) বসে। কিন্তু delete-এ মাঝখানের কোনো নোডও সরাতে হতে পারে, আর তখন তার সন্তানদের কোথাও না কোথাও জুড়ে দিতে হয় — BST-এর নিয়ম না ভেঙে। আগে delete করার নোডটি খুঁজে বের করুন (খোঁজার মতোই হাঁটা), তারপর দেখুন তার কয়টি child:

তৃতীয় অবস্থার “ঠিক পরের মান”-কে বলে inorder successor — inorder ক্রমে যে মান এর ঠিক পরে আসে। আমাদের মূল ট্রিতে ৫০-এর পরে ৬০. একে পাওয়ার নিয়ম: একবার ডানে, তারপর যতদূর যায় বাঁয়ে। ডান subtree-র সবাই ৫০-এর চেয়ে বড়, আর তাদের মধ্যে সবচেয়ে ছোটটি থাকে সবচেয়ে বাঁয়ে।

আগে:            ৫০-এর জায়গায় ৬০ বসানো:     পুরোনো ৬০ (leaf) মোছা:
      50                 60                         60
     /  \               /  \                       /  \
   30    70           30    70                   30    70
  / \   / \          / \   / \                  / \      \
 20 40 60  80       20 40 60  80               20 40      80
                          ↑ এখন দুইবার আছে

কেন এটি নিয়ম ভাঙে না? ৬০ ছিল ডান subtree-র সবচেয়ে ছোট মান, তাই ডানের বাকি সবার চেয়ে ছোট; আবার ৫০-এর চেয়ে বড় বলে বাঁ দিকের সবার চেয়ে বড়। Root-এর চেয়ারে বসার জন্য সে-ই একমাত্র যোগ্য প্রার্থী। আর একটি সুন্দর তথ্য: successor-এর কখনো বাঁ child থাকে না (থাকলে সে-ই হতো আরও ছোট)। তাই তাকে মোছা সবসময় অবস্থা ১ বা ২ — কখনো আবার অবস্থা ৩ নয়। চাইলে successor-এর বদলে predecessor (বাঁ subtree-র সবচেয়ে বড়, অর্থাৎ ৪০) দিয়েও একই কাজ করা যায়।

৭ · ট্রি যখন লাঠি হয়ে যায় — balance কেন জরুরি

এখন পর্যন্ত সব কিছু চমৎকার দেখাল, কারণ আমরা মানগুলো ঢুকিয়েছি একটি ভালো ক্রমে — আগে মাঝের ৫০, তারপর দুই পাশের ৩০ আর ৭০। কিন্তু ধরুন একটি স্কুলের রোল নম্বর আসছে ক্রমানুসারে: ১০, ২০, ৩০, ৪০, ৫০. ঢুকিয়ে দেখুন কী আকার দাঁড়ায়:

এটি কোনো কাল্পনিক সমস্যা নয়। বাস্তবের ডেটা প্রায়ই সাজানো অবস্থায় আসে — রোল নম্বর, ক্রমিক অর্ডার নম্বর, সময় অনুযায়ী লেনদেন, ফাইলের নাম বর্ণানুক্রমে। সাধারণ BST ঠিক এই সাধারণ অবস্থাতেই সবচেয়ে খারাপ আচরণ করে। নিচের প্রোগ্রামটি ১ থেকে ১০০০ পর্যন্ত মান দুইভাবে ঢোকায় — একবার ক্রমানুসারে, একবার “আগে মাঝখান” কৌশলে — তারপর দুটি ট্রির height মাপে:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int key; struct Node *left, *right; } Node;
void insert(Node **p, int key) {            // লুপ দিয়ে, recursion ছাড়া
    while (*p && (*p)->key != key) p = key < (*p)->key ? &(*p)->left : &(*p)->right;
    if (*p) return;                          // আগে থেকেই আছে
    if ((*p = malloc(sizeof **p)) == NULL) exit(1);
    (*p)->key = key; (*p)->left = (*p)->right = NULL;
}
int height(const Node *t) {                 // নোড গুনে: খালি = 0
    if (t == NULL) return 0;
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}
void build(Node **t, int lo, int hi) {      // আগে মাঝখান, তারপর দুই পাশ
    if (lo > hi) return;
    int mid = lo + (hi - lo) / 2;
    insert(t, mid); build(t, lo, mid - 1); build(t, mid + 1, hi);
}
void free_tree(Node *t) { if (t) { free_tree(t->left); free_tree(t->right); free(t); } }
int main(void) {
    Node *stick = NULL, *bushy = NULL;
    for (int k = 1; k <= 1000; k++) insert(&stick, k);
    build(&bushy, 1, 1000);
    printf("sorted order : height = %d\n", height(stick));
    printf("middle first : height = %d\n", height(bushy));
    free_tree(stick); free_tree(bushy); return 0;
}

সমাধান: যে ট্রি নিজেই ভারসাম্য রাখে

সব সময় ডেটার ক্রম আমাদের হাতে থাকে না। তাই কম্পিউটার বিজ্ঞানীরা এমন BST বানিয়েছেন, যা প্রতিটি insert বা delete-এর পর নিজেই পরীক্ষা করে কোথাও বেশি হেলে পড়েছে কি না, আর পড়লে কয়েকটি pointer ঘুরিয়ে (একে বলে rotation) আবার সোজা করে। এদের বলে self-balancing tree. ফলে যে ক্রমেই ডেটা আসুক, height সবসময় log n-এর কাছাকাছি থাকে।

৮ · বাস্তব জগতে ট্রি — আপনি প্রতিদিন যা ব্যবহার করছেন

ট্রি শুধু পরীক্ষার প্রশ্ন নয়। আপনি এই পাতাটি পড়তে পড়তেই অন্তত তিন-চারটি ট্রি কাজ করছে:

আরও একটি জায়গা আছে, যেখানে ট্রি নিজেই সিদ্ধান্ত নেয়। Machine learning-এর decision tree মডেলে প্রতিটি নোড একটি প্রশ্ন: “মাসিক আয় ৩০ হাজারের বেশি?” হ্যাঁ হলে এক শাখা, না হলে আরেক। Leaf-এ পৌঁছালে উত্তর: “ঋণ দেওয়া যায়” বা “ঝুঁকিপূর্ণ”। সুবিধা হলো, একটি ছোট decision tree মানুষ নিজে পড়ে বুঝতে পারে কেন সিদ্ধান্তটি এলো।

৯ · AI-এর যুগে — BST কোড যাচাই

“C-তে একটি BST লিখে দাও” — যেকোনো AI কয়েক সেকেন্ডে লিখে দেবে, আর সাধারণ পরীক্ষায় সেটি ঠিকঠাকই চলবে। সমস্যা লুকিয়ে থাকে কিনারায়: সাজানো ইনপুট, একই মান দুইবার, দুই child-ওয়ালা নোড মোছা, আর প্রোগ্রাম শেষে মেমরি ফেরত দেওয়া। AI-এর শেখার উৎসে পাঠ্যবইয়ের ছোট উদাহরণই বেশি, আর সেখানে এই কিনারাগুলো প্রায়ই দেখানো হয় না।

AI-এর লেখা BST হাতে পেলে — যাচাইয়ের চেকলিস্ট

• -Wall -Wextra দিয়ে compile করেছি, warning শূন্য; -fsanitize=address দিয়ে চালিয়ে কোনো leak বা use-after-free পাইনি
• প্রতিবার insert-এর পর inorder ছাপিয়ে দেখেছি — আউটপুট সবসময় সাজানো
• একই মান দুইবার দিয়ে দেখেছি, আর insert-search-delete তিনটি সমান মানকে একইভাবে দেখে
• Leaf, এক child আর দুই child — তিন রকম নোডই মুছে দেখেছি, root-ও
• সাজানো বড় ইনপুট (কয়েক লাখ) দিয়ে চালিয়েছি — crash করে কি না, কত সময় লাগে
• খালি ট্রিতে search, delete আর free ডেকে দেখেছি — NULL সামলাচ্ছে কি না