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)