实施Treap的C ++程序
这是用于实现Treap的C++程序。Treap数据结构基本上是随机的二叉搜索树。在这里，我们将考虑对此进行插入，删除和搜索操作。
功能和说明
rotLeft()左旋转功能rotRight()右旋转功能函数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()递归搜索键的功能-
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:
要删除的节点是叶节点
deallocate the memory and update root to null.
delete root.
有两个子节点的要删除的节点
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
要删除的节点只有一个孩子
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) {
//要删除的节点是叶节点
if (root == nullptr)
return;
if (key < root->data)
deleteNod(root->l, key);
else if (key > root->data)
deleteNod(root->r, key);
//有两个子节点的要删除的节点
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);
}
}
//要删除的节点只有一个孩子
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)