থ্রেডেড বাইনারি ট্রি হল একটি বাইনারি ট্রি যা একটি নির্দিষ্ট ক্রমে গাছটিকে অতিক্রম করার সুবিধা প্রদান করে৷
এটি ইনঅর্ডার ট্রাভার্সালকে দ্রুত করে তোলে এবং এটি স্ট্যাক ছাড়া এবং পুনরাবৃত্তি ছাড়াই করে। দুই ধরনের থ্রেডেড বাইনারি গাছ আছে।
একক থ্রেডেড প্রতিটি নোড বাম বা ডান দিকে থ্রেড করা হয় মানে পূর্বসূরী বা উত্তরাধিকারী। এখানে, সমস্ত ডান নাল পয়েন্টার ইনঅর্ডার উত্তরসূরিকে নির্দেশ করবে বা সমস্ত বাম নাল পয়েন্টার ইনঅর্ডার পূর্বসূরকে নির্দেশ করবে।
ডাবল থ্রেডেড প্রতিটি নোড বাম এবং ডান দিকে থ্রেড করা হয় মানে ইন-অর্ডার পূর্বসূরী এবং উত্তরাধিকারী। এখানে, সমস্ত ডান নাল পয়েন্টার ইনঅর্ডার উত্তরসূরি নির্দেশ করবে এবং সমস্ত বাম নাল পয়েন্টার ইনঅর্ডার পূর্বসূরকে নির্দেশ করবে।
এটি থ্রেডেড বাইনারি ট্রি বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম।
ফাংশন এবং সিউডোকোড
ফাংশন সন্নিবেশ()
Insert node as root if tree is completely empty. Otherwise, if newnode < current node then Go to left thread and set the newnode as left child. else Go to right thread and set the newnode as right child.
ফাংশন অনুসন্ধান()
If search key < root then Go to left thread else Go to right thread
ফাংশন ডিলিট()
নোড এবং এর অভিভাবক খুঁজুন। নোড মুছে ফেলার জন্য তিনটি ক্ষেত্রে আছে -
- নোড যার দুটি সন্তান আছে৷ ৷
- শুধু সন্তান রেখে গেছেন।
- শুধুমাত্র সন্তান আছে।
উদাহরণ
#include <iostream>
#include <cstdlib>
#define MAX_VALUE 65536
using namespace std;
class N { //node declaration
public:
int k;
N *l, *r;
bool leftTh, rightTh;
};
class ThreadedBinaryTree {
private:
N *root;
public:
ThreadedBinaryTree() { //constructor to initialize the variables
root= new N();
root->r= root->l= root;
root->leftTh = true;
root->k = MAX_VALUE;
}
void makeEmpty() { //clear tree
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) { / /move to right thread
if (p->rightTh)
break;
p = p->r;
} else if (p->k > key) { // move to left thread
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) { //search in left thread
if (temp->rightTh)
return false;
temp = temp->r;
} else if (temp->k > key) { //search in right thread
if (temp->leftTh)
return false;
temp = temp->l;
} else {
return true;
}
}
}
void Delete(int key) {
N *dest = root->l, *p = root;
for (;;) { //find Node and its parent.
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; //has two children
target = dest->l; //largest node at left child
while (!target->rightTh) {
p = target;
target = target->r;
}
dest->k= target->k; //replace mode
}
if (p->k >= target->k) { //only left child
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 {//only right child
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() { //print the tree
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;
//perform switch operation
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";
}
}
cout<<"\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 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 7 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 6 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 4 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 5 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 3 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 5 Display tree 3 4 5 6 7 10 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 3 Enter integer element to search: 7 Element 7 found in the tree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 3 Enter integer element to search: 1 Element 1 not found in the tree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 2 Enter integer element to delete: 3 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 5 Display tree 4 5 6 7 10 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 4 Tree Cleared 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 5 Display tree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 6
