Chương trình C ++ để triển khai Treap

Đây là một chương trình C ++ để triển khai Treap. Cấu trúc dữ liệu Treap về cơ bản là một cây tìm kiếm nhị phân ngẫu nhiên. Ở đây, chúng tôi sẽ xem xét các thao tác chèn, xóa và tìm kiếm trên này.

Chức năng và mô tả

hàm insetNod () để chèn một khóa nhất định vào treap với mức độ ưu tiên một cách đệ quy -

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.

function searchNod () để tìm kiếm khóa trong treap một cách đệ quy -

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.

function deleteNod () để xóa khóa khỏi treap một cách đệ quy -

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

Ví dụ

#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;
}

Đầu ra

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)