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;
}
评论 (0)
