我们强烈建议将第1组作为这篇文章的先决条件。 Treap（随机二叉搜索树） 本文讨论了搜索、插入和删除的实现。 搜索： 等同于 标准BST搜索 。搜索时不考虑优先级。
null
CPP
// C function to search a given key in a given BST TreapNode* search(TreapNode* root, int key) { // Base Cases: root is null or key is present at root if (root == NULL || root->key == key) return root; // Key is greater than root's key if (root->key < key) return search(root->right, key); // Key is smaller than root's key return search(root->left, key); } |
插入 1） 创建键等于x且值等于随机值的新节点。 2） 执行标准 BST插件 . 3） 新插入的节点具有随机优先级，因此可能会违反Max Heap属性。。使用旋转来确保插入节点的优先级遵循max heap属性。 在插入过程中，我们递归地遍历插入节点的所有祖先。 a） 如果在左子树中插入了新节点，并且左子树的根具有更高的优先级，则执行右旋转。 b） 如果在右子树中插入了新节点，并且右子树的根具有更高的优先级，则执行左旋转。
CPP
/* Recursive implementation of insertion in Treap */ TreapNode* insert(TreapNode* root, int key) { // If root is NULL, create a new node and return it if (!root) return newNode(key); // If key is smaller than root if (key <= root->key) { // Insert in left subtree root->left = insert(root->left, key); // Fix Heap property if it is violated if (root->left->priority > root->priority) root = rightRotate(root); } else // If key is greater { // Insert in right subtree root->right = insert(root->right, key); // Fix Heap property if it is violated if (root->right->priority > root->priority) root = leftRotate(root); } return root; } |
删除： 这里的delete实现与中讨论的步骤略有不同 以前的职位 . 1） 如果节点是叶，请将其删除。 2） 如果节点有一个子节点为NULL，另一个子节点为非NULL，则用非空子节点替换节点。 3） 如果节点的两个子节点都为非NULL，则查找左、右子节点的最大值。 ….a） 如果右子节点的优先级更高，则在节点处执行左旋转 ….b） 如果左子节点的优先级更高，则在节点处执行右旋转。 第3步的想法是将节点向下移动，这样我们就可以得到案例1或案例2。
CPP
/* Recursive implementation of Delete() */ TreapNode* deleteNode(TreapNode* root, int key) { // Base case if (root == NULL) return root; // IF KEYS IS NOT AT ROOT if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); // IF KEY IS AT ROOT // If left is NULL else if (root->left == NULL) { TreapNode *temp = root->right; delete (root); root = temp; // Make right child as root } // If Right is NULL else if (root->right == NULL) { TreapNode *temp = root->left; delete (root); root = temp; // Make left child as root } // If key is at root and both left and right are not NULL else if (root->left->priority < root->right->priority) { root = leftRotate(root); root->left = deleteNode(root->left, key); } else { root = rightRotate(root); root->right = deleteNode(root->right, key); } return root; } |
演示所有操作的完整程序
CPP
// C++ program to demonstrate search, insert and delete in Treap #include <bits/stdc++.h> using namespace std; // A Treap Node struct TreapNode { int key, priority; TreapNode *left, *right; }; /* T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x (on right side) y x / Right Rotation / x T3 – – – – – – – > T1 y / < - - - - - - - / T1 T2 Left Rotation T2 T3 */ // A utility function to right rotate subtree rooted with y // See the diagram given above. TreapNode *rightRotate(TreapNode *y) { TreapNode *x = y->left, *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Return new root return x; } // A utility function to left rotate subtree rooted with x // See the diagram given above. TreapNode *leftRotate(TreapNode *x) { TreapNode *y = x->right, *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Return new root return y; } /* Utility function to add a new key */ TreapNode* newNode( int key) { TreapNode* temp = new TreapNode; temp->key = key; temp->priority = rand ()%100; temp->left = temp->right = NULL; return temp; } // C function to search a given key in a given BST TreapNode* search(TreapNode* root, int key) { // Base Cases: root is null or key is present at root if (root == NULL || root->key == key) return root; // Key is greater than root's key if (root->key < key) return search(root->right, key); // Key is smaller than root's key return search(root->left, key); } /* Recursive implementation of insertion in Treap */ TreapNode* insert(TreapNode* root, int key) { // If root is NULL, create a new node and return it if (!root) return newNode(key); // If key is smaller than root if (key <= root->key) { // Insert in left subtree root->left = insert(root->left, key); // Fix Heap property if it is violated if (root->left->priority > root->priority) root = rightRotate(root); } else // If key is greater { // Insert in right subtree root->right = insert(root->right, key); // Fix Heap property if it is violated if (root->right->priority > root->priority) root = leftRotate(root); } return root; } /* Recursive implementation of Delete() */ TreapNode* deleteNode(TreapNode* root, int key) { if (root == NULL) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); // IF KEY IS AT ROOT // If left is NULL else if (root->left == NULL) { TreapNode *temp = root->right; delete (root); root = temp; // Make right child as root } // If Right is NULL else if (root->right == NULL) { TreapNode *temp = root->left; delete (root); root = temp; // Make left child as root } // If key is at root and both left and right are not NULL else if (root->left->priority < root->right->priority) { root = leftRotate(root); root->left = deleteNode(root->left, key); } else { root = rightRotate(root); root->right = deleteNode(root->right, key); } return root; } // A utility function to print tree void inorder(TreapNode* root) { if (root) { inorder(root->left); cout << "key: " << root->key << " | priority: %d " << root->priority; if (root->left) cout << " | left child: " << root->left->key; if (root->right) cout << " | right child: " << root->right->key; cout << endl; inorder(root->right); } } // Driver Program to test above functions int main() { srand ( time (NULL)); struct TreapNode *root = NULL; root = insert(root, 50); root = insert(root, 30); root = insert(root, 20); root = insert(root, 40); root = insert(root, 70); root = insert(root, 60); root = insert(root, 80); cout << "Inorder traversal of the given tree " ; inorder(root); cout << "Delete 20" ; root = deleteNode(root, 20); cout << "Inorder traversal of the modified tree " ; inorder(root); cout << "Delete 30" ; root = deleteNode(root, 30); cout << "Inorder traversal of the modified tree " ; inorder(root); cout << "Delete 50" ; root = deleteNode(root, 50); cout << "Inorder traversal of the modified tree " ; inorder(root); TreapNode *res = search(root, 50); (res == NULL)? cout << "50 Not Found " : cout << "50 found" ; return 0; } |
输出：
Inorder traversal of the given tree key: 20 | priority: %d 92 | right child: 50key: 30 | priority: %d 48 | right child: 40key: 40 | priority: %d 21key: 50 | priority: %d 73 | left child: 30 | right child: 60key: 60 | priority: %d 55 | right child: 70key: 70 | priority: %d 50 | right child: 80key: 80 | priority: %d 44Delete 20Inorder traversal of the modified tree key: 30 | priority: %d 48 | right child: 40key: 40 | priority: %d 21key: 50 | priority: %d 73 | left child: 30 | right child: 60key: 60 | priority: %d 55 | right child: 70key: 70 | priority: %d 50 | right child: 80key: 80 | priority: %d 44Delete 30Inorder traversal of the modified tree key: 40 | priority: %d 21key: 50 | priority: %d 73 | left child: 40 | right child: 60key: 60 | priority: %d 55 | right child: 70key: 70 | priority: %d 50 | right child: 80key: 80 | priority: %d 44Delete 50Inorder traversal of the modified tree key: 40 | priority: %d 21key: 60 | priority: %d 55 | left child: 40 | right child: 70key: 70 | priority: %d 50 | right child: 80key: 80 | priority: %d 4450 Not Found
对上述输出的解释：
Every node is written as key(priority)The above code constructs below tree 20(92) 50(73) / 30(48) 60(55) 40(21) 70(50) 80(44) After deleteNode(20) 50(73) / 30(48) 60(55) 40(21) 70(50) 80(44) After deleteNode(30) 50(73) / 40(21) 60(55) 70(50) 80(44) After deleteNode(50) 60(55) / 40(21) 70(50) 80(44)
幸亏 贾伊·戈亚尔 用于提供初始实施。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
