本地源文件：docs/ds__avl.md

AVL 树

AVL 树，是一种平衡的二叉搜索树．由于各种算法教材上对 AVL 的介绍十分冗长，造成了很多人对 AVL 树复杂、不实用的印象．但实际上，AVL 树的原理简单，实现也并不复杂．

性质

空二叉树是一个 AVL 树
如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 |ℎ(𝑙𝑠) −ℎ(𝑟𝑠)| ≤1|h(ls)−h(rs)|≤1，h 是其左右子树的高度
树高为 𝑂(log⁡𝑛)O(log⁡n)

平衡因子：右子树高度 - 左子树高度

树高的证明

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

𝑓𝑛=⎧{ {⎨{ {⎩1(𝑛=1)2(𝑛=2)𝑓𝑛−1+𝑓𝑛−2+1(𝑛>2)fn={1(n=1)2(n=2)fn−1+fn−2+1(n>2)

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

𝑓𝑛=5+2√55(1+√52)𝑛+5−2√55(1−√52)𝑛−1fn=5+255(1+52)n+5−255(1−52)n−1

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

𝑛<log1+√52⁡(𝑓𝑛+1)<32log2⁡(𝑓𝑛+1)n<log1+52⁡(fn+1)<32log2⁡(fn+1)

因此 AVL 树的高度为 𝑂(log⁡𝑓𝑛)O(log⁡fn)，这里的 𝑓𝑛fn 为结点数．

过程

插入结点

与 BST（二叉搜索树）中类似，先进行一次失败的查找来确定插入的位置，插入节点后根据平衡因子来决定是否需要调整．

删除结点

删除和 BST 类似，将结点与后继交换后再删除．

删除会导致树高以及平衡因子变化，这时需要沿着被删除结点到根的路径来调整这种变化．

平衡的维护

插入或删除节点后，可能会造成 AVL 树的性质 2 被破坏．因此，需要沿着从被插入/删除的节点到根的路径对树进行维护．如果对于某一个节点，性质 2 不再满足，由于我们只插入/删除了一个节点，对树高的影响不超过 1，因此该节点的平衡因子的绝对值至多为 2．由于对称性，我们在此只讨论左子树的高度比右子树大 2 的情况，即下图中 ℎ(𝐵) −ℎ(𝐸) =2h(B)−h(E)=2．此时，还需要根据 ℎ(𝐴)h(A) 和 ℎ(𝐶)h(C) 的大小关系分两种情况讨论．需要注意的是，由于我们是自底向上维护平衡的，因此对节点 D 的所有后代来说，性质 2 仍然是被满足的．

情况一：A 点树高不小于 C 点树高

设 ℎ(𝐸) =𝑥h(E)=x，则有

⎧{ {⎨{ {⎩ℎ(𝐵)=𝑥+2ℎ(𝐴)=𝑥+1𝑥≤ℎ(𝐶)≤𝑥+1{h(B)=x+2h(A)=x+1x≤h(C)≤x+1

其中 ℎ(𝐶) ≥𝑥h(C)≥x 是由于节点 B 满足性质 2，因此 ℎ(𝐶)h(C) 和 ℎ(𝐴)h(A) 的差不会超过 1．此时我们对节点 D 进行一次右旋操作（旋转操作与其它类型的平衡二叉搜索树相同），如下图所示．

显然节点 A、C、E 的高度不发生变化，并且有

⎧{ {⎨{ {⎩0≤ℎ(𝐶)−ℎ(𝐸)≤1𝑥+1≤ℎ′(𝐷)=max(ℎ(𝐶),ℎ(𝐸))+1=ℎ(𝐶)+1≤𝑥+20≤ℎ′(𝐷)−ℎ(𝐴)≤1{0≤h(C)−h(E)≤1x+1≤h′(D)=max(h(C),h(E))+1=h(C)+1≤x+20≤h′(D)−h(A)≤1

因此旋转后的节点 B 和 D 也满足性质 2．

情况二：A 点树高小于 C 点树高

设 ℎ(𝐸) =𝑥h(E)=x，则与刚才同理，有

⎧{ {⎨{ {⎩ℎ(𝐵)=𝑥+2ℎ(𝐶)=𝑥+1ℎ(𝐴)=𝑥{h(B)=x+2h(C)=x+1h(A)=x

此时我们先对节点 B 进行一次左旋操作，再对节点 D 进行一次右旋操作，如下图所示．

显然节点 A、E 的高度不发生变化，并且 B 的新右儿子和 D 的新左儿子分别为 C 原来的左右儿子，则有

⎧{ { { {⎨{ { { {⎩𝑥−1≤ℎ′(𝑟𝑠𝐵),ℎ′(𝑙𝑠𝐷)≤𝑥0≤ℎ(𝐴)−ℎ′(𝑟𝑠𝐵)≤10≤ℎ(𝐸)−ℎ′(𝑙𝑠𝐷)≤1ℎ′(𝐵)=max(ℎ(𝐴),ℎ′(𝑟𝑠𝐵))+1=𝑥+1ℎ′(𝐷)=max(ℎ(𝐸),ℎ′(𝑙𝑠𝐷))+1=𝑥+1ℎ′(𝐵)−ℎ′(𝐷)=0{x−1≤h′(rsB),h′(lsD)≤x0≤h(A)−h′(rsB)≤10≤h(E)−h′(lsD)≤1h′(B)=max(h(A),h′(rsB))+1=x+1h′(D)=max(h(E),h′(lsD))+1=x+1h′(B)−h′(D)=0

因此旋转后的节点 B、C、D 也满足性质 2．

维护平衡操作：伪代码 1𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 MaintainBalance(𝑝)2𝑙←𝑙𝑠𝑝,𝑟←𝑟𝑠𝑝3𝐢𝐟 ℎ(𝑙)−ℎ(𝑟)=24𝐢𝐟 ℎ(𝑙𝑠𝑙)≥ℎ(𝑟𝑠𝑙)5RightRotate(𝑝)6𝐞𝐥𝐬𝐞7LeftRotate(𝑙)8RightRotate(𝑝)9𝐞𝐥𝐬𝐞 𝐢𝐟 ℎ(𝑙)−ℎ(𝑟)=−210𝐢𝐟 ℎ(𝑙𝑠𝑟)≤ℎ(𝑟𝑠𝑟)11LeftRotate(𝑝)12𝐞𝐥𝐬𝐞13RightRotate(𝑟)14LeftRotate(𝑝)1function MaintainBalance(p)2l←lsp,r←rsp3if h(l)−h(r)=24if h(lsl)≥h(rsl)5RightRotate(p)6else7LeftRotate(l)8RightRotate(p)9else if h(l)−h(r)=−210if h(lsr)≤h(rsr)11LeftRotate(p)12else13RightRotate(r)14LeftRotate(p)

与其他平衡二叉搜索树相同，AVL 树中节点的高度、子树大小等信息需要在旋转时进行维护．

其他操作

AVL 树的其他操作（Predecessor、Successor、Select、Rank 等）与普通的二叉搜索树相同．

参考代码

下面的代码是用 AVL 树实现的 Map，即有序不可重映射：

参考代码

---|---

## 其他资料

在 [AVL Tree Visualization](https://www.cs.usfca.edu/~galles/visualization/AVLtree.html) 可以观察 AVL 树维护平衡的过程．

[维基百科 -- AVL 树](https://en.wikipedia.org/wiki/AVL_tree)

* * *

>  __本页面最近更新： 2026/1/7 10:15:08，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/avl.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/avl.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [Wajov](https://github.com/Wajov), [Enter-tainer](https://github.com/Enter-tainer), [Tiphereth-A](https://github.com/Tiphereth-A), [mgt](mailto:i@margatroid.xyz), [RIvance](https://github.com/RIvance), [5ab-juruo](https://github.com/5ab-juruo), [ChungZH](https://github.com/ChungZH), [diauweb](https://github.com/diauweb), [GoodCoder666](https://github.com/GoodCoder666), [Great-designer](https://github.com/Great-designer), [iamtwz](https://github.com/iamtwz), [jimgreen2013](https://github.com/jimgreen2013), [Tokur233](https://github.com/Tokur233), [Xeonacid](https://github.com/Xeonacid)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用