树堆（Treap）图文详解与实现
1.Treap的定义
树堆（Treap）是二叉排序树（Binary Sort Tree）与堆（Heap）结合产生的一种拥有堆性质的二叉排序树。
但是这里要注意两点，第一点是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是；第二点是Treap并不严格满足平衡二叉排序树（AVL树）的要求，即树堆中每个节点的左右子树高度之差的绝对值可能会超过1，只是近似满足平衡二叉排序树的性质。
Treap每个节点记录两个数据，一个是键值，一个是随机附加的优先级，Treap在以关键码构成二叉排序树的同时，又以结点优先级形成最大堆和最小堆。所以Treap必须满足这两个性质，一是二叉排序树的性质，二是堆的性质。如下图，即为一个树堆。
2.Treap的特点
Treap因在BST中加入了堆的性质，在以随机顺序将节点插入二叉排序 树时，根据随机附加的优先级以旋转的方式维持堆的性质，其特点是能基本实现随机平衡的结构。相对于其他的平衡二叉搜索树，优点是实现简单，因为Treap维护堆性质的方法只用到了旋转，只需要两种旋转，易于维护，可用于高效快速查找。
3.Treap的操作
3.1Treap的插入
给节点随机分配一个优先级，先和二叉排序树（又叫二叉搜索树）的插入一样，先把要插入的点插入到一个叶子上，然后再维护堆的性质。
以最小堆为例，如果当前节点的优先级比其根节点小就旋转。如果当前节点是根的左子节点就右旋。如果当前节点是根的右子节点就左旋。 即左旋能使根节点转移到左边，右旋能使根节点转移到右边。
下图中，当X节点优先级小于Y节点时右旋和Y节点优先级小于X节点的左旋，其左右旋转如下图：
插入写成递归形式的话，只需要在递归调用完成后判断是否满足堆性质，如果不满足就旋转，实现相对简单。其插入过程示例图如下：
时间复杂度： 由于旋转是O(1)的，最多进行h次(h是树的高度)，插入的复杂度是O(h)的，在期望情况下h=O(log n)，所以它的期望复杂度是O(log n)。
3.2Treap的删除
（1）找到相应的结点； （2）若该结点为叶子结点，则直接删除； （3）若该结点为只包含一个叶子结点的结点，则将其叶子结点赋值给它； （4）若该结点为其他情况下的节点，则进行相应的旋转，具体的方法就是每次找到优先级最小的儿子，向与其相反的方向旋转，直到该结点为上述情况之一，然后进行删除。
时间复杂度： 最多进行O(h)次旋转，期望复杂度是O(log n)。
3.3Treap的查找
根据Treap具有二叉搜索树的性质，可以快速查找所需节点。 时间复杂度： 期望复杂度是O(log n)。
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;
}运行结果截图：
参考文献
[1]http://blog.csdn.net/yang_yulei/article/details/46005845 [2]http://www.cnblogs.com/shuaiwhu/archive/2012/05/06/2485894.html