AVL 树基础

xzz_cat6 · 2026-01-05 10:09:45 · 算法·理论

AVL 是一种平衡树，和 BST（二叉搜索树）用途相同。

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

在读本文之前，默认读者已经会 BST 的全部操作。

AVL 树的定义与性质

定义平衡因子 BF=h(ls) - h(rs)，其中 h 表示树高。
空二叉树是一个 AVL 树。
如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 |BF| \leq 1。
维护一颗二叉搜索树满足 AVL 的性质的过程叫做维护平衡。

AVL 树的平衡维护

AVL 利用旋转操作维护平衡。

旋转

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;
}

维护平衡

如果对于某一个节点，|BF|\ge2，由于我们每次只插入/删除一个节点，对树高的影响不超过 1，因此 |BF|=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;
}

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

复杂度证明

此处证明 AVL 树的树高为 O(\log n)。

设 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 为结点数。

可持久化

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

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);
}

代码可以去这里看。