ট্রিপ বাস্তবায়নের জন্য C++ প্রোগ্রাম

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

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

ফাংশন insetNod() একটি প্রদত্ত কী ঢোকাতে অগ্রাধিকারের সাথে বারবার −

If root = nullptr
   return data as root.
If given data is less then root node,
   Insert data in left subtree.
   Rotate left if heap property violated.
else
   Insert data in right subtree.
   Rotate right if heap property violated.

ফাংশন searchNod() পুনরাবৃত্তভাবে ট্রেপে কী অনুসন্ধান করার জন্য −

If key is not present return false.
If key is present return true.
If key is less than root, search in left subtree.
Else
   search in right subtree.

ফাংশন deleteNod() ট্রিপ থেকে পুনরাবৃত্তভাবে কী মুছে ফেলার জন্য −

If key is not present return false
If key is present return true.
If key is less than root, go to left subtree.
Else
   Go to right subtree.
If key is found:
   node to be deleted which is a leaf node
      deallocate the memory and update root to null.
      delete root.
   node to be deleted which has two children
      if left child has less priority than right child
         call rotLeft() on root
         recursively delete the left child
      else
         call rotRight() on root
         recursively delete the right child
   node to be deleted has only one child
         find child node
      deallocate the memory
   Print the result.
End

উদাহরণ

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct TreapNod  { //node declaration
   int data;
   int priority;
   TreapNod* l, *r;
   TreapNod(int d) { //constructor
      this->data = d;
      this->priority = rand() % 100;
      this->l= this->r = nullptr;
   }
};
void rotLeft(TreapNod* &root) { //left rotation
   TreapNod* R = root->r;
   TreapNod* X = root->r->l;
   R->l = root;
   root->r= X;
   root = R;
}
void rotRight(TreapNod* &root) { //right rotation
   TreapNod* L = root->l;
   TreapNod* Y = root->l->r;
   L->r = root;
   root->l= Y;
   root = L;
}
void insertNod(TreapNod* &root, int d) { //insertion
   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) {
   //node to be deleted which is a leaf node
   if (root == nullptr)
      return;
   if (key < root->data)
      deleteNod(root->l, key);
   else if (key > root->data)
      deleteNod(root->r, key);
      //node to be deleted which has two children
   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);
         }
      }
      //node to be deleted has only one child
      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) { //display treap
   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)