C++ প্রোগ্রাম: স্প্লে ট্রি (Splay Tree) বাস্তবায়ন

এটি একটি C++ প্রোগ্রাম যা স্প্লে ট্রি (Splay Tree) বাস্তবায়ন করে।

ক্লাস বিবরণ

Begin
    class SplayTree:
        Splay() ফাংশন দিয়ে টপ-ডাউন স্প্লে ট্রি বাস্তবায়ন।
        head.rch বাম ট্রি, head.lch ডান ট্রি নির্দেশ করে।
        রাইট ট্রির সাথে লিঙ্ক তৈরি।
        লেফট ট্রির সাথে লিঙ্ক তৈরি।
        লেফট, মিডল, রাইট ট্রি অ্যাসেম্বল করুন।
        Insert() ফাংশন দিয়ে নোড ইনসার্ট।
        যদি root->k >= key: সব কী রুটের লেফটে।
        Else if root->k <= key: সব কী রুটের রাইটে।
        Else: রুট রিটার্ন।
End

ক্লাস বিবরণ এবং সিউডোকোড

Begin
    স্ট্রাকচার s ডিক্লেয়ার: k, lch, rch।
    class SplayTree:
        RR_Rotate() - ডান ঘুরানো।
        LL_Rotate() - বাম ঘুরানো।
        Splay() - টপ-ডাউন স্প্লে ট্রি বাস্তবায়ন।
        New_Node() - নোড তৈরি।
        Insert() - নোড ইনসার্ট।
        Delete() - নোড ডিলিট।
        Search() - নোড সার্চ।
        InOrder() - ইনঅর্ডার ট্রাভার্সাল।
        main() - মেনু-চালিত প্রোগ্রাম।
End

উদাহরণ কোড

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

struct s {
    int k;
    s* lch;
    s* rch;
};

class SplayTree {
public:
    s* RR_Rotate(s* k2) {
        s* k1 = k2->lch;
        k2->lch = k1->rch;
        k1->rch = k2;
        return k1;
    }
    s* LL_Rotate(s* k2) {
        s* k1 = k2->rch;
        k2->rch = k1->lch;
        k1->lch = k2;
        return k1;
    }
    s* Splay(int key, s* root) {
        if (!root) return NULL;
        s header;
        header.lch = header.rch = NULL;
        s* LeftTreeMax = &header;
        s* RightTreeMin = &header;
        while (1) {
            if (key < root->k) {
                if (!root->lch) break;
                if (key < root->lch->k) {
                    root = RR_Rotate(root);
                    if (!root->lch) break;
                }
                RightTreeMin->lch = root;
                RightTreeMin = RightTreeMin->lch;
                root = root->lch;
                RightTreeMin->lch = NULL;
            } else if (key > root->k) {
                if (!root->rch) break;
                if (key > root->rch->k) {
                    root = LL_Rotate(root);
                    if (!root->rch) break;
                }
                LeftTreeMax->rch = root;
                LeftTreeMax = LeftTreeMax->rch;
                root = root->rch;
                LeftTreeMax->rch = NULL;
            } else break;
        }
        LeftTreeMax->rch = root->lch;
        RightTreeMin->lch = root->rch;
        root->lch = header.rch;
        root->rch = header.lch;
        return root;
    }
    s* New_Node(int key) {
        s* p_node = new s;
        if (!p_node) { fprintf(stderr, "Out of memory!\n"); exit(1); }
        p_node->k = key;
        p_node->lch = p_node->rch = NULL;
        return p_node;
    }
    s* Insert(int key, s* root) {
        static s* p_node = NULL;
        if (!p_node) p_node = New_Node(key);
        else p_node->k = key;
        if (!root) { root = p_node; p_node = NULL; return root; }
        root = Splay(key, root);
        if (key < root->k) {
            p_node->lch = root->lch;
            p_node->rch = root;
            root->lch = NULL;
            root = p_node;
        } else if (key > root->k) {
            p_node->rch = root->rch;
            p_node->lch = root;
            root->rch = NULL;
            root = p_node;
        } else return root;
        p_node = NULL;
        return root;
    }
    s* Delete(int key, s* root) {
        s* temp;
        if (!root) return NULL;
        root = Splay(key, root);
        if (key != root->k) return root;
        else {
            if (!root->lch) { temp = root; root = root->rch; }
            else { temp = root; root = Splay(key, root->lch); root->rch = temp->rch; }
            free(temp);
            return root;
        }
    }
    s* Search(int key, s* root) { return Splay(key, root); }
    void InOrder(s* root) {
        if (root) {
            InOrder(root->lch);
            cout << "key: " << root->k;
            if(root->lch) cout << " | left child: " << root->lch->k;
            if(root->rch) cout << " | right child: " << root->rch->k;
            cout << "\n";
            InOrder(root->rch);
        }
    }
};

int main() {
    SplayTree st;
    s *root = NULL;
    st.InOrder(root);
    int i, c;
    while(1) {
        cout << "1. Insert\n2. Delete\n3. Search\n4. Exit\nEnter your choice: ";
        cin >> c;
        switch(c) {
            case 1:
                cout << "Enter value to be inserted: "; cin >> i;
                root = st.Insert(i, root);
                cout << "\nAfter Insert: " << i << endl;
                st.InOrder(root);
                break;
            case 2:
                cout << "Enter value to be deleted: "; cin >> i;
                root = st.Delete(i, root);
                cout << "\nAfter Delete: " << i << endl;
                st.InOrder(root);
                break;
            case 3:
                cout << "Enter value to be searched: "; cin >> i;
                root = st.Search(i, root);
                cout << "\nAfter Search " << i << endl;
                st.InOrder(root);
                break;
            case 4: exit(1);
            default: cout << "\nInvalid type! \n";
        }
    }
    return 0;
}

আউটপুট (নমুনা)

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 7
After Insert: 7
key: 7
... (বاقি আউটপুট সংক্ষিপ্ত)