C++ प्रोग्राम: Treap डेटा स्ट्रक्चर का कार्यान्वयन

यह C++ प्रोग्राम Treap (Tree + Heap) डेटा स्ट्रक्चर को लागू करता है। Treap एक रैंडमाइज़्ड बाइनरी सर्च ट्री है जो बाइनरी सर्च ट्री के गुणों (बाएं सबट्री में छोटे मान, दाएं में बड़े) और हीप के गुणों (प्राथमिकता आधारित) दोनों को बनाए रखता है। यहां इन्सर्शन, डिलीशन और सर्च ऑपरेशन दिखाए गए हैं।

मुख्य फंक्शन और विवरण

insertNode() - Treap में की इन्सर्ट करना

यदि रूट nullptr है:
    डेटा को रूट के रूप में लौटाएं
यदि दिया गया डेटा रूट नोड से कम है:
    बाएं सबट्री में इन्सर्ट करें
    यदि हीप प्रॉपर्टी का उल्लंघन हुआ तो बाएं रोटेट करें
अन्यथा:
    दाएं सबट्री में इन्सर्ट करें
    यदि हीप प्रॉपर्टी का उल्लंघन हुआ तो दाएं रोटेट करें

searchNode() - Treap में की सर्च करना

यदि की मौजूद नहीं है तो false लौटाएं
यदि की मौजूद है तो true लौटाएं
यदि की रूट से कम है तो बाएं सबट्री में सर्च करें
अन्यथा दाएं सबट्री में सर्च करें

deleteNode() - Treap से की डिलीट करना

यदि की मौजूद नहीं है तो false लौटाएं
यदि की मौजूद है तो true लौटाएं
यदि की रूट से कम है तो बाएं सबट्री में जाएं
अन्यथा दाएं सबट्री में जाएं
यदि की मिल गई:
    यदि नोड लीफ नोड है:
        मेमोरी डिएलोकेट करें और रूट को null अपडेट करें
    यदि नोड के दो बच्चे हैं:
        यदि बाएं बच्चे की प्राथमिकता दाएं से कम है:
            रूट पर rotLeft() कॉल करें
            बाएं बच्चे को रिकर्सिवली डिलीट करें
        अन्यथा:
            रूट पर rotRight() कॉल करें
            दाएं बच्चे को रिकर्सिवली डिलीट करें
    यदि नोड का केवल एक बच्चा है:
        बच्चे नोड को खोजें
        मेमोरी डिएलोकेट करें
परिणाम प्रिंट करें
समाप्ति

उदाहरण कोड

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

struct TreapNode {
    int data;
    int priority;
    TreapNode *left, *right;
    
    TreapNode(int d) {
        this->data = d;
        this->priority = rand() % 100;
        this->left = this->right = nullptr;
    }
};

void rotLeft(TreapNode* &root) {
    TreapNode* R = root->right;
    TreapNode* X = root->right->left;
    R->left = root;
    root->right = X;
    root = R;
}

void rotRight(TreapNode* &root) {
    TreapNode* L = root->left;
    TreapNode* Y = root->left->right;
    L->right = root;
    root->left = Y;
    root = L;
}

void insertNode(TreapNode* &root, int d) {
    if (root == nullptr) {
        root = new TreapNode(d);
        return;
    }
    if (d < root->data) {
        insertNode(root->left, d);
        if (root->left != nullptr && root->left->priority > root->priority)
            rotRight(root);
    } else {
        insertNode(root->right, d);
        if (root->right != nullptr && root->right->priority > root->priority)
            rotLeft(root);
    }
}

bool searchNode(TreapNode* root, int key) {
    if (root == nullptr) return false;
    if (root->data == key) return true;
    if (key < root->data) return searchNode(root->left, key);
    return searchNode(root->right, key);
}

void deleteNode(TreapNode* &root, int key) {
    if (root == nullptr) return;
    if (key < root->data)
        deleteNode(root->left, key);
    else if (key > root->data)
        deleteNode(root->right, key);
    else {
        // लीफ नोड
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            root = nullptr;
        }
        // दो बच्चे
        else if (root->left && root->right) {
            if (root->left->priority < root->right->priority) {
                rotLeft(root);
                deleteNode(root->left, key);
            } else {
                rotRight(root);
                deleteNode(root->right, key);
            }
        }
        // एक बच्चा
        else {
            TreapNode* child = (root->left) ? root->left : root->right;
            TreapNode* curr = root;
            root = child;
            delete curr;
        }
    }
}

void displayTreap(TreapNode *root, int space = 0, int height = 10) {
    if (root == nullptr) return;
    space += height;
    displayTreap(root->left, space);
    cout << endl;
    for (int i = height; i < space; i++) cout << ' ';
    cout << root->data << "(" << root->priority << ")\n";
    displayTreap(root->right, space);
}

int main() {
    int nums[] = {1, 7, 6, 4, 3, 2, 8, 9, 10};
    int n = sizeof(nums) / sizeof(int);
    TreapNode* root = nullptr;
    srand(time(nullptr));
    
    for (int num : nums) insertNode(root, num);
    
    cout << "Constructed Treap:\n\n";
    displayTreap(root);
    
    cout << "\nDeleting node 8:\n\n";
    deleteNode(root, 8);
    displayTreap(root);
    
    cout << "\nDeleting node 3:\n\n";
    deleteNode(root, 3);
    displayTreap(root);
    
    return 0;
}

आउटपुट

Constructed Treap:
1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 8(20) 9(41) 10(25)

Deleting node 8:
1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 9(41) 10(25)

Deleting node 3:
1(12) 2(27) 4(46) 6(75) 7(88) 9(41) 10(25)

नोट: Treap में प्रत्येक नोड को एक रैंडम प्राथमिकता दी जाती है, जिससे ट्री बैलेंस्ड रहता है और ऑपरेशन्स की औसत समय जटिलता O(log n) होती है।