树堆（Treap）图文详解与实现

大家好，欢迎来到IT知识分享网。

1.定义

树堆（Treap）是二叉搜索树（Binary Search Tree）与堆（Heap）结合产生的一种拥有堆性质的二叉搜索树。

但是这里要注意两点：

• Treap 和二叉堆有一点不同，二叉堆一定是完全二叉树，而 Treap 不一定是。
• Treap 并不严格满足平衡二叉搜索树（AVL 树）的要求，即 Treap 中每个结点的左右子树高度差的绝对值可能会超过 1，只是近似满足平衡二叉搜索树的性质。

Treap 每个结点记录两个数据，一个是键值，一个是随机附加的优先级。Treap 在以关键码构成二叉搜索树的同时，又以结点优先级形成大顶堆和小顶堆。

所以 Treap 必须满足两个性质：

• 满足二叉排序树的性质。
• 满足堆的性质。

2.特点

根据附加的随机优先级以旋转的方式维持堆的性质，在二叉搜索树中加入了堆的性质。这么做得好处是，不管以何种顺序插入结点构建二叉树，都能够让二叉搜索树的高度保持稳定，即用来平衡二叉搜索树。

相对于其他的平衡二叉搜索树，Treap 优点是实现简单，因为维护堆性质只用到了旋转，只需要两种旋转，易于维护。

3.操作

3.1 插入

给节点随机分配一个优先级，先和二叉排序树（又叫二叉搜索树）的插入一样，先把要插入的点插入到一个叶子上，然后再维护堆的性质。

以最小堆为例，如果当前节点的优先级比其根节点小就旋转。如果当前节点是根的左子节点就右旋。如果当前节点是根的右子节点就左旋。 即左旋能使根节点转移到左边，右旋能使根节点转移到右边。

下图中，当X节点优先级小于Y节点时右旋和Y节点优先级小于X节点的左旋，其左右旋转如下图：

插入写成递归形式的话，只需要在递归调用完成后判断是否满足堆性质，如果不满足就旋转，实现相对简单。其插入过程示例图如下：

3.2 删除

3.3 查找

4 数据结构的设计

结点采用结构体存储，定义如下：

struct node { 
    int key;//关键字  int priority;//随机优先级 node* left;//左节点 node* right;//右节点 }; 

5.实现示例

#include <stdio.h> #include <stdlib.h> #include <time.h> typedef struct node Node; typedef struct treap_t Treap; typedef Node* nodePoint; struct node { 
    int key;//关键字  int priority;//随机优先级 Node* left;//左节点 Node* right;//右节点 }; Node* root;//Treap的根结点 //左旋转 void rotate_left(Node* &node) { 
    Node* x = node->right; node->right = x->left; x->left =node; node = x; } //右旋转 void rotate_right(Node* &node) { 
    Node* x = node->left; node->left = x->right; x->right = node; node = x; } //插入操作 void treap_insert(Node* &root, int key, int priority) { 
    //根为NULL，则直接创建此结点为根结点 if (root == NULL) { 
    root = (Node*)new Node; root->left = NULL; root->right = NULL; root->priority = priority; root->key = key; } //向左插入结点 else if (key <root->key) { 
    treap_insert(root->left, key, priority); if (root->left->priority < root->priority) rotate_right(root); } //向左插入结点 else { 
    treap_insert(root->right, key, priority); if (root->right->priority < root->priority) rotate_left(root); } } //删除结点操作 void treap_delete(Node* &root, int key) { 
    if (root != NULL) { 
    if (key < root->key) treap_delete(root->left, key); else if (key > root->key) treap_delete(root->right, key); else { 
    //左孩子为空 if (root->left == NULL) root = root->right; //右孩子为空 else if (root->right == NULL) root = root->left; //左右孩子均不为空 else { 
    //先旋转，然后再删除 if (root->left->priority < root->right->priority) { 
    rotate_right(root); treap_delete(root->right, key); } else { 
    rotate_left(root); treap_delete(root->left,key); } } } } } //中序遍历 void in_order_traverse(Node* root) { 
    if (root!= NULL) { 
    in_order_traverse(root->left); printf("%d\t", root->key); in_order_traverse(root->right); } } //计算树的高度 int depth(Node* node) { 
    if(node == NULL) return -1; int l = depth(node->left); int r = depth(node->right); return (l < r)?(r+1):(l+1); } int main() { 
    srand(time(0)); //产生最大伪随机数0至RAND_MAX(32767) //printf("%d\n",RAND_MAX); //随机插入10个节点 printf("----------------------创建Treap树堆-----------------------\n"); printf("顺序插入0至9十个数，键值与优先级如下\n"); for (int i = 0; i < 10; i++) { 
    int pri=rand(); printf("key:%d priority:%d\n",i,pri); treap_insert(root,i,pri); } //中序遍历Treap printf("\n插入完毕，中序遍历Treap所得结果为:\n"); in_order_traverse(root); printf("\nTreap高度：%d\n", depth(root)); printf("----------------------删除结点-----------------------\n"); printf("请输入要删除的结点键值\n"); int rmKey; scanf("%d",&rmKey); treap_delete(root, rmKey); printf("\n删除完毕，中序遍历Treap所得结果为:\n"); in_order_traverse(root); printf("\nTreap高度：%d\n", depth(root)); getchar(); getchar(); return 0; } 

运行结果截图：

参考文献