左偏树

左偏树是一种支持在

O(\log n)

的时间复杂度进行合并的数据结构。

Define

外结点 : 左儿子或者右儿子是空结点的结点。

距离：一个节点

x

的距离 dist_x 定义韦其子树中与结点

x

左偏树的基本性质

左偏树具有堆的性质，还有左偏性质：即对于每个结点x，有

dist_{ls}\ge dist_{rs}

基本结论

1.结点

x

的距离

dist_x=dist_{rs}+1

2.距离为

n

的左偏树至少有

2^{n+1}-1

个结点，形态是一棵满二叉树

操作

合并

定义 merge(x,y) 为合并两棵分别以

x,y

为根结点的左偏树，其返回值合并为合并之后的根节点。

这里以小根堆举例，大根堆则将判断大小的符号换过来即可。

若将 $v_x\le v_y$ ，以 $x$ 作为合并之后的根节点，否则以 $y$ 作为合并之后的根节点,若有 $v_x>v_y$ 交换 $x,y$ 。
将 $y$ 与 $x$ 的其中一个儿子合并，用合并后的根节点代替与 $y$ 合并的儿子的位置，并返回 $x$ 。
重复操作，直到有一个为空。
返回时若有 $dist_{ls}\ge dist_{rs}$ ，没有则交换两边，并且维护该数组为 $dist_x=dist_{rs}+1$ 。

CPP

int merge(int x,int y){
    if(!x||!y)return x+y;
    if(v[y]<v[x])swap(x,y);
    rs(x)=merge(rs(x),y);
    if(dist[ls(x)]<dist[rs(x)])swap(ls(x),rs(x));
    dist[x]=dist[rs(x)]+1;
    return x;
}

插入给定值

新建结点，并且合并即可。

求最值

最值为根节点的值（堆的性质）。

删除

将删除结点的左右结点合并，然后修改删除结点信息杰克。

最后再开一个维护父亲结点的数组维护父亲暴力跳即可。

这里维护父亲结点，可能会退化成

O(n)

，那么可以类比使用路径压缩的方式，求一个结点所在左偏树的根节点，写成:

CPP

int find(int x){
    if(rt[x]!=x)rt[x]=find(rt[x]);
    return rt[x];
}

那么维护 rt[x] 可以塞进其它函数里面直接处理：

合并写法：

CPP

void Merge(int x,int y){
    rt[x]=rt[y]=merge(x,y);
}

删除写法:

CPP

void Delete(int x){
    rt[ls(x)]=rt[rs(x)]=rt[x]=merge(ls(x),rs(x));
}//rt也要改不然有些数字可能会指向rt[x]最后找不到正确根

文章操作

Define

左偏树的基本性质

基本结论

操作

合并

插入给定值

求最值

删除

相关推荐

评论

左偏树