C++-এ থ্রেডেড বাইনারি ট্রি (Threaded Binary Tree) ইমপ্লিমেন্টেশন

থ্রেডেড বাইনারি ট্রি (Threaded binary tree) একটি বাইনারি ট্রি যা ট্রি-ট্রাভার্সাল (tree traversal) একটি নির্দিষ্ট অর্ডারে দ্রুত করার সুবিধা দেয়।

এটি ইনঅর্ডার ট্রাভার্সাল (inorder traversal) কে দ্রুত করে এবং স্ট্যাক বা রিকার্শন ছাড়াই এটি করতে পারে। থ্রেডেড বাইনারি ট্রির দুটি ধরন রয়েছে:

• সিঙ্গেল থ্রেডেড (Single Threaded): প্রতিটি নোড বাম বা ডান দিকে থ্রেডেড থাকে (ইনঅর্ডার প্রিডিসেসর বা সাকসেসর)। এখানে সব ডান নাল পয়েন্টার ইনঅর্ডার সাকসেসরের দিকে পয়েন্ট করবে বা সব বাম নাল পয়েন্টার ইনঅর্ডার প্রিডিসেসরের দিকে পয়েন্ট করবে।
• ডাবল থ্রেডেড (Double threaded): প্রতিটি নোড দুদিকেই থ্রেডেড থাকে (ইনঅর্ডার প্রিডিসেসর এবং সাকসেসর)। এখানে সব ডান নাল পয়েন্টার ইনঅর্ডার সাকসেসরের দিকে এবং সব বাম নাল পয়েন্টার ইনঅর্ডার প্রিডিসেসরের দিকে পয়েন্ট করবে।

নিচে থ্রেডেড বাইনারি ট্রি ইমপ্লিমেন্ট করার C++ প্রোগ্রাম দেওয়া হলো।

ফাংশন ও সিউডোকোড

function insert()

যদি ট্রি সম্পূর্ণ খালি হয়, তবে নোডটি রুট হিসেবে ইনসার্ট করুন।
অন্যথায়, যদি newnode < current node হয়, তবে
    বাম থ্রেডে যান এবং newnode কে বাম চাইল্ড হিসেবে সেট করুন।
অন্যথায়
    ডান থ্রেডে যান এবং newnode কে ডান চাইল্ড হিসেবে সেট করুন।

function search()

যদি সার্চ কী < রুট হয়, তবে
    বাম থ্রেডে যান
অন্যথায়
    ডান থ্রেডে যান

function delete()

নোড এবং এর প্যারেন্ট (parent) খুঁজে বের করুন। নোড ডিলিট করার তিনটি কেস রয়েছে:

• নোড যার দুইটি চাইল্ড আছে।
• শুধু বাম চাইল্ড আছে।
• শুধু ডান চাইল্ড আছে।

উদাহরণ

#include <iostream>
#include <cstdlib>
#define MAX_VALUE 65536
using namespace std;

class N { // নোড ডিক্লেয়ারেশন
public:
    int k;
    N *l, *r;
    bool leftTh, rightTh;
};

