C++ में थ्रेडेड बाइनरी ट्री का कार्यान्वयन

थ्रेडेड बाइनरी ट्री एक बाइनरी ट्री है जो किसी विशेष क्रम में ट्री को ट्रैवर्स करने की सुविधा प्रदान करता है।

यह इनऑर्डर ट्रैवर्सल को तेज बनाता है और इसे स्टैक और रिकर्सन के बिना करता है। थ्रेडेड बाइनरी ट्री के दो प्रकार होते हैं।

सिंगल थ्रेडेड प्रत्येक नोड या तो बाएं या दाएं थ्रेडेड होता है यानी इनऑर्डर प्रीडिसेसर या सक्सेसर। यहां, सभी राइट नल पॉइंटर्स इनऑर्डर सक्सेसर की ओर इंगित करेंगे या सभी लेफ्ट नल पॉइंटर्स इनऑर्डर प्रीडिसेसर की ओर इंगित करेंगे।

डबल थ्रेडेड प्रत्येक नोड बाएं और दाएं दोनों तरफ थ्रेडेड होता है यानी इनऑर्डर प्रीडिसेसर और सक्सेसर दोनों। यहां, सभी राइट नल पॉइंटर्स इनऑर्डर सक्सेसर की ओर इंगित करेंगे और सभी लेफ्ट नल पॉइंटर्स इनऑर्डर प्रीडिसेसर की ओर इंगित करेंगे।

यह थ्रेडेड बाइनरी ट्री को कार्यान्वित करने के लिए एक C++ प्रोग्राम है।

फंक्शन्स और स्यूडोकोड

function insert()

यदि ट्री पूरी तरह खाली है तो नोड को रूट के रूप में इन्सर्ट करें। अन्यथा, यदि न्यू नोड < करंट नोड तो
    बाएं थ्रेड पर जाएं और न्यू नोड को बाएं चाइल्ड के रूप में सेट करें।
अन्यथा
    दाएं थ्रेड पर जाएं और न्यू नोड को दाएं चाइल्ड के रूप में सेट करें।

function search()

यदि सर्च की < रूट तो
    बाएं थ्रेड पर जाएं
अन्यथा
    दाएं थ्रेड पर जाएं

function delete()

नोड और उसके पैरेंट को खोजें। नोड डिलीट करने के लिए तीन मामले हैं:

• नोड जिसके दो चाइल्ड्स हैं।
• केवल बायां चाइल्ड है।
• केवल दायां चाइल्ड है।

उदाहरण

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

class Node { // नोड घोषणा
public:
    int key;
    Node *left, *right;
    bool leftThread, rightThread;
};

class ThreadedBinaryTree {
private:
    Node *root;
    
public:
    ThreadedBinaryTree() { // वेरिएबल्स इनिशियलाइज़ करने के लिए कंस्ट्रक्टर
        root = new Node();
        root->right = root->left = root;
        root->leftThread = true;
        root->key = MAX_VALUE;
    }
    
    void makeEmpty() { // ट्री क्लियर करें
        root = new Node();
        root->right = root->left = root;
        root->leftThread = true;
        root->key = MAX_VALUE;
    }
    
    void insert(int key) {
        Node *p = root;
        for(;;) {
            if(p->key < key) { // दाएं थ्रेड पर जाएं
                if(p->rightThread)
                    break;
                p = p->right;
            } else if(p->key > key) { // बाएं थ्रेड पर जाएं
                if(p->leftThread)
                    break;
                p = p->left;
            } else {
                return;
            }
        }
        
        Node *temp = new Node();
        temp->key = key;
        temp->rightThread = temp->leftThread = true;
        
        if(p->key < key) {
            temp->right = p->right;
            temp->left = p;
            p->right = temp;
            p->rightThread = false;
        } else {
            temp->right = p;
            temp->left = p->left;
            p->left = temp;
            p->leftThread = false;
        }
    }
    
    bool search(int key) {
        Node *temp = root->left;
        for(;;) {
            if(temp->key < key) { // दाएं थ्रेड में खोजें
                if(temp->rightThread)
                    return false;
                temp = temp->right;
            } else if(temp->key > key) { // बाएं थ्रेड में खोजें
                if(temp->leftThread)
                    return false;
                temp = temp->left;
            } else {
                return true;
            }
        }
    }
    
    void Delete(int key) {
        Node *dest = root->left, *par = root;
        for(;;) { // नोड और उसके पैरेंट को खोजें
            if(dest->key < key) {
                if(dest->rightThread)
                    return;
                par = dest;
                dest = dest->right;
            } else if(dest->key > key) {
                if(dest->leftThread)
                    return;
                par = dest;
                dest = dest->left;
            } else {
                break;
            }
        }
        
        Node *target = dest;
        if(!dest->rightThread && !dest->leftThread) { // दो चाइल्ड्स हैं
            par = dest;
            target = dest->left; // बाएं चाइल्ड पर सबसे बड़ा नोड
            while(!target->rightThread) {
                par = target;
                target = target->right;
            }
            dest->key = target->key; // मोड बदलें
        }
        
        if(par->key >= target->key) { // केवल बायां चाइल्ड
            if(target->rightThread && target->leftThread) {
                par->left = target->left;
                par->leftThread = true;
            } else if(target->rightThread) {
                Node* largest = target->left;
                while(!largest->rightThread) {
                    largest = largest->right;
                }
                largest->right = par;
                par->left = target->left;
            } else {
                Node* smallest = target->right;
                while(!smallest->leftThread) {
                    smallest = smallest->left;
                }
                smallest->left = target->left;
                par->left = target->right;
            }
        } else { // केवल दायां चाइल्ड
            if(target->rightThread && target->leftThread) {
                par->right = target->right;
                par->rightThread = true;
            } else if(target->rightThread) {
                Node* largest = target->left;
                while(!largest->rightThread) {
                    largest = largest->right;
                }
                largest->right = target->right;
                par->right = target->left;
            } else {
                Node* smallest = target->right;
                while(!smallest->leftThread) {
                    smallest = smallest->left;
                }
                smallest->left = par;
                par->right = target->right;
            }
        }
    }
    
    void displayTree() { // ट्री प्रिंट करें
        Node *temp = root, *par;
        for(;;) {
            par = temp;
            temp = temp->right;
            if(!par->rightThread) {
                while(!temp->leftThread) {
                    temp = temp->left;
                }
            }
            if(temp == root)
                break;
            cout << temp->key << " ";
        }
        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
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

थ्रेडेड बाइनरी ट्री नल पॉइंटर्स का उपयोग करके इनऑर्डर प्रीडिसेसर/सक्सेसर को संकेत करता है, जिससे O(1) स्पेस में इनऑर्डर ट्रैवर्सल संभव होता है (रिकर्सन/स्टैक के बिना)। यह मेमोरी-बाधित वातावरण में उपयोगी है। इन्सर्शन, डिलीशन और सर्च ऑपरेशन्स थ्रेड पॉइंटर्स को उचित तरीके से बनाए रखते हैं।