左偏树

· · 个人记录

左偏树是一种支持在 O(\log n) 的时间复杂度进行合并的数据结构。

Define

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

距离：一个节点 x 的距离 dist_x 定义韦其子树中与结点 x 最近的外结点到 x 的距离。特别的，定义空结点的距离为 -1 。

左偏树的基本性质

左偏树具有堆的性质，还有左偏性质：即对于每个结点x，有 dist_{ls}\ge dist_{rs}

基本结论

1.结点 x 的距离dist_x=dist_{rs}+1

2.距离为 n 的左偏树至少有2^{n+1}-1 个结点，形态是一棵满二叉树

操作

合并

定义 merge(x,y) 为合并两棵分别以 x,y 为根结点的左偏树，其返回值合并为合并之后的根节点。

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

  1. 若将 v_x\le v_y，以 x 作为合并之后的根节点， 否则以 y 作为合并之后的根节点,若有 v_x>v_y 交换 x,y。

  2. 将 y 与 x 的其中一个儿子合并，用合并后的根节点代替与 y 合并的儿子的位置，并返回 x。

  3. 重复操作，直到有一个为空。

  4. 返回时若有 dist_{ls}\ge dist_{rs}，没有则交换两边，并且维护该数组为 dist_x=dist_{rs}+1。

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) ，那么可以类比使用路径压缩的方式，求一个结点所在左偏树的根节点，写成:

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

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

合并写法：

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

删除写法:

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