class ThreadedBinaryTree {
private:
    N *root;
public:
    ThreadedBinaryTree() { // কনস্ট্রাক্টর
        root = new N();
        root->r = root->l = root;
        root->leftTh = true;
        root->k = MAX_VALUE;
    }
    void makeEmpty() { // ট্রি ক্লিয়ার
        root = new N();
        root->r = root->l = root;
        root->leftTh = true;
        root->k = MAX_VALUE;
    }
    void insert(int key) {
        N *p = root;
        for (;;) {
            if (p->k < key) { // ডান থ্রেডে যান
                if (p->rightTh) break;
                p = p->r;
            } else if (p->k > key) { // বাম থ্রেডে যান
                if (p->leftTh) break;
                p = p->l;
            } else {
                return;
            }
        }
        N *temp = new N();
        temp->k = key;
        temp->rightTh = temp->leftTh = true;
        if (p->k < key) {
            temp->r = p->r;
            temp->l = p;
            p->r = temp;
            p->rightTh = false;
        } else {
            temp->r = p;
            temp->l = p->l;
            p->l = temp;
            p->leftTh = false;
        }
    }
    bool search(int key) {
        N *temp = root->l;
        for (;;) {
            if (temp->k < key) { // বাম থ্রেডে সার্চ
                if (temp->rightTh) return false;
                temp = temp->r;
            } else if (temp->k > key) { // ডান থ্রেডে সার্চ
                if (temp->leftTh) return false;
                temp = temp->l;
            } else {
                return true;
            }
        }
    }
    void Delete(int key) {
        N *dest = root->l, *p = root;
        for (;;) { // নোড এবং এর প্যারেন্ট খুঁজুন
            if (dest->k < key) {
                if (dest->rightTh) return;
                p = dest;
                dest = dest->r;
            } else if (dest->k > key) {
                if (dest->leftTh) return;
                p = dest;
                dest = dest->l;
            } else {
                break;
            }
        }
        N *target = dest;
        if (!dest->rightTh && !dest->leftTh) { // দুইটি চাইল্ড আছে
            p = dest;
            target = dest->l; // বাম চাইল্ডের লার্জেস্ট নোড
            while (!target->rightTh) {
                p = target;
                target = target->r;
            }
            dest->k = target->k; // রিপ্লেস
        }
        if (p->k >= target->k) { // শুধু বাম চাইল্ড
            if (target->rightTh && target->leftTh) {
                p->l = target->l;
                p->leftTh = true;
            } else if (target->rightTh) {
                N* largest = target->l;
                while (!largest->rightTh) largest = largest->r;
                largest->r = p;
                p->l = target->l;
            } else {
                N *smallest = target->r;
                while (!smallest->leftTh) smallest = smallest->l;
                smallest->l = target->l;
                p->l = target->r;
            }
        } else { // শুধু ডান চাইল্ড
            if (target->rightTh && target->leftTh) {
                p->r = target->r;
                p->rightTh = true;
            } else if (target->rightTh) {
                N *largest = target->l;
                while (!largest->rightTh) largest = largest->r;
                largest->r = target->r;
                p->r = target->l;
            } else {
                N *smallest = target->r;
                while (!smallest->leftTh) smallest = smallest->l;
                smallest->l = p;
                p->r = target->r;
            }
        }
    }
    void displayTree() { // ট্রি প্রিন্ট
        N *temp = root, *p;
        for (;;) {
            p = temp;
            temp = temp->r;
            if (!p->rightTh) {
                while (!temp->leftTh) {
                    temp = temp->l;
                }
            }
            if (temp == root) break;
            cout << temp->k << " ";
        }
        cout << endl;
    }
};

int main() {
    ThreadedBinaryTree tbt;
    cout << "ThreadedBinaryTree\n";
    char ch;
    int c, v;
    while(1) {
        cout << "1. Insert " << endl;
        cout << "2. Delete" << endl;
        cout << "3. Search" << endl;
        cout << "4. Clear" << endl;
        cout << "5. Display" << endl;
        cout << "6. Exit" << endl;
        cout << "Enter Your Choice: ";
        cin >> c;
        switch (c) {
            case 1:
                cout << "Enter integer element to insert: ";
                cin >> v;
                tbt.insert(v);
                break;
            case 2:
                cout << "Enter integer element to delete: ";
                cin >> v;
                tbt.Delete(v);
                break;
            case 3:
                cout << "Enter integer element to search: ";
                cin >> v;
                if (tbt.search(v) == true)
                    cout << "Element " << v << " found in the tree" << endl;
                else
                    cout << "Element " << v << " not found in the tree" << endl;
                break;
            case 4:
                cout << "\nTree Cleared\n";
                tbt.makeEmpty();
                break;
            case 5:
                cout << "Display tree: \n";
                tbt.displayTree();
                break;
            case 6:
                exit(1);
            default:
                cout << "\nInvalid type! \n";
        }
    }
    return 0;
}

আউটপুট (স্যাম্পল রান)

ThreadedBinaryTree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 10
...
Display tree
3 4 5 6 7 10
...
Element 7 found in the tree
...
Element 1 not found in the tree
...
Display tree
4 5 6 7 10
...
Tree Cleared
Display tree
(empty)
Enter Your Choice: 6