C++ প্রোগ্রাম: ট্রিপ (Treap) ডেটা স্ট্রাকচার বাস্তবায়ন

এটি একটি C++ প্রোগ্রাম যা ট্রিপ (Treap) ডেটা স্ট্রাকচার বাস্তবায়ন করে। ট্রিপ মূলত একটি র‍্যান্ডোমাইজড বাইনারি সার্চ ট্রি। এখানে আমরা ইন্সার্ট, ডিলিট এবং সার্চ অপারেশন বিবেচনা করব।

ফাংশন এবং বিবরণ

insertNod() ফাংশন একটি কী ট্রিপে প্রায়োরিটির সাথে রিকার্সিভভাবে ইন্সার্ট করার জন্য:

যদি রুট = nullptr
    ডেটাকে রুট হিসেবে রিটার্ন করুন।
যদি দেওয়া ডেটা রুট নোডের চেয়ে ছোট হয়,
    বাম সাবট্রিতে ডেটা ইন্সার্ট করুন।
    হিপ প্রপার্টি লঙ্ঘন হলে বাম ঘুরান।
অন্যথায়
    ডান সাবট্রিতে ডেটা ইন্সার্ট করুন।
    হিপ প্রপার্টি লঙ্ঘন হলে ডান ঘুরান।

searchNod() ফাংশন ট্রিপে কী সার্চ করার জন্য রিকার্সিভভাবে:

যদি কী উপস্থিত না থাকে false রিটার্ন করুন।
যদি কী উপস্থিত থাকে true রিটার্ন করুন।
যদি কী রুটের চেয়ে ছোট হয়, বাম সাবট্রিতে সার্চ করুন।
অন্যথায় ডান সাবট্রিতে সার্চ করুন।

deleteNod() ফাংশন ট্রিপ থেকে কী ডিলিট করার জন্য রিকার্সিভভাবে:

যদি কী উপস্থিত না থাকে false রিটার্ন করুন।
যদি কী উপস্থিত থাকে true রিটার্ন করুন।
যদি কী রুটের চেয়ে ছোট হয়, বাম সাবট্রিতে যান।
অন্যথায় ডান সাবট্রিতে যান।
যদি কী পাওয়া যায়:
    ডিলিট করার নোড যা একটি লিফ নোড
        মেমরি ডি-অ্যালোকেট করুন এবং রুটকে null-এ আপডেট করুন।
        রুট ডিলিট করুন।
    ডিলিট করার নোড যাতে দুটি চাইল্ড থাকে
        যদি বাম চাইল্ডের প্রায়োরিটি ডান চাইল্ডের চেয়ে কম হয়
            রুটে rotLeft() কল করুন
            বাম চাইল্ডকে রিকার্সিভভাবে ডিলিট করুন
        অন্যথায়
            রুটে rotRight() কল করুন
            ডান চাইল্ডকে রিকার্সিভভাবে ডিলিট করুন
    ডিলিট করার নোড যাতে শুধু একটি চাইল্ড থাকে
        চাইল্ড নোড খুঁজুন
        মেমরি ডি-অ্যালোকেট করুন
ফলাফল প্রিন্ট করুন।
শেষ

উদাহরণ

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

struct TreapNod {
    int data;
    int priority;
    TreapNod* l, *r;
    TreapNod(int d) {
        this->data = d;
        this->priority = rand() % 100;
        this->l = this->r = nullptr;
    }
};

void rotLeft(TreapNod* &root) {
    TreapNod* R = root->r;
    TreapNod* X = root->r->l;
    R->l = root;
    root->r = X;
    root = R;
}

void rotRight(TreapNod* &root) {
    TreapNod* L = root->l;
    TreapNod* Y = root->l->r;
    L->r = root;
    root->l = Y;
    root = L;
}

void insertNod(TreapNod* &root, int d) {
    if (root == nullptr) {
        root = new TreapNod(d);
        return;
    }
    if (d < root->data) {
        insertNod(root->l, d);
        if (root->l != nullptr && root->l->priority > root->priority)
            rotRight(root);
    } else {
        insertNod(root->r, d);
        if (root->r != nullptr && root->r->priority > root->priority)
            rotLeft(root);
    }
}

bool searchNod(TreapNod* root, int key) {
    if (root == nullptr)
        return false;
    if (root->data == key)
        return true;
    if (key < root->data)
        return searchNod(root->l, key);
    return searchNod(root->r, key);
}

void deleteNod(TreapNod* &root, int key) {
    if (root == nullptr)
        return;
    if (key < root->data)
        deleteNod(root->l, key);
    else if (key > root->data)
        deleteNod(root->r, key);
    else {
        if (root->l == nullptr && root->r == nullptr) {
            delete root;
            root = nullptr;
        }
        else if (root->l && root->r) {
            if (root->l->priority < root->r->priority) {
                rotLeft(root);
                deleteNod(root->l, key);
            } else {
                rotRight(root);
                deleteNod(root->r, key);
            }
        }
        else {
            TreapNod* child = (root->l) ? root->l : root->r;
            TreapNod* curr = root;
            root = child;
            delete curr;
        }
    }
}

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

int main() {
    int nums[] = {1,7,6,4,3,2,8,9,10};
    int a = sizeof(nums)/sizeof(int);
    TreapNod* root = nullptr;
    srand(time(nullptr));
    for (int n: nums)
        insertNod(root, n);
    cout << "Constructed Treap:\n\n";
    displayTreap(root);
    cout << "\nDeleting node 8:\n\n";
    deleteNod(root, 8);
    displayTreap(root);
    cout << "\nDeleting node 3:\n\n";
    deleteNod(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)