11
30
2015
0

Treap学习笔记~

Treap的基本操作:

插入操作(Insert)=bst插入操作+旋转操作

bst插入——递归思想:同普通排序二叉树的插入操作相同
从根节点开始向下不断寻找,p==0表示该位置能插入待扩展,则在此位置建立节点后不断返回上一层,从下往上更新节点的Ln/rn属性值
注意,这里的p为引用,效果为:
在返回上一层父节点时,父节点的子节点就会更新为p
新的节点直接使用insert(p,x)插入即可,p的初始值为0
void Insert(int &p,int x)
{
	if(p==0)//表示该节点尚不存在
	{
		p=++tot;
		t[p].key=x;
		t[p].pro=rand();
		t[p].L=t[p].r=0;//此时的左右结点还都是未扩展的
		t[p].Ln=t[p].rn=0;
		return;
	}
	if(x<=t[p].key)
	{
		Insert(t[p].L,x);
		t[p].Ln++;
	}
	else
	{
		Insert(t[p].r,x);
    t[p].rn++;
  }
}

旋转——维持平衡的关键

递归插入之后判断是否需要旋转

由于上面的引用更新,插入节点的子节点p'=t[p].L
则旋转条件t[p'].pro<t[p].pro等价于t[t[p].L]<t[p].pro
p'为p右节点时同理
更新的过程就变成了这样:
if(x<=t[p].key)
	{
		Insert(t[p].L,x);
		t[p].Ln++;
		if(t[t[p].L].pro<t[p].pro) Zag(p);
	}
else
	{
		Insert(t[p].r,x);
                t[p].rn++;
                if(t[t[p].r].pro<t[p].pro) Zig(p);
        }

具体的旋转过程?

——因为这里构造的是小根堆,或许我们可以这样理解:权值重吊在下面,权值轻的被拉上去

这样何时左旋何时右旋就清楚了。左旋(Zig)和右旋(Zag)是互逆操作

       左旋——当前根节点变为其右节点的左子节点,其右节点变为根节点

       具体操作:维护根节点、L/r、Ln/rn

p的右节点叫k——
k将他的左节点给p作为右节点,k的左节点由p补上(这两个步骤显然是不能颠倒的)——
rn与Ln的变化(记得算上子树的根节点)——
最后的p=k,引用更新当前子树根节点(颇有点“苍天已死,黄天当立”的意味~)
 
       右旋同理
void Zig(int &p)
{
	int k=t[p].r;
	t[p].r=t[k].L;
	t[k].L=p;
	t[p].rn=t[k].Ln;
	t[k].Ln=1+t[p].Ln+t[p].rn;
	p=t;
}
void Zag(int &p)
{
	int k=t[p].L;
	t[p].L=t[k].r;
	t[k].r=p;
	t[p].Ln=t[k].rn;
	t[k].rn=1+t[p].Ln+t[p].rn;
	p=t;
}
Category: 平衡树 | Tags: | Read Count: 204

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com