C++ 程序实现 Treap
c++server side programmingprogramming更新于 2024/10/25 0:54:00
这是一个 C++ 程序实现 Treap。Treap 数据结构基本上是一个随机二叉搜索树。这里，我们来考虑插入、删除和搜索操作。
函数和说明
| 函数 rotLeft() 用于左旋转 | 首先旋转树，然后设置新根。 |
| 函数 rotRight() 用于右旋转 | 首先旋转树，然后设置新根。 |
函数 insetNod() 以优先级递归方式将给定键插入 treap −
如果 root = nullptr 返回数据作为根。 如果给定数据小于根节点， 在左子树中插入数据。 如果违反了堆属性，则向左旋转。 else 在右子树中插入数据。 如果违反了堆属性，则向右旋转。
function searchNod() 用于递归搜索 treap 中的键 −
如果键不存在，则返回 false。 如果键存在，则返回 true。 如果键小于根，则在左子树中搜索。 Else 在右子树中搜索。
function deleteNod() 用于递归删除 treap 中的键 −
如果键不存在，则返回 false 如果键存在，则返回 true。 如果 key 小于 root，则转到左子树。 否则 转到右子树。 如果找到 key: 要删除的节点是叶节点 释放内存并将 root 更新为 null。 删除 root。 要删除的节点有两个子节点 如果左子节点的优先级低于右子节点 在 root 上调用 rotLeft() 递归删除左子节点 else 在根节点上调用 rotRight() 递归删除右子节点 要删除的节点只有一个子节点 查找子节点 释放内存 打印结果。 结束
示例
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct TreapNod { //节点声明
int data;
int priority;
TreapNod* l, *r;
TreapNod(int d) { //构造函数
this->data = d;
this->priority = rand() % 100;
this->l= this->r = nullptr;
}
};
void rotLeft(TreapNod* &root) { //左旋转
TreapNod* R = root->r;
TreapNod* X = root->r->l;
R->l = root;
root->r= X;
root = R;
}
void rotRight(TreapNod* &root) { //右旋转
TreapNod* L = root->l;
TreapNod* Y = root->l->r;
L->r = root;
root->l= Y;
root = L;
}
void insertNod(TreapNod* &root, int d) { //插入
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)
