数据结构之Treap详解

1.概述

同splaytree一样，treap也是一个平衡二叉树，不过Treap会记录一个额外的数据，即优先级。Treap在以关键码构成二叉搜索树的同时，还按优先级来满足堆的性质。因而，Treap=tree+heap。这里需要注意的是，Treap并不是二叉堆，二叉堆必须是完全二叉树，而Treap可以并不一定是。

2.Treap基本操作

为了使Treap中的节点同时满足BST性质和最小堆性质，不可避免地要对其结构进行调整，调整方式被称为旋转。在维护Treap的过程中，只有两种旋转，分别是左旋转(简称左旋)和右旋转(简称右旋)。
左旋一个子树，会把它的根节点旋转到根的左子树位置，同时根节点的右子节点成为子树的根；右旋一个子树，会把它的根节点旋转到根的右子树位置，同时根节点的左子节点成为子树的根。

structTreap_Node

{

Treap_Node*left,*right;//节点的左右子树的指针

intvalue,fix;//节点的值和优先级

};

voidTreap_Left_Rotate(Treap_Node*&a)//左旋节点指针一定要传递引用

{

Treap_Node*b=a->right;

a->right=b->left;

b->left=a;

a=b;

}

voidTreap_Right_Rotate(Treap_Node*&a)//右旋节点指针一定要传递引用

{

Treap_Node*b=a->left;

a->left=b->right;

b->right=a;

a=b;

}

3.Treap的操作

同其他树形结构一样，treap的基本操作有：查找，插入，删除等。

3.1   查找

同其他二叉树一样，treap的查找过程就是二分查找的过程，复杂度为O(lgn)。

3.2   插入

在Treap中插入元素，与在BST中插入方法相似。首先找到合适的插入位置，然后建立新的节点，存储元素。但是要注意新的节点会有一个优先级属性，该值可能会破坏堆序，因此我们要根据需要进行恰当的旋转。具体方法如下：

1.从根节点开始插入；
2.如果要插入的值小于等于当前节点的值，在当前节点的左子树中插入，插入后如果左子节点的优先级小于当前节点的优先级，对当前节点进行右旋；
3.如果要插入的值大于当前节点的值，在当前节点的右子树中插入，插入后如果右子节点的优先级小于当前节点的优先级，对当前节点进行左旋；
4.如果当前节点为空节点，在此建立新的节点，该节点的值为要插入的值，左右子树为空，插入成功。

Treap_Node*root;

voidTreap_Insert(Treap_Node*&P,intvalue)//节点指针一定要传递引用

{

if(!P)//找到位置，建立节点

{

P=newTreap_Node;

P->value=value;

P->fix=rand();//生成随机的修正值

}

elseif(value<=P->value)

{

Treap_Insert(P->left,r);

if(P->left->fix<P->fix)

Treap_Right_Rotate(P);//左子节点修正值小于当前节点修正值，右旋当前节点

}

else

{

Treap_Insert(P->right,r);

if(P->right->fix<P->fix)

Treap_Left_Rotate(P);//右子节点修正值小于当前节点修正值，左旋当前节点

}

}

3.3  删除

与BST一样，在Treap中删除元素要考虑多种情况。我们可以按照在BST中删除元素同样的方法来删除Treap中的元素，即用它的后继(或前驱)节点的值代替它，然后删除它的后继(或前驱)节点。

上述方法期望时间复杂度为O(logN)，但是这种方法并没有充分利用Treap已有的随机性质，而是重新得随机选取代替节点。我们给出一种更为通用的删除方法，这种方法是基于旋转调整的。首先要在Treap树中找到待删除节点的位置，然后分情况讨论：

情况一，该节点为叶节点或链节点，则该节点是可以直接删除的节点。若该节点有非空子节点，用非空子节点代替该节点的，否则用空节点代替该节点，然后删除该节点。

情况二，该节点有两个非空子节点。我们的策略是通过旋转，使该节点变为可以直接删除的节点。如果该节点的左子节点的优先级小于右子节点的优先级，右旋该节点，使该节点降为右子树的根节点，然后访问右子树的根节点，继续讨论；反之，左旋该节点，使该节点降为左子树的根节点，然后访问左子树的根节点，这样继续下去，直到变成可以直接删除的节点。

BST_Node*root;

voidTreap_Delete(Treap_Node*&P,int*value)//节点指针要传递引用

{

if(value==P->value)//找到要删除的节点对其删除

{

if(!P->right||!P->left)//情况一，该节点可以直接被删除

{

Treap_Node*t=P;

if(!P->right)

P=P->left;//用左子节点代替它

else

P=P->right;//用右子节点代替它

deletet;//删除该节点

}

else//情况二

{

if(P->left->fix<P->right->fix)//左子节点修正值较小，右旋

{

Treap_Right_Rotate(P);

Treap_Delete(P->right,r);

}

else//左子节点修正值较小，左旋

{

Treap_Left_Rotate(P);

Treap_Delete(P->left,r);

}

}

}

elseif(value<P->value)

Treap_Delete(P->left,r);//在左子树查找要删除的节点

else

Treap_Delete(P->right,r);//在右子树查找要删除的节点

}

可以这样定义结构体：

structTreap_Node

{

Treap_Node*left,*right;//节点的左右子树的指针

intvalue,fix,weight,size;//节点的值，优先级，重复计数（记录相同节点个数，节省空间），子树大小

inlineintlsize(){returnleft?left->size?0;}//返回左子树的节点个数

inlineintrsize(){returnright?right->size?0;}//返回右子树的节点个数

};

5.总结

Treap作为一种简洁高效的有序数据结构，在计算机科学和技术应用中有着重要的地位。它可以用来实现集合、多重集合、字典等容器型数据结构，也可以用来设计动态统计数据结构。

6.参考资料

（1）Treap：http://www.nocow.cn/index.php/Treap
（2）随机平衡二叉查找树Treap的分析与应用：http://www.byvoid.com/blog/wp-content/uploads/2010/12/treap-analysis-and-application.pdf