AVL树详解：从平衡因子到四种旋转，完整实现插入与删除

期末备考数据结构也好，面试被问到“讲一下AVL树”也罢，这个知识点几乎出现在每个计算机学习者的必经之路上。AVL树算是平衡二叉树里最经典、也最适合入门的一棵，它用一条很直观的约束——任何节点的左右子树高度差不超过1，把二叉搜索树从“可能退化成链表”的困境里拉回来，让查找、插入、删除的时间复杂度稳定在O(log n)。

说实话，AVL树的代码量不大，难点在于理解“为什么要旋转”和“怎么判断该转哪一种”。很多人死记LL、RR、LR、RL四种类型，画图练习时不错，一到自己手写就卡在递归实现和高度更新上。这篇文章从平衡因子的定义一路推到四种旋转的完整代码，再给出可复用的插入与删除实现，最后聊聊我实操中反复踩过的坑。无论你是期末复习、考研准备，还是面试前突击，看完这篇，应该能自己独立写出一个可用的AVL树。

1. 为什么需要AVL树：普通二叉搜索树的退化困境

1.1 一组有序数据就能让BST变成一条链表

先说清楚AVL树到底在解决什么。二叉搜索树（BST）有一个很美好的理想形态：每次插入都均匀落在左右两侧，树的深度大约是log2 N，查找一个元素最多比较log2 N次就够了，这也是大家常说BST查找是O(log n)的原因。

但注意，这个结论有一个隐藏前提：树必须是近似平衡的。只要插入顺序“不巧”，BST就会完全变样。比如我依次插入1、2、3、4、5，每一轮都把新节点放到当前树的最右位置，最后得到的树就是一条只有右孩子的“链表”，根本看不出树的形状。此时查找节点5要走5次比较，复杂度退化成O(n)。

问题出在哪？BST只对节点之间的大小关系做了约束，对树的“形态”完全没有限制。左边比根小、右边比根大这条规则保证了有序性，却没保证树是“矮胖”的还是“瘦高”的。真实业务中，数据分布往往不是随机均匀的，单调递增的ID、时间戳、排好序的批量数据都很常见，它们很容易把BST打退化。

1.2 AVL树的平衡约束与平衡因子

1962年，Adelson-Velsky和Landis提出了AVL树，核心思想是给每个节点加一个“健康指标”：平衡因子（balance factor）。定义不复杂，就是左子树高度减去右子树高度。AVL树强制要求每个节点的平衡因子只能是-1、0、1三者之一，一旦某个节点出现2或-2，就认为失衡，必须通过旋转把树“掰回”健康状态。

很多教材喜欢说“AVL树是高度平衡的二叉搜索树”，这句话的关键点是“高度”。有了这个约束，树的高度被控制在O(log n)级别，查找效率才真正稳下来。

使用平衡因子前需要注意一个约定：左减右，还是右减左。不同教材定义方向可能相反，代码里只要统一就行。我自己习惯左子树高度减右子树高度，后面的代码也按这个约定写。如果你按右减左实现，代码里旋转判断的正负号就要对称反过来，否则会踩大坑。

2. AVL树的高度分析：为什么它真的能把查询锁在O(log n)

2.1 高度与最少节点数的递推关系

学AVL树时绕不开一个问题：高度为h的AVL树，最少有多少个节点？这个推导是考研408和期末考试常见题型，背后藏着一个像斐波那契数列一样的递推式。

设N(h)是高度为h的AVL树的最少节点数。根节点先占去1个位置，为了让整棵树达到高度h，左右子树里较高的那棵至少是高度h-1；同时AVL要求左右子树高度差不超过1，所以较矮的那棵高度至少是h-2。于是：

N(h) = 1 + N(h-1) + N(h-2)

边界是 N(0) = 1（只有根节点），N(1) = 2（根加一个孩子）。这个递推式与斐波那契数列一致，解出来大约 N(h) ≈ F(h+2) - 1，而斐波那契数的通项增长很快，反过来由N推导h，可以得到高度上限约为 1.44 × log2(N + 2) - 1.33。

这个数字说明三件事：第一，AVL树的高度确实是对数量级；第二，它比完全平衡的理想二叉树（高度约log2 N）高一点点，大约高44%，但仍然是O(log n)；第三，就算数据带来的破坏力再强，AVL树最差也就比完美情况多一截，远好于退化成链表。

