資料結構
網路
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 千次瀏覽
廣告