平衡二叉树treap的构建和使用

1、Treap的构建和应用 竹子的叶子Treap的构建和使用BY 竹子的叶子一、定义叶子我没有找到定义，只是满天飞的人们提到的词，Treap=Tree+Heap，就是让二叉排序树在Heap的规则下进行一些简单的翻转，由于Heap翻转所以靠的关键字段Aux是随机生成的，所以在满足BST的同时，平衡又是随即建立起来的，消除了BST由于有序数据的插入退化的情况，所以Treap在有些地方也被称作随机二叉树（Randomize Binary Sort Tree）在Treap的翻转中，只有两种翻转：左旋和右旋，比起AVL树和扩展树（Splay Tree）的翻转要简单得多，少得多，很容易掌握。而且由于随机化，不

2、会出现退化现象，平均的插入、删除和查找效率都为。其中，在每个节点上都增加了一个用于维持Heap特性的域Aux，且为随机值，定义如下：Type TTree = Tree; Tree = Record Data,Aux:longint; Lch,Rch:TTree; End;Var Root:TTree;二、实现1、翻转这里的翻转很简单，图示就能表示清楚。而且是两个互为镜像的操作。记住，左旋是让P降落到比它小的位置上，右旋是让P降落到比它大的位置上。右旋：RotRotate_R P S S P 3 1 1 2 2 3左旋：RotRotate_L3 P S S P 1 2 3 1 2代码如下。Pro

3、cedure Rotate_R(Var P:TTree);Var S:TTree; S:=P.lch; P.lch:=S.rch; S.rch:=P; P:=S;End;Procedure Rotate_L(Var P:TTree);Var S:TTree;Begin S:=P.rch; P.rch:=S.lch; S.lch:=P; P:=S;End;2、插入插入的时候，通过二分找到当前数据的位置，然后插入。插入之后，给当前节点的Aux域给一个随机值，然后根据这个随机值，对二叉树进行翻转，这里很像Heap（根的Aux值一定=儿子的Aux），所以叫Treap。此处给出的是递归算法。（没有给出感

4、觉上效率更高的迭代算法，是因为我写不出来，太麻烦了）Procedure Insert(Var r:TTree;x:longint);Begin If r=nil then Begin New(r); r.data:=x; r.Aux:=Random(MaxLongint); R.lch:=nil; r.rch:=nil; End Else if xr.Aux then Rotate_R(r); End Else begin Insert(r.rch,x); If r.rch.Auxr.Aus then Rotate_L(r); End;End;3、删除删除和BST很相似，需要分类讨论。情况一：

5、没有儿子，直接删除；情况二：有一个儿子，将儿子放在原来其所在位置；情况三：有两个儿子，此时比较两个儿子随机值Aux的大小而进行旋转，向较大的一个儿子的方向旋转，将较小的儿子旋转上去。经过不停的旋转，到最后一定会转变为情况一或情况二（想想为什么？），然后进行删除，也是用递归写法。Procedure Delete(Var P:TTree;x:longint);Begin If (P=nil) or (p.datax) then exit Else begin If (p.lch=nil) or (p.lch=nil) then Begin If p.rch=nil then P:=P.lch el

6、se P:=P.rch; End Else begin If p.lch.Auxp.rch.Aux then Begin Rotate_L(P); Delete(p.lch,x); /此时要删除的节点就成为了P的左儿子，下面同理。 End Else begin Rotate_R(P); Delete(p.rch,x); End; End; End;End;需要说明的是，在这里，P一定要是在树上的指针，例如：Delete(root.lch,key)；否则对指针而言，下面的东西会丢失的。其实用数组模拟指针是个很不错的办法，但是叶子我比较偏爱指针，所以都写的指针代码，感兴趣的可以看一下张后面附带的用数组写的Treap。3、搜索。搜索就完全和BST一模一样了，但是不会发生退化成链条的现象，这就是引入一点点小操作给BST带来的变革，也是一种简单的消除数据顺序对BST的影响，克服了缺点。三、总结相比较AVL树、红黑书和伸展树，Treap真的是