2.2 判定一棵树是不是AVL树的实操方法

考试里经常给一棵树，让你判断它是不是AVL树。很多人只看每个节点的左右子树高度，这当然没错，但容易漏掉“递归”两个字。

正确流程是：从根节点开始，先计算当前节点左右子树高度，检查差值绝对值是否小于等于1；然后分别对左孩子、右孩子递归执行相同检查。任何一个节点不过关，整棵树就不合格。空节点高度按0处理，单个节点高度按1处理，这个约定要固定住。

当你需要打印节点高度来验证代码正确性时，也会用到这套递归逻辑。后面调试章节我会专门写一个可视化打印函数，把节点高度和结构一起输出，对排查“假平衡”问题特别管用。

3. 四种旋转：AVL树的“正骨”手法

3.1 旋转的本质与右旋代码

旋转是AVL树最核心的操作，本质上做的事情可以用一句话概括：在不破坏中序有序性的前提下，改变局部子树的“根是谁”。BST的有序性是所有操作的命根子，旋转必须保持它。

看右旋。假设节点y是失衡点，它的左孩子是x，x的右孩子是T2。右旋后，x顶替y成为子树根，y变成x的右孩子，T2变成y的左孩子。

如果不好想象，用生活化的类比：y、x、T2像三个排队的人，原来y排在x前面，但x身高更高、位置也更重要，就让x站到y前面，中间那个T2往右挪一个位置。队还是那个队，只是站队顺序（指子树关系）换了。

private Node rightRotate(Node y) { Node x = y.left; Node t2 = x.right; x.right = y; y.left = t2; updateHeight(y); updateHeight(x); return x; }

注意代码里的顺序：先改引用，再更新高度。先更新y再更新x，因为旋转后y在x的下面，y的高度是x高度计算所需要的子信息。如果先更新x，y还没变，x的高度就算错了。

3.2 LL、RR、LR、RL四种情形怎么做

旋转按失衡类型分成四种，名字里的字母含义是“从哪条路径插入导致失衡”。LL表示在左孩子的左子树插入，RR表示在右孩子的右子树插入，LR表示在左孩子的右子树插入，RL表示在右孩子的左子树插入。

LL型对应右旋。失衡节点平衡因子为2，它的左孩子平衡因子为1，说明左边一路偏高，直接把根往右掰一下就好。

RR型对应左旋，和右旋完全对称，失衡节点平衡因子为-2，右孩子平衡因子为-1，执行一次左旋。

LR型比较麻烦。失衡节点平衡因子为2，但左孩子的平衡因子是-1，说明“左子树里长歪了”，不能直接右旋。直接右旋的话，原来那颗左孩子的右子树T2会接到失衡节点左边，但T2本身比左孩子更“右倾”，转完还是不平衡。正确做法是先对左孩子做一次左旋，把局部变成LL形态，再对失衡节点右旋。

// LR：先左旋左孩子，再右旋根 node.left = leftRotate(node.left); return rightRotate(node);

RL型是镜像对称：先右旋右孩子，再左旋根。

// RL：先右旋右孩子，再左旋根 node.right = rightRotate(node.right); return leftRotate(node);

3.3 判断旋转类型的实用口诀

判断口诀是我觉得比教科书更实用的记忆方式：同号单旋，异号双旋；哪边高，先从哪边动手。

具体说：拿到失衡节点，先看它的平衡因子。如果是正数（左高），再看左孩子的平衡因子。左孩子也是正数（同号），就是LL，单右旋；左孩子是负数（异号），就是LR，双旋。反过来，失衡节点为负数（右高），右孩子为负数（同号），就是RR，单左旋；右孩子为正数（异号），就是RL，双旋。

这个“同号异号”判断在代码里几乎可以照抄，因为平衡因子的符号直接反映“偏高方向”。“同号单旋”不只是记忆技巧，它背后有数学直觉：符号一致代表失衡路径是“笔直”的，一次旋转就能纠正；符号不一致代表路径拐了个弯，必须先在拐弯处校正方向，再做整体调整。

4. 完整实现：AVL树的插入和删除（Java版）

4.1 递归返回新根的设计模式

