左偏树

OI 知识>数据结构
584 words

左偏树

左偏树是可并堆的一种，具有堆的性质，可快速合并.

维护如下信息：\(\text{val}\)：权值，\(\text{ls}\)：左儿子，\(\text{rs}\)：右儿子，\(\text{dist}\)：距离，\(\text{fa}\)：父亲。

一，dist

对于一棵二叉树，我们定义外结点为左儿子或右儿子为空的结点。

定义一个外结点的 \(\text{dist}\) 为 \(1\)，非外结点的 \(\text{dist}\) 为其到子树中最近外结点的距离加一，空结点的 \(\text{dist}\) 为 \(0\)。

现在有一棵 \(n\) 个结点的二叉树，则有如下性质：

  1. 根的 \(\text{dist}\) 不超过 \([log(n+1)]\)；

  2. 若该二叉树根的 \(\text{dist}\) 为 \(x\)，则至少有 \(x-1\) 层为满二叉树，至少有 \(2^x-1\) 个结点。

二，左偏树的性质

左偏树是一棵二叉树，它具有如下性质：

  1. 堆的性质；

  2. 每个结点左儿子的 \(\text{dist}\) 大于等于右儿子的 \(\text{dist}\)；

  3. 每个结点的 \(\text{dist}\) 都等于右儿子的 \(\text{dist}+1\)。

左偏树的深度无保证，一条向左的链也是左偏树。

三，核心操作——合并 merge

  1. 取值较小的根作为合并后堆的根节点；

  2. 将这个根的左儿子作为合并后堆的左儿子；

  3. 递归合并其右儿子和另一个堆，作为合并后堆的右儿子；

  4. 若合并后左儿子的 \(\text{dist}\) 小于右儿子的 \(\text{dist}\)，交换两儿子。

该操作的时间复杂度是 \(O(\log n+\log m)\) 的。

1
2
3
4
5
6
7
8
9
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(val[x]>val[y]) swap(x,y);
    rs[x]=merge(rs[x],y),fa[rs[x]]=x;
    if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
    dis[x]=dis[rs[x]]+1;
    return x;
}

四，其他操作

插入结点

将单个结点视为一个堆，合并即可。

删除根

合并根的左右儿子。

删除任意结点

合并左右儿子，自底向上更新 \(\text{dist}\)，不满足左偏性质时交换左右儿子，\(\text{dist}\) 无需更新时结束递归。

时间复杂度：\(O(\log n)\)

1
2
3
4
5
6
7
void pushup(int x)
{
    if(!x) return;
    if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
    if(dis[x]!=dis[rs[x]]+1)
        dis[x]=dis[rs[x]]+1,pushup(fa[x]);
}

对整个堆进行加/减/乘运算

在根上打标记，删除根/合并堆时下传即可。

Comments