平衡思路超简单,最早发明的自平衡二叉树,也是查询速度最快的平衡树,
luogu 阅读链接。
前言
默认读者会基本的 BST 操作。
基本操作
节点定义
平衡因子:BF(BalanceFactor),左子树高 − 右子树高。
平衡树是让树的形态尽可能像完全二叉树,而不是链。
在 AVL 中,我们认为 ∣BF∣≤1,也就是 BF 为 0,1,−1 时的子树是平衡的,否则就是不平衡的。
1 2 3 4 5 6 7
| struct node{ int ch[2], size, val, h; }d[N]; int root, tot; #define ls(x) d[x].ch[0] #define rs(x) d[x].ch[1] #define getBF(x) (d[ls(x)].h - d[rs(x)].h)
|
旋转
rotate
操作是把某个给定节点上移一个位置,并保证二叉搜索树的性质不改变。
旋转操作分为左旋和右旋(图上节点是编号)。

我们来模拟一下右旋的操作(红色是要删除的,蓝色是更改后的)。

这样就完成了一次旋转。
而在实现中,我会把左右旋写在一起。
这里的 rotate(x, 0)
表示将 x 的左儿子提到 x 的高度。
这里的 rotate(x, 1)
表示将 x 的右儿子提到 x 的高度。
1 2 3 4 5 6
| void rotate(int&now, int dir){ int t = d[now].ch[dir]; d[now].ch[dir] = d[t].ch[!dir]; d[t].ch[!dir] = now; pushup(now), pushup(t), now = t; }
|
平衡维护
如果它是平衡的,那么我们更新节点。
否则,我们考虑左子树过高的情况(右儿子同理),即 BF>1:
我们又两种可能:
左儿子的左子树较高:
图中的数字是树高。

左儿子的右子树较高:
我们先转换成第一种,再平衡。

1 2 3 4 5 6 7 8 9
| void maintain(int&x){ int BF = getBF(x); if(BF > 1){ if(getBF(ls(x)) <= 0)rotate(ls(x), 1); rotate(x, 0); } else if(BF < -1)(getBF(rs(x)) >= 0) && (rotate(rs(x), 0), 1), rotate(x, 1); else if(x)pushup(x); }
|
插入
这里我们递归插入,然后在返回时维护平衡即可。
1 2 3 4 5 6
| void insert(int&now, int val){ if(!now)return void(now = newnode(val)); if(d[now].val < val)insert(rs(now), val); else insert(ls(now), val); maintain(now); }
|
删除
如果删除节点最多有一个儿子,那么我们用它的儿子顶替它。
否则和后继交换。
记得在返回时维护。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void del(int&now, int val){ if(!now)return; if(d[now].val == val){ int w = now; if(ls(now) && (w = rs(now))){ while(ls(w))w = ls(w); d[now].val = d[w].val, del(rs(now), d[w].val); } else now = ls(now) ? ls(now) : rs(now); } else if(d[now].val < val)del(rs(now), val); else del(ls(now), val); maintain(now); }
|
复杂度证明
设 fn 为高度为 n 的 AVL 树所包含的最少节点数,则有
fn=⎩⎪⎪⎨⎪⎪⎧12fn−1+fn−2+1(n=1)(n=2)(n>2)
根据常系数非齐次线性差分方程的解法,{fn+1} 是一个斐波那契数列。这里 fn 的通项为:
fn=55+25(21+5)n+55−25(21−5)n−1
斐波那契数列以指数的速度增长,对于树高 n 有:
n<logϕ(fn+1)<23log2(fn+1)n
因此 AVL 树的高度为 O(logfn),这里的 fn 为结点数。
代码
P3369
可持久化
之后补。