Treap을 구현하는 C++ 프로그램

Treap을 구현하기 위한 C++ 프로그램입니다. Treap 데이터 구조는 기본적으로 무작위 이진 검색 트리입니다. 여기에서는 이에 대한 삽입, 삭제 및 검색 작업을 고려할 것입니다.

기능 및 설명

함수 insetNod() 재귀적으로 우선 순위가 있는 treap에 주어진 키를 삽입하려면 -

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() treap에서 키를 재귀적으로 검색하기 위해 -

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() 재귀적으로 treap에서 키를 삭제하려면 -

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)