数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学实现 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() 用于递归地搜索 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)
更新于：2019 年 7 月 30 日
超过 1 千次浏览
广告