AVL 树：区间操作和可持久化

xzz_cat6 · 2025-01-19 10:57:09 · 算法·理论

本文将介绍 AVL 树的基础操作，区间操作（分裂和合并），可持久化。

在读本文之前，默认读者已经会 BST（二叉搜索树）的全部操作。

AVL 树的定义与性质

空二叉树是一个 AVL 树。
如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 |h(ls) - h(rs)| \leq 1，h 是其左右子树的高度。
树高为 O(\log n)。
定义平衡因子 BF=h(ls) - h(rs)。
一个树平衡，当且仅当这个树满足性质 3。

由于性质二，其在实现二叉搜索树时，时间复杂度为对数级别的。

AVL 树的平衡维护

AVL 树为了保证性质二，利用旋转操作维护平衡，这也是其与 BST 唯一的不同点。

旋转

rotate() 操作是把某个给定节点上移一个位置，并保证二叉搜索树的性质不改变（如下图），建议参照代码理解。

void rotate(int &u,bool f){
  int v=ch[u][f];
  ch[u][f]=ch[v][!f];
  ch[v][!f]=u;
  pushup(u),pushup(v),u=v;
}

维护平衡

如果对于某一个节点，性质 2 不再满足，由于我们每次只插入/删除一个节点，对树高的影响不超过 1，因此该节点的平衡因子的绝对值至多为 2。由于对称性，我们在此只讨论左子树的高度比右子树大 2 的情况，即下图中 h(B)-h(E)=2。此时，还需要根据 h(D) 和 h(C) 的大小关系分两种情况讨论。需要注意的是，由于我们是自底向上维护平衡的，因此对节点 D 的所有后代来说，性质 2 仍然是被满足的。

情况 1：如上图，发现 D 的树高比 C 的树高大，此时只需要旋转 B 到 A 处，即左旋 A。旋转完后如下图。

情况 2：如上图，发现 D 的树高比 C 的树高要小，手模一下发现不能直接左旋 A，否则仍然不平衡。此时需要先右旋 B，再左旋 A，如下图。

代码：

void maintain(int &u){
    int chk=BF(u);
    if(chk>1){
      if(BF(ls(u))<=0)  rotate(ls(u),1);
      rotate(u,0);
    }
    else if(chk<-1){
      if(BF(rs(u))>=0)  rotate(rs(u),0);
      rotate(u,1);
    }
    else if(u)  pushup(u);
}

基本操作

变量和宏定义

建议先跳过此部分，后文中遇到了变量再来这里对照。	变量名	含义
rt	根
tot	节点数
ls,ch[0]	左儿子
rs,ch[1]	右儿子
siz	子树内节点个数
h	子树树高
val	节点权值
BF	子树平衡因子

新建空节点

空节点权值为 x。

int newnode(int x){
    int u=++tot;
    val[u]=x,siz[u]=h[u]=1,ls(u)=rs(u)=0;
    return u;
}

维护父节点信息

void pushup(int u){
        siz[u]=siz[ls(u)]+siz[rs(u)]+1;
        h[u]=max(h[ls(u)],h[rs(u)])+1;
}

旋转

即上文的 rotate() 和 maintain() 函数。

插入节点

与 BST（二叉搜索树）的插入操作基本相同，只不过要用递归实现，每次插入后维护平衡。当我们插入一个节点，如果这个点的权值大于当前点的权值，就要去搜索右子树，反之搜索左子树。

void insert(int &u,int w){
    if(!u)  return void(u=newnode(w));
    if(val[u]<w)    insert(rs(u),w);
    else    insert(ls(u),w);
    maintain(u);//维护平衡
}

删除节点

先找到这个节点，之后如果删除节点最多有一个儿子，那么我们用它的儿子顶替它，否则和后继交换，返回时维护平衡。

void del(int &u,int w){
    if(!u)  return;
    if(val[u]==w){
      int v=u;
      if(ls(u)&&(v=rs(u))){
        while(ls(v))    v=ls(v);
        val[u]=val[v],del(rs(u),val[v]);
      }
      else  u=ls(u)?ls(u):rs(u);
    }
    else if(val[u]<w)   del(rs(u),w);
    else    del(ls(u),w);
    maintain(u);
}

查询第k小

等价于 BST，只需要判断出当前排名在树的哪个部分即可，类似于权值线段树。

int kth(int x){
    int u=rt,tmp=0;
    while(u){
      if((tmp=siz[ls(u)]+1)==x) return val[u];
      else  u=((tmp>x)?ls(u):(x-=tmp,rs(u)));
    }
    return -1;
}

查询排名

等价于 BST，直接计算该子树中小于 val 的节点个数加一。

int qrk(int x){
    int ans=1,u=rt;
    while(u){
      if(val[u]<x)  ans+=siz[ls(u)]+1,u=rs(u);
      else  u=ls(u);
    }
    return ans;
}

查询前驱和后继

利用二叉搜索树的性质求即可。