写AVL树之前要建立一套递归设计模式，而这个模式我在写红黑树、跳表时也常复用，思路是：所有修改树结构的递归方法，都不要试图原地修改后“什么都不返回”，而是返回以该节点为根的子树经过操作后的新根。

为什么？因为旋转会交换父子关系，原来的“根节点”可能不再是一棵子树的根。比如右旋后，传入的y已经不是新根了，真正的根x要被上层接收。所以插入和删除都必须写成return新的根，上层通过node.left = insert(node.left, val)这种方式做接缝。递归顺着往下走，返回值顺着往上接，结构才能无痛重组。

这个模式理解之后，插入删除的骨架就很清晰：

public class AvlTree { private Node root; private static class Node { int val; int height; Node left; Node right; Node(int val) { this.val = val; this.height = 1; } } private int height(Node n) { return n == null ? 0 : n.height; } private int balanceFactor(Node n) { return n == null ? 0 : height(n.left) - height(n.right); } private Node updateHeight(Node n) { n.height = Math.max(height(n.left), height(n.right)) + 1; return n; } }

两个需要注意的约定：空节点高度是0；单节点高度是1。这样父节点计算高度时不用做额外的“空指针判断”，因为height方法内部已经处理了null。

4.2 插入：先BST插入再回溯平衡

插入的完整逻辑是先按照BST规则把节点放到该放的位置，然后递归回溯时逐层更新高度、检查平衡，一旦发现失衡就按四种情况旋转。这段过程合在一起就是：

