介绍

操作(插入 删除 查找 分离 合并 旋转)

算法分析

介绍

我们可以看到，如果一个二叉排序树节点插入的顺序是随机的，这样我们得到的二叉排序树大多数情况下是平衡的，即使存在一些极端情况，但是这种情况发生的概率很小，所以我们可以这样建立一颗二叉排序树，而不必要像AVL那样旋转，可以证明随机顺序建立的二叉排序树在期望高度是，但是某些时候我们并不能得知所有的带插入节点，打乱以后再插入。所以我们需要一种规则来实现这种想法，并且不必要所有节点。也就是说节点是顺序输入的，我们实现这一点可以用Treap。

Treap=Tree+Heap

Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。

操作

Treap维护堆性质的方法用到了旋转，这里先简单地介绍一下。Treap只需要两种旋转，这样编程复杂度比Splay等就要小一些，这正是Treap的特色之一。

旋转是这样的： Image:Treap Rotate.jpg

插入

给节点随机分配一个优先级，先和二叉排序树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是跟的左儿子就右旋如果当前节点是跟个右儿子就左旋。

我们如果把插入写成递归形式的话，只需要在递归调用完成后判断是否满足堆性质，如果不满足就旋转，实现非常容易。

由于旋转是的，最多进行h次(h是树的高度),插入的复杂度是log( n )的，在期望情况下，所以它的期望复杂度是 O( log( N ) );

插入代码:

void insert(int &x,int y)

{

if (x==0)

{

x=++size;

e[x].l=0;e[x].r=0;e[x].a=y;e[x].b=rand()*rand();

e[x].ll=0;e[x].rr=0;// .ll记录了左儿子个数. .RR记录了右儿子个数 .l记录了左儿子编号. .R记录了右儿子编号。

return;

}

if (y>e[x].a)

{

insert(e[x].r,y);

e[x].rr++;

if (e[x].b>e[e[x].r].b) right(x);

return;

}

if (y<=e[x].a)

{

insert(e[x].l,y);

e[x].ll++;

if(e[x].b>e[e[x].l].b) left(x);

return;

}

}

删除

有了旋转的操作之后，Treap的删除比二叉排序树还要简单。因为Treap满足堆性质，所以我们只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。

删除最多进行log( n )次旋转，期望复杂度是log( n )。

void Delete(int &x,int y)

{

if (e[x].a==y)

{

if (e[x].l==0||e[x].r==0)

{

if (e[x].l==0)

{x=e[x].r;return;}

if (e[x].r==0)

{x=e[x].l;return;}

}

if (e[e[x].l].b<e[e[x].r].b)

{

left(x);

e[x].rr--;

Delete(e[x].r,y);

}else

{

right(x);

e[x].ll--;

Delete1(e[x].l,y);

}

}

else

{

if (e[x].a>y) { e[x].ll--;Delete1(e[x].l,y);}

if (e[x].a<=y) { e[x].rr--;Delete1(e[x].r,y);}

}

}

第二种删除方法：为保证效率，可以用普通二叉查找树的删除方法，找到节点的中序前缀，然后替换，删除，并使用非递归。虽然时间复杂度仍为log级别，但常数因子小了很多。

Pascal代码：

procedure del(x:longint);

var

now,MinMax,p:point;

begin

now:=root; //root为根指针

null^.x:=x;

while now^.x <> x do

begin

p:=now;

if now^.x > x then

now:=now^.l

else

now:=now^.r;

end;

if now = null then // 没找到X

exit;

if now^.l <> null then // 左子树不为空，往左找

begin

MinMax:=now^.l;

p:=now;

while MinMax^.r <> null do

begin

p:=MinMax;

MinMax:=MinMax^.r;

end;

now^.x:=MinMax^.x;

if p <> now then

p^.r:=MinMax^.l

else

p^.l:=MinMax^.l;

dispose(MinMax);

end

else

if now^.r <> null then // 右子树不为空，往右找

begin

MinMax:=now^.r;

p:=now;

while MinMax^.l <> null do

begin

p:=MinMax;

MinMax:=MinMax^.l;

end;

now^.x:=MinMax^.x;

if p <> now then

p^.l:=MinMax^.r

else

p^.r:=MinMax^.r;

dispose(MinMax);

end

else // X本身是叶子

begin

if p^.x > x then

p^.l:=null

else

p^.r:=null;

dispose(now);

end;

end;

查找

和一般的二叉排序树一样，但是由于Treap的随机化结构，可以证明Treap中查找的期望复杂度是log( n )。

分离

要把一个Treap按大小分成两个Treap，只要在需要分开的位置加一个虚拟节点，然后旋至根节点删除，左右两个子树就是得出的两个Treap了。根据二叉排序树的性质，这时左子树的所有节点都小于右子树的节点。

时间相当于一次插入操作的复杂度，也就是 log( n )

合并

合并是指把两个Treap合并成一个Treap，其中第一个Treap的所有节点都必须小于或等于第二个Treap中的所有节点，也就是分离的结果所要满足的条件。合并的过程和分离相反，只要加一个虚拟的根，把两棵树分别作为左右子树，然后把根删除就可以了。

时间复杂度和删除一样，也是期望

旋转

旋转就是把random出来的值进行维护堆得性质的操作.因为BST得特殊性质,所以在旋转时,还要维护BST的性质。

void right(int &x)

{

int j=e[x].r;

e[x].r=e[j].l;

e[x].rr=e[j].ll;

e[j].l=x;

e[j].ll=e[x].ll+e[j].ll+1;

x=j;

}

void left(int &x)

{

int j=e[x].l;

e[x].l=e[j].r;

e[x].ll=e[j].rr;

e[j].r=x;

e[j].rr=e[x].rr+e[j].rr+1;

x=j;

}

算法分析

首先我们注意到二叉排序树有一个特性，就是每个子树的形态在优先级唯一确定的情况下都是唯一的，不受其他因素影响，也就是说，左子树的形态与树中大于根节点的值无关，右子树亦然。

这是因为Treap满足堆的性质，Treap的根节点是优先级最大的那个节点，考虑它的左子树，树根也是子树里面最大的一点，右子树亦然。所以Treap相当于先把所有节点按照优先级排序，然后插入，实质上就相当于以随机顺序建立的二叉排序树，只不过它并不需要一次读入所有数据，可以一个一个地插入。而当这个随机顺序确定的时候，这个树是唯一的。

因此在给定优先级的情况下，只要是用符合要求的操作，通过任何方式得出的Treap都是一样的，所以不改变优先级的情况下，特殊的操作不会造成Treap结构的退化。而改变优先级可能会使Treap变得不够随机以致退化。

证明随机建立二叉排序树的大家可以参见CLRS P265 12.4 Randomly built binary search trees，这里略去。

如果有我们就证明了，Treap插入的期望复杂度是

Treap的其它操作的期望复杂度同样是

优点与缺点

优点

实现简单，效率高，性价比很高

缺点

引用

外部链接

一个Treap的演示(做得太好了，不说了大家看看就知道了...)

Randomized Search Trees(pdf), 有对Treap和它的加权形式的详尽介绍以及复杂度的严格证明