本文将介绍 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() 操作是把某个给定节点上移一个位置，并保证二叉搜索树的性质不改变（如下图），建议参照代码理解。

CPP

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，如下图。

代码：

CPP

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

。

CPP

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

维护父节点信息

CPP

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

CPP

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);//维护平衡
}

删除节点

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

CPP

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，只需要判断出当前排名在树的哪个部分即可，类似于权值线段树。

CPP

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

的节点个数加一。

CPP

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

查询前驱和后继

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

CPP

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

级别的。具体的，若当前节点的左子树大小加一比分裂排名要小，则分裂右子树，否则分裂左子树。

CPP

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 树。此时采用按照树高合并的办法，若左边的树比右边的树高，则合并左边的树的右子树和右边的树，反之合并右边的树的左子树和左边的树。

CPP

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() 类似，只是进入右子树时将左子树和根的权值累加进贡献。

CPP

#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]。再给这段区间的树根打上标记，下放标记就代表交换左右子树。

CPP

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

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

可持久化

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

CPP

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

可持久化平衡树代码

可持久化文艺平衡树代码

习题

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

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

文章操作