int pre(int x){
    int u=rt,ans=1-(1<<31);
    while(u){
      if(val[u]>=x) u=ls(u);
      else  ans=val[u],u=rs(u);
    }
    return ans;
}
int nxt(int x){
    int u=rt,ans=(1<<31)-1;
    while(u){
      if(val[u]<=x) u=rs(u);
      else  ans=val[u],u=ls(u);
    }
    return ans;
}

到这里就可以做一道模板题了，如果还不会建议先敲一遍，代码。

复杂度证明

设 f_n 为高度为 n 的 AVL 树所包含的最少节点数，则有

f_n= \begin{cases} 1&(n=1)\\ 2&(n=2)\\ f_{n-1}+f_{n-2}+1& (n>2) \end{cases}

根据常系数非齐次线性差分方程的解法，\{f_n+1\} 是一个斐波那契数列。这里 f_n 的通项为：

f_n=\frac{5+2\sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{5-2\sqrt{5}}{5}\left(\frac{1-\sqrt{5}}{2}\right)^n-1

斐波那契数列以指数的速度增长。对于树高 n 有：

n<\log_{\frac{1+\sqrt{5}}{2}} (f_n+1)<\frac{3}{2}\log_2 (f_n+1)

因此 AVL 树的高度为 O(\log f_n)，这里的 f_n 为结点数。

区间操作

由于要将操作区间提取出来，所以不可避免的需要分裂和合并操作，又由于下文中的分裂和合并会破坏 AVL 树的性质2，所以分裂和合并后的树不是标准的 AVL 树，但是依旧能用旋转操作将树高维持在 \log n，即满足性质3，下文中称满足性质 3 但是不满足性质 2 的树为半 AVL 树。

分裂

现在有一颗半 AVL 树，现在要按照排名分裂，将其按照 FHQtreap 的方法分裂后，不进行任何维护平衡的操作，这样两棵树的树高依旧保持在 \log n 级别的。具体的，若当前节点的左子树大小加一比分裂排名要小，则分裂右子树，否则分裂左子树。

void split(int &rt1,int &rt2,int p,int x){
    if(!x){
        rt1=0,rt2=p;
        return;
    }
    if(siz[ls(p)]+1<=x){
        rt1=p;
        split(rs(p),rt2,rs(p),x-siz[ls(p)]-1);
        pushup(p);
        return;
    }
    else{
        rt2=p;
        split(rt1,ls(p),ls(p),x);
        pushup(p);
        return;
    }
}

合并

依旧是两颗半 AVL 树，且值域不相交。现在要将其合并成一颗半 AVL 树。此时采用按照树高合并的办法，若左边的树比右边的树高，则合并左边的树的右子树和右边的树，反之合并右边的树的左子树和左边的树。

inline int merge(int u,int v){
    if(!u)  return v;
    if(!v)  return u;
    if(h[u]>=h[v]){
        rs(u)=merge(rs(u),v);
        maintain(u);
        return u;
    }
    else{
        ls(v)=merge(u,ls(v));
        maintain(v);
        return v;
    }
}

区间和

假设现在要查询区间 [l,r] 的权值和，则利用前缀和，变成查找区间 [1,r] 的和减去区间 [1,l-1] 的和。查询过程与 kth() 类似，只是进入右子树时将左子树和根的权值累加进贡献。

#define ll long long
ll query(int u,int k){
    ll res=0;
    while(1){
        pushdown(u);
        if(k==siz[ls(u)]){
            res+=sum[ls(u)];
            return res;
        }   
        if(k==siz[ls(u)]+1){
            res+=sum[ls(u)]+val[u];
            return res;
        }   
        if(k<siz[ls(u)])    u=ls(u);
        else{
            res+=sum[ls(u)]+val[u];
            k-=siz[ls(u)]+1,u=rs(u);
        }       
    }
    return res;
}

区间翻转

假设现在要翻转区间 [l,r]，则先分裂出区间 [l,r]。再给这段区间的树根打上标记，下放标记就代表交换左右子树。

inline void pushdown(int u){
    if(!tag[u]) return;
    swap(ls(u),rs(u));
    if(ls(u))   tag[ls(u)]^=tag[u];
    if(rs(u))   tag[rs(u)]^=tag[u];
    tag[u]=0;
}
inline void change(int &u,int l,int r){
    int x=0,y=0,z=0,t=0;
    if(r!=n)    split(t,z,u,r);
    else    t=u;
    if(l!=1)    split(x,y,t,l-1);
    else    y=t;
    tag[y]^=1;
    u=merge(merge(x,y),z);
}

到这里又可以做一道模板题了，代码。

可持久化

每当要改变树的形态时，比如：改变子树大小，子树高度，标记和左右子树时，就复制一份节点。以插入为例，注释行即为复制操作。

void insert(int &u,int k,int w){
    if(!u)  return void(u=newnode(w));
    pushdown(u);
    if(k<=siz[ls(u)]){
        ls(u)=copy(ls(u));//add
        insert(ls(u),k,w);
    }
    else{
        rs(u)=copy(rs(u));//add
        insert(rs(u),k-siz[ls(u)]-1,w);
    }
    maintain(u);
}

可持久化平衡树代码

可持久化文艺平衡树代码

习题

其中习题涉及自我复制操作，只需要自己合并自己即可。