public void insert(int val) { root = insert(root, val); } private Node insert(Node node, int val) { if (node == null) { return new Node(val); } if (val < node.val) { node.left = insert(node.left, val); } else if (val > node.val) { node.right = insert(node.right, val); } else { return node; // 值已存在，不重复插入 } updateHeight(node); int bf = balanceFactor(node); // LL：左孩子的左子树插入 if (bf > 1 && balanceFactor(node.left) >= 0) { return rightRotate(node); } // LR：左孩子的右子树插入 if (bf > 1 && balanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } // RR：右孩子的右子树插入 if (bf < -1 && balanceFactor(node.right) <= 0) { return leftRotate(node); } // RL：右孩子的左子树插入 if (bf < -1 && balanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; }

这里的关键点是：updateHeight(node)必须先于平衡判断。如果先判断再更新高度，节点的高度是旧值，平衡因子算出来就不对。递归回到更上层时，上层节点的高度也要依赖孩子的最新高度，一层层回溯最终才能把整棵树的高度刷新。

第二个容易忽略的点是判断条件里不依赖插入值，而是看平衡因子的符号。判断LL和LR只看子树平衡因子是否大于等于0还是小于0，这套写法比用插入值判断更干净，而且可以原样复用到删除逻辑里。

4.3 删除：用后继替代后的多级平衡

删除比插入麻烦。插入最多做一次旋转（单旋或双旋）就能恢复平衡，因为新增节点只在一条路径上增加高度；删除却可能让高层节点失衡，旋转后失衡可能“传染”到更高的祖先，所以必须一路回溯到根，最坏情况要做O(log n)次旋转。

删除的步骤是：先按BST规则找到目标节点。如果目标节点只有一个孩子或没有孩子，直接用孩子替代；如果两个孩子都有，找右子树的最小节点（后继）覆盖当前节点值，然后递归删除那个后继节点。这部分和普通BST完全一致。

删除之后要回溯更新高度、检查平衡，因为删除发生在子树里，所有祖先的高度都可能变化。新的难点在于：删除路径上每个失衡节点都不只用“删除值”判断旋转类型，因为删除值已经消失在树里了。此时判断只能靠平衡因子本身，好在删除代码里本来就能直接看子树的balanceFactor。

public void delete(int val) { root = delete(root, val); } private Node delete(Node node, int val) { if (node == null) { return null; } if (val < node.val) { node.left = delete(node.left, val); } else if (val > node.val) { node.right = delete(node.right, val); } else { // 单孩子或叶子节点：直接返回孩子 if (node.left == null) return node.right; if (node.right == null) return node.left; // 双孩子：用右子树最小节点替换 Node successor = minNode(node.right); node.val = successor.val; node.right = delete(node.right, successor.val); } updateHeight(node); int bf = balanceFactor(node); if (bf > 1 && balanceFactor(node.left) >= 0) { return rightRotate(node); // LL } if (bf > 1 && balanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); // LR } if (bf < -1 && balanceFactor(node.right) <= 0) { return leftRotate(node); // RR } if (bf < -1 && balanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); // RL } return node; } private Node minNode(Node node) { while (node.left != null) { node = node.left; } return node; }

删除代码看起来和插入很像，但有两个本质区别。第一，插入代码里单旋条件用>= 0和<= 0，将平衡因子为0的情况归为单旋，这在删除场景是必要的；第二，删除过程中递归返回后，回溯路径上的每个节点都可能出现新的失衡，而不仅仅是最初那个。所以不要有“删除一次旋转就完事”的错觉，让递归沿着路径把所有节点都扫一遍。

4.4 代码中容易忽略的顺序问题

写这段代码时，我踩过的最深的一个坑是高度更新顺序。不只递归回溯时要先updateHeight再判断平衡，旋转函数内部也得按正确顺序更新。

右旋函数内部，y先往下变矮，x变高，所以必须先更新y的height，再更新x的height。如果反过来，x的height会用到y的旧值，最终整棵树的高度信息全错。这种错误比较隐蔽，因为代码逻辑“看起来没问题”，只有后面插入新节点时平衡因子偶尔算错，才知道埋了雷。

另一个顺序问题是删除时先替换值还是先递归删除。必须先替换当前节点的值为后继值，再删除右子树里的后继。原因很简单，后继节点一旦被删除，它的值就丢了，你拿什么覆盖当前节点？这个顺序反了会直接报空指针或得到错误值。

5. 性能对比与应用场景：为什么现实中更多用红黑树

5.1 BST、AVL、红黑树复杂度对比

学到这里，很多人会问：既然AVL树这么好，为什么Java的TreeMap底层用的是红黑树，而不是AVL树？答案藏在“旋转的成本”里。

AVL树平衡要求更严，树更矮，查找性能略好；但为了维持严格平衡，插入和删除时做旋转的频率更高、需要回溯的层数更深。红黑树放开了平衡条件，只要求从根到叶子的所有路径上黑色节点数相同，最长路径不超过最短路径的两倍。虽然红黑树高度上限比AVL树略高，但它插入删除时的调整次数少且更局部化，写操作多的场景综合效率更高。

5.2 读多写少的场景选AVL，读写均衡选红黑树

选型时我一般按这个思路判断：如果系统是读密集型的，比如缓存索引、查找表，数据量大、更新少，AVL树值得优先考虑，因为更矮的树意味着更少的比较次数。如果系统是读写均衡甚至写密集型的，比如通用的有序集合、调度任务队列，红黑树在结构稳定性上更省事。

不过这是理论上的比较。实际工程里你很少需要自己实现AVL树，因为绝大多数编程语言的标准库都已经提供了基于红黑树的有序集合：Java的TreeMap、TreeSet，C++的std::map、std::set。在这些成熟组件面前，“自己手写一棵AVL树”的性价比很低，学习价值远大于生产价值。

5.3 AVL树在哪些实际系统里出现

抛开标准库，AVL树仍然有它的一席之地。比较经典的场景有几类：一是在某些内存数据库或键值存储引擎里，数据全部驻留内存，AVL树比B树更合适；二是需要按序迭代又要求查找极快的自定义索引结构，比如游戏开发中的单位管理、排行榜；三是在算法竞赛和高性能算法库中，AVL树常被当作“基准平衡树”来验证其他数据结构。

更重要的是学习意义。AVL树把“自平衡二叉树”的整套概念压缩在了最小的代码量里。理解AVL树之后，再看红黑树的颜色翻转、Splay树的伸展旋转、Treap的随机优先级，都会觉得顺理成章。AVL树是理解整个平衡树家族的垫脚石。

6. 实操中的高频问题和调试技巧

6.1 忘记更新高度导致的“假平衡”

搜索资料时会看到“假平衡”这个词，翻译成大白话就是：每个节点的平衡因子看起来都在允许范围内，但树内部的高度信息已经错误，旋转判断全部跟着乱套。最常见的原因是递归回溯时只做了旋转，没更新高度；或者旋转内部更新顺序反了。

这类bug的特征很典型：插入一两轮正常，第三轮突然出现一个节点的平衡因子是3或-3，远超2。你检查代码逻辑，二叉搜索树的插入部分没错，旋转也没写错，就是树的高度数据不匹配。解决办法是给每个节点维护height字段，在每次递归返回前强制执行updateHeight(node)，并且旋转函数内部严格按从下到上的顺序更新。

6.2 LR/RR容易混淆，怎么稳定判断

LR和RR是初学者最容易混淆的一组。记不住的原因在于两种情况的插入路径完全不同，但失衡节点都是左高或者右高。我自己的稳定判断方法分三步走：先看失衡节点的平衡因子符号，确定“左高”还是“右高”；然后只看它的哪个孩子更高；最后看这个孩子的孩子的平衡因子符号，同号单旋，异号双旋。

举个例子。一个节点的平衡因子是2，说明左子树高。如果它的左孩子平衡因子是1，说明左孩子的左子树高，路径一路朝左，就是LL，直接右旋。如果左孩子平衡因子是-1，说明左孩子的右子树高，路径在左孩子这里拐了个弯，就是LR，先左旋左孩子，再右旋根。

这个方法比背“LL是左左，RR是右右”不容易错，因为它不依赖记忆，而是从平衡因子的符号自然推导。多练几组插入序列，比如10、20、30、40这种递增序列和随机序列，很快就能形成肌肉记忆。

6.3 删除路径上一路校验才是关键

删除操作最容易犯的错误是：找到目标节点，调整好局部平衡就认为结束了，没有对父节点、祖父节点一路校验。前面说过，删除会让祖先子树高度减小，从而引发更高层的失衡，这种失衡比插入引发的问题更隐蔽、更容易漏。

实际上我写过的最稳的删除实现，就是让递归删除步骤返回新根后，插入的平衡检查逻辑原样复用。删除里不需要额外写一整套旋转判断，直接拷段检查代码，把每次递归返回后都跑一遍，问题就自动解决了。注意删除场景下单旋条件要包含平衡因子为0的情况（>= 0和<= 0），这是由AVL删除的数学性质决定的，换了条件会破坏删除后树的平衡结构。

6.4 给树写个缩进打印，胜过一千行断点

调试AVL树最大的痛点是看不到结构。断点只能告诉你某个节点的值，不能告诉你树的形状。我强烈建议手写一个简单的缩进树形打印函数，把每个节点的值和高度一起输出。

public void printTree() { printTree(root, "", true); } private void printTree(Node node, String prefix, boolean isRight) { if (node == null) return; System.out.println(prefix + (isRight ? "R:" : "L:") + node.val + "(h=" + node.height + ")"); printTree(node.left, prefix + " ", false); printTree(node.right, prefix + " ", true); }

输出结果形如：

L:10(h=2) L:5(h=1) R:8(h=1)

这种输出能一眼看出左右子树是否均衡、每个节点的height是否正确。每插入或删除一次就打印一次，多试几组数据，旋转的正确性很快就能验证出来。比在调试器里一个个查看对象引用高效太多。

6.5 学习路线建议和后续进阶方向

如果你正在学数据结构，我的建议是先不要一上来就写完整AVL树。先把普通BST的插入、删除、查找写好，确保二叉树递归基本功扎实；然后单独写右旋和左旋两个函数，用几个手工构造的失衡树验证；最后把插入逻辑和旋转接起来，平衡判断用前面说的“同号单旋、异号双旋”口诀。

AVL树真正难的不是代码量，而是你对递归和平衡两个概念的肌肉记忆。一旦你亲手调通过一组插入、一组删除，后面再看红黑树、B树、跳跃表都会轻松很多。我个人当时做完AVL树后，又顺着去看了红黑树的插入调整逻辑，突然发现自己在颜色翻转和叔叔节点检查里看到的，其实和AVL是同一套“维护平衡”的思路，只不过用的是另一套度量标准而已。

最后再分享一个应试小技巧：手写AVL树时，代码只要跑通插入删除，就不用太纠结面试官会不会被冗长代码吓住。面试官真正想看的是你对平衡因子的理解、旋转时机的判断、以及代码的可读性。把这些讲清楚，比背下完整实现更有说服力。