一、左偏树是什么

左偏树的基础——堆

我们曾经学习过基础数据结构之一——堆(heap)

堆支持三种操作(以小根堆为例)

1、查询(query):查询堆中最小的元素

2、删除(del):删除堆中的任意一个元素

3、插入(insert):插入一个新元素

4、维护(modify):维护堆的性质:任何非叶子结点的权值都大于它的所有子结点。在删除和插入后进行维护

左偏树的用途

如果题目要求我们将两个不相关但类型相同(都是大根对或小根堆)的堆合并成一个大堆,我们就用到了左偏树。

二、左偏树的变量定义

$child[i][0]$和 $child[i][1]$是左右结点的指针,$val[i]$是当前结点的权值,$dis[i]$是当前结点的距离标号,$fa[i]$该结点的父节点

距离标号:当前结点到离它最近的叶子节点的距离

三、左偏树的性质(以小根堆为例)

(1)、节点的权值小于等于它左右儿子的权值。

和堆的性质相同

(2)、节点的左儿子的距离不小于右儿子的距离。

这就是为什么这棵树叫做左偏树,也就是左边的结点总数始终大于或等于右边孩子的结点总数

在写平衡树的时候,我们是确保它的深度尽量的小,这样访问每个节点都很快。但是左偏树不需要这样,它的目的是快速提取最小节点和快速合并。所以它并不平衡,而且向左偏。但是距离和深度不一样,左偏树并不意味着左子树的节点数或是深度一定大于右子树。

(3)、节点的距离等于右儿子的距离+1。

(4)、一个 n 个节点的左偏树距离最大为 $log(n+1)-1$

证明如下:

若左偏树的距离为一定值,则结点数最少的左偏树是完全二叉树。

结点最少的话,就是左右儿子距离一样,这就是完全二叉树了。

若一棵左偏树的距离为 k,则这棵左偏树至少有 $2^{k+1}-1$个节点。

距离为 k 的完全二叉树高度也是 k,节点数就是 $2^{k+1}-1$个。

这样就可以证明性质四了。

因为 $n\geq 2^{k+1}-1$,所以 $k\leq log(n+1)-1$。

四、左偏树的操作

(1)、合并

现在有两个小根堆 A,B,要将他们合并

1、如果 A 根结点的权值大于 B 根结点,便交换 A,B,保证接下来操作时 A 根结点的权值小于或等于 B 根结点。

2、把 A 结点的根结点作为两树合并后的新树 C 的根结点

3、合并 A 的右子树和 B 堆,因为左偏树的左子树较重,所以为了维持操作时间复杂度为 $O(logN)$,所以合并 A 的右子树和 B 堆。

4、合并了 A 的右子树和 B 之后,A 的右子树的距离可能会变大,当 A 的右子树的距离大于 A 的左子树的距离时,性质 2 会被破坏。在这种情况下,我们只须要交换 A 的右子树和左子树。

而且因为 A 的右子树的距离可能会变,所以要更新 A 的距离标号。这样就合并就结束了。

再理解一下代码:

int merge (int x,int y)
{
    if (x==0||y==0)
        return x+y;
    if (val[x]>val[y]||(val[x]==val[y]&&x>y))
        swap (x,y);
    child[x][1]=merge (child[x][1],y);
    fa[child[x][1]]=x;
    if (dis[child[x][0]]<dis[child[x][1]])
        swap (child[x][0],child[x][1]);
    dis[x]=dis[child[x][1]]+1;
    return x;
}

时间复杂度:我们可以看出每次我们都把它的右子树放下去合并。因为一棵树的距离取决于它右子树的距离 (性质三),所以拆开的过程不会超过它的距离。根据性质四,不会超过 $log(n_x+1)+log(n_y+1)-2$,复杂度就是 $O(log(n_x)+log(n_y))$

(2)、插入

插入一个节点,就是把一个点和一棵树合并起来。

因为其中一棵树只有一个节点,所以插入的效率是 $O(log n)$

(3)删除最小/大点

因为根是最小/大点,所以可以直接把根的两个儿子合并起来。

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,m;
int child[MAXN][2],val[MAXN],dis[MAXN],fa[MAXN];
int merge (int x,int y)
{
    if (x==0||y==0)
        return x+y;
    if (val[x]>val[y]||(val[x]==val[y]&&x>y))
        swap (x,y);
    child[x][1]=merge (child[x][1],y);
    fa[child[x][1]]=x;
    if (dis[child[x][0]]<dis[child[x][1]])
        swap (child[x][0],child[x][1]);
    dis[x]=dis[child[x][1]]+1;
    return x;
}
int get_rt (int x)
{
    while (fa[x])
        x=fa[x];
    return x;
}
void del (int x)
{
    val[x]=-1;
    fa[child[x][0]]=fa[child[x][1]]=0;
    merge (child[x][0],child[x][1]);
}
int main()
{
    scanf ("%d%d",&n,&m);
    dis[0]=-1;
    for (int i=1;i<=n;i++)
        scanf ("%d",&val[i]);
    for (int i=1;i<=m;i++)
    {
        int opt,x,y;
        scanf ("%d",&opt);
        if (opt==1)
        {
            scanf ("%d%d",&x,&y);
            if (x!=y&&val[x]!=-1&&val[y]!=-1)
            {
                int x_rt=get_rt (x),y_rt=get_rt (y);
                merge (x_rt,y_rt);
            }
        }
        else
        {
            scanf ("%d",&x);
            if  (val[x]==-1)
                printf ("-1\n");
            else
            {
                int x_rt=get_rt (x);
                printf ("%d\n",val[x_rt]);
                del (x_rt);
            }
        }
    }
    return 0;
}
分类: 文章

1 条评论

hgjkgj · 2018年8月14日 7:42 下午

%%%¥

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注