AVL树这名字很多人在面试前背了无数遍LL 转 RR、LR 先左后右可真到让你手写一遍或者遇到删除后连失衡形态都认不出来的情况就露馅了。我今天就把 AVL 树从失衡到平衡的完整链路捋一遍重点放在四种旋转机制上——为什么这么转、什么时候转、转了之后平衡因子怎么更新全部用代码和具体例子说话。这篇适合正在复习数据结构的同学、准备手撕算法面试的开发者以及那些写了平衡树但总在边界条件上报错的人。看完你会明白旋转机制本质上只是“换个根节点”的小把戏并不神秘。1. 先搞懂AVL树到底在解决什么问题1.1 二叉搜索树的退化危机普通的二叉搜索树BST有个经典问题如果插入顺序恰好是升序或降序树会退化成一条链表。我举个例子连续插入 1、2、3、4、5二叉搜索树的形态会变成只有右孩子的“斜树”——查找 1 要一路走到最左下角查找 5 也要 O(n) 时间明明是个树结构却干出了链表的活。之所以会退化是因为普通 BST 只保证“左小右大”这个局部约束完全不管整棵树的高度是否可控。这时候 AVL 树出现了它的核心约束只有一个任何节点的左右子树高度差不超过 1。一旦插入或删除导致某个节点失衡就立即通过旋转把树重新“扶正”。这样带来的收益非常实际一棵 n 个节点的 AVL 树高度严格控制在 O(log n)精确点说大概 1.44 log2(n)查找、插入、删除的时间复杂度就稳定在 O(log n)。代价是每次变更结构后要做额外的平衡维护但这个代价换来了可预期的性能上限对搜索密集型场景非常值。1.2 平衡因子的定义与计算方法要判断一个节点是否失衡先得定义“高度”和“平衡因子”。我习惯把空节点高度记为 0叶子节点高度记为 1。一个节点的平衡因子Balance FactorBF定义为 左子树高度减去右子树高度也就是 BF(node) height(left) - height(right)。这个值只有三种合法状态-1、0、1。一旦某个节点的 BF 是 2 或 -2就说明它失衡了必须触发旋转。这里有个容易搞混的细节AVL 的平衡因子有的教材写成“右减左”有的写成“左减右”本身没有对错但会直接影响代码里判断方向的写法。我建议你固定使用“左减右”因为这样和“LL 失衡对应 BF2”“RR 失衡对应 BF-2”的记忆方式是一致的。写代码时只要保证计算函数和旋转判断逻辑配套就行别把两种习惯混着用否则你会看到一堆莫名其妙的符号错误。1.3 失衡的四种基本形态失衡不是随机的它一定发生在某个子树上根据插入点在失衡节点左子树还是右子树以及更下一层的情况可以分成四种。命名方式看的是“路径方向”不是节点数LL 表示新节点插到了失衡节点的左孩子的左子树RR 表示插到了右孩子的右子树LR 表示插到了左孩子的右子树RL 表示插到了右孩子的左子树。这四种失衡和旋转方案的对应关系是LL 用右旋RR 用左旋LR 先左旋左孩子再右旋根RL 先右旋右孩子再左旋根。记住这张对应表后面实现就很清晰。但你光记住“LL 转右”还不够得搞清楚“右旋时到底哪些节点换位置了”这才是手撕代码的关键。2. 旋转机制的本质为什么是这四个操作2.1 LL失衡与右旋左孩子上位我用一个例子走一遍。假设现有节点 30、20插入 10 后30 的左子树高度是 220 下面还有 10右子树高度是 0BF2失衡且形态为 LL。这时候对 30 做右旋把 20 提上来当新子树的根30 挂到 20 的右孩子原来 20 的右孩子如果有变成 30 的左孩子。为什么这样转一下就平衡了核心在于旋转不改变中序遍历顺序。旋转前中序是 10、20、30旋转后中序还是 10、20、30它只改变了树的结构没有破坏 BST 的“左小右大”约定。所有旋转都是如此这是旋转“合法”的根本原因。操作细节上右旋时拿到失衡节点的左孩子作为新根再把新根的右子树“腾出来”挂到失衡节点的左侧这个“腾出来的子树”在代码里通常叫 T2 或 temp。2.2 RR失衡与左旋右孩子上位RR 和 LL 是对称的。比如现有 10、20插入 30此时失衡节点是 10BF-2。对 10 做左旋把 20 提为根10 挂到 20 左孩子20 原来的左孩子变成 10 的右孩子。中序遍历在旋转前后都是 10、20、30。这两个单旋其实不需要死记理解“谁被提上来了、谁被挤下去了”就行右旋是左孩子上位左旋是右孩子上位。“上位”的节点会占据原根的位置原根则变成它的某一侧孩子而被顶掉的那个子树会落到原根身上。这么想任何单旋你都能推出来。2.3 LR失衡先左旋孩子再右旋根LR 的情况比单旋麻烦失衡节点为 30它的左孩子 10 的右子树插入了新节点 20。直接右旋 30 有用吗没用。因为此时 30 的左孩子10的右子树很高直接右旋会把 20 这个子树转到 30 的左孩子位置整体依然不平衡。正确做法是分两步先对失衡节点的左孩子 10 做左旋把 20 从“左孩子的右子树”翻到“左孩子的左子树”整体结构就从 LR 变成了 LL再对失衡节点 30 做右旋。这就是“先左旋孩子再右旋根”的由来。实际操作时你可以直接封装一个 rotate_left_right(node) 函数里面调用两次单旋先 rotate_left(node.left)再把返回值赋给 node.left最后 rotate_right(node)。2.4 RL失衡先右旋孩子再左旋根RL 与 LR 对称失衡节点为 10右孩子 30 的左子树插入了 20。处理方式是先对 30 做右旋把它变成 RR 形态再对 10 做左旋。为了方便记忆你可以用个小口诀LR 是“先左后右”RL 是“先右后左”第一步永远是把双旋变成单旋。到这里我用一张表把四种形态和旋转方案放一起方便你对照着写代码失衡形态平衡因子特征左减右处理方式旋转后子树根LLBF(node) 1且 BF(node.left) 0直接右旋 node原 node.leftLRBF(node) 1且 BF(node.left) 0先左旋 node.left再右旋 node原 node.leftRRBF(node) -1且 BF(node.right) 0直接左旋 node原 node.rightRLBF(node) -1且 BF(node.right) 0先右旋 node.right再左旋 node原 node.right注意这里的“BF(node.left) 0”是删除场景下更严谨的写法后面第 4 节会细说。如果你用的是“右减左”约定整张表的符号全部取反。3. 从零手写AVL树插入与旋转的代码实现3.1 节点结构与基础工具方法我用 Python 写因为表达最直观逻辑完全可以迁到 C、Java、Go。节点结构包含 key、left、right、height。height 存的是“以该节点为根的子树高度”叶子节点高度为 1空节点高度为 0。这和你平常用的“深度”不是一回事别混。基础工具方法我通常写三个必须配套出现def get_height(node): if node is None: return 0 return node.height def update_height(node): if node is not None: node.height 1 max(get_height(node.left), get_height(node.right)) def get_balance(node): if node is None: return 0 return get_height(node.left) - get_height(node.right)get_balance 里一定要判空因为递归过程中会频繁对空子树调用不判空直接访问 node.height 就会崩。update_height 里我顺手也判了空虽然正规调用不会传 None但防御性写法能省掉不少调试时间。3.2 四种旋转的代码实现单旋代码是 AVL 树的“原子操作”我建议背下来但不能死背要理解每个指针为什么这么指。右旋以 y 节点为失衡节点它的左孩子是 xx 的右孩子叫 T2。旋转后 x 上位y 变成 x 的右孩子T2 变成 y 的左孩子。左旋完全对称。def rotate_right(y): x y.left T2 x.right x.right y # x 上位y 落到右侧 y.left T2 # T2 顶替原来 y 的左孩子 update_height(y) update_height(x) return x def rotate_left(x): y x.right T2 y.left y.left x # y 上位x 落到左侧 x.right T2 # T2 顶替原来 x 的右孩子 update_height(x) update_height(y) return y有个极其容易踩的坑旋转后更新高度的顺序。右旋里y 先变成了 x 的孩子所以必须先 update_height(y)再 update_height(x)。如果反过来先更新 x后更新 yx 的高度用到的还是 y 旋转前的高度算出来的值就是错的。这个顺序问题我在网上见过不少人问其实道理很简单谁在下面谁先更新因为它会影响上面的计算。3.3 插入后的再平衡递归回溯的魅力插入逻辑用的是递归因为递归天然具备“从插入点一路回溯到根”的能力。先看完整代码def rebalance(node): update_height(node) balance get_balance(node) if balance 1: if get_balance(node.left) 0: node.left rotate_left(node.left) return rotate_right(node) if balance -1: if get_balance(node.right) 0: node.right rotate_right(node.right) return rotate_left(node) return node def insert(node, key): if node is None: return AVLNode(key) if key node.key: node.left insert(node.left, key) elif key node.key: node.right insert(node.right, key) else: return node return rebalance(node)我用了统一的 rebalance 函数而不是在 insert 里判断四种形态。为什么这么设计因为 rebalance 只看当前节点的平衡因子和左右孩子平衡因子的关系不需要知道“新插入的 key 跑到了哪个方向”所以插入、删除都能复用代码量反而更少。insert 每递归返回一层就调用一次 rebalance这样整个路径上所有失衡节点都会被修正。另外有些教材的插入实现会用if balance 1 and key node.left.key来判断 LLif balance 1 and key node.left.key判断 LR。这在插入场景是对的因为 key 的方向代表新节点的去向。但删除场景下没有新 key 可用所以我还是推荐用 rebalance 这种纯看平衡因子的统一写法一套逻辑走天下。3.4 高度更新时机谁先变成孩子谁先更新很多人写的 AVL 树“时好时坏”根源往往就是高度更新时机不对。记住一条原则递归返回前每一层都要 update_height旋转内部谁先变成别人的孩子谁先更新。具体来说insert 里递归压栈回来第一件事是 rebalancerebalance 第一步就是 update_height(node)。旋转内部右旋先更新 y 再更新 x左旋先更新 x 再更新 y。双旋就是调用两次单旋高度更新自然被两次单旋内部处理掉了不需要额外再更新一次。你可能会问为什么插入后只回溯一遍就行因为 AVL 树的旋转有一个特性插入引起的失衡在第一次旋转后会使得该子树的高度恢复成插入前的高度所以上层的平衡因子不会再变化。这也是“插入最多一次旋转或双旋”这句话的由来。不过删除不一样删除后的失衡可能向上传播多级这个我们放到下一节说。4. 删除操作比插入更隐蔽的失衡4.1 删除的三种基本情况删除逻辑首先要解决“节点怎么删”再解决“删完怎么平衡”。和普通 BST 一样分三种情况叶子节点直接返回 None让父节点的孩子指针指向空即可。只有一个孩子把孩子顶上来返回孩子节点。有两个孩子用中序后继右子树的最小节点或前驱替换当前节点的值然后递归删除那个后继节点。我习惯用中序后继因为它在右子树最左下角删除它符合“叶子或只有一个孩子”的简单场景。def min_value_node(node): while node.left is not None: node node.left return node def delete(node, key): if node is None: return None if key node.key: node.left delete(node.left, key) elif key node.key: node.right delete(node.right, key) else: if node.left is None: return node.right if node.right is None: return node.left successor min_value_node(node.right) node.key successor.key node.right delete(node.right, successor.key) return rebalance(node)这里有个细节找到后继后不是直接断开后继节点而是把后继的 key 复制到当前节点再递归删除右子树里的那个后继。这么做的好处是删除操作始终发生在叶子附近不会出现“删一个中间节点导致指针混乱”的麻烦。4.2 删除后不能再用 key 判断形态删除后的 rebalance 和插入有很大的不同插入时我们知道新 key 是从哪条路径插进去的所以可以用key node.left.key判断方向删除时当前子树高度下降可能来自左子树也可能来自右子树而且没有任何新 key 可以参考所以必须靠节点自身的平衡因子以及左右孩子的平衡因子来判断。判断逻辑就是我前面 rebalance 函数里写的那两条当前节点 BF 1说明左子树高。如果左孩子的 BF 0说明是 LR 型先左旋左孩子否则是 LL 型直接右旋。当前节点 BF -1说明右子树高。如果右孩子的 BF 0说明是 RL 型先右旋右孩子否则是 RR 型直接左旋。注意这里对 LL 型而言判断条件是get_balance(node.left) 0。很多教材在删除场景写 0其实 0的情况在删除时也会出现此时直接右旋同样合法且效果正确。这也是用统一 rebalance 的好处之一不容易漏边界。4.3 删除的连锁失衡可能一路旋到根插入时旋转一次就能让整棵子树恢复原高但删除不是这样。删除可能导致某个子树高度减 1第一次旋转只修复了局部子树的平衡却可能让往上几层的节点从“没失衡”变成“失衡”。所以删除必须从递归返回路径上每一层都执行 rebalance一路检查到根节点为止。举个例子你删掉一棵很深平衡树的某个叶子这棵树最下层的失衡被一次旋转修复了但修复后它所在子树的高度又减了 1导致它的父节点失衡于是父节点也要转。如果父节点转完它所在子树的高度又变了爷爷节点也要跟着处理。正因为如此删除的 rebalance 调用不能像插入那样“大概率只转一次”而是要老老实实让每一层递归都执行一次完整判断。你只要保证每层都return rebalance(node)这个问题就被递归天然解决了。5. 常见问题与排查技巧实录5.1 旋转后平衡因子更新错位症状插入后树还是不平衡甚至出现“转完更歪了”的情况。原因 99% 是旋转内部高度更新顺序写反了。我见过有人把右旋写成# 错误示范 def rotate_right(y): x y.left T2 x.right x.right y y.left T2 update_height(x) update_height(y) return x表面看只是两行顺序调换但 x 的高度更新时y 还是旧的左孩子关系旋转已发生但 y 的高度没变算出来的 x.height 就比实际小或大。调试方法很简单在 get_balance 前后打印 node.key 和左右子树高度对比旋转前中后的值是不是符合预期。5.2 递归回溯时节点高度没更新症状插入后只有局部子树平衡了往上两层还是失衡甚至 root 的平衡因子始终不对。这种问题的根源往往不是旋转本身而是递归函数的返回路径上少了更新高度的步骤。有些人写的 insert只有走到 None 新建节点时设置高度回到中间节点时只做旋转判断忘了在返回前调 update_height。结果就是新节点插入后它的父节点、祖父节点的 height 全是旧值平衡因子自然算错。正确做法是像我的 rebalance 函数那样进入函数第一步就 update_height不管当前节点需不需要旋转高度都要先刷新。5.3 测试用例怎么覆盖四种旋转想确认自己的 AVL 实现正确最直接的方法是构造四个最小失衡场景分别验证四种旋转。给你一套我常用的插入序列构造 LL依次插入 30、20、10。插入 10 后30 的左子树高度为 2右子树为 0触发右旋。构造 RR依次插入 10、20、30。对称地触发左旋。构造 LR依次插入 30、10、20。插入 20 后30 的左孩子 10 的右子树高了先左旋 10 再右旋 30。构造 RL依次插入 10、30、20。先右旋 30 再左旋 10。验证方式我强烈建议写一个递归断言函数def assert_avl(node): if node is None: return True if abs(get_balance(node)) 1: raise AssertionError(fnode {node.key} unbalanced, bf{get_balance(node)}) assert_avl(node.left) assert_avl(node.right)再配合中序遍历必须是升序这个 BST 性质双重检查。每次插入后都调用 assert_avl基本能保证旋转写对了。5.4 画图调试比日志更有效我个人练 AVL 树最受益的习惯不是打日志而是写一个简短的括号表示法打印函数把树结构直接打印出来。例如一个平衡的树打印成(20(10,30))一看就知道树的形状。你也可以用层序遍历打印配合缩进看左右结构。调试旋转时我通常是手工构造上面那四个用例然后看打印结果是不是和预期形态一致。最后一个经验插入练熟后一定要把删除也测试到位。很多人只测插入导致 delete 里的 rebalance 从来没被触发过面试真让手撕删除时就露馅。我建议你准备一组较长的随机序列比如插入 1 到 100 的乱序再按随机顺序删除其中一半每步都跑 assert_avl。跑通之后你对“连锁失衡”的理解会扎实很多。AVL 树这个东西第一次写总觉得繁琐但你把旋转的指针变化画清楚、把统一 rebalance 的套路固定下来之后它就是一套非常机械的流程。以后再看到红黑树、跳表那些“近似平衡”的结构你也能立刻意识到它们为什么愿意放宽“高度差不超过 1”这个条件——毕竟保持严格平衡的维护成本在真实场景里有时候比收益还高。能完全搞懂 AVL 的人再去理解其他平衡结构基本就是降维打击。 AVL树详解：四种旋转机制、平衡因子更新与代码实现
AVL树这名字很多人在面试前背了无数遍LL 转 RR、LR 先左后右可真到让你手写一遍或者遇到删除后连失衡形态都认不出来的情况就露馅了。我今天就把 AVL 树从失衡到平衡的完整链路捋一遍重点放在四种旋转机制上——为什么这么转、什么时候转、转了之后平衡因子怎么更新全部用代码和具体例子说话。这篇适合正在复习数据结构的同学、准备手撕算法面试的开发者以及那些写了平衡树但总在边界条件上报错的人。看完你会明白旋转机制本质上只是“换个根节点”的小把戏并不神秘。1. 先搞懂AVL树到底在解决什么问题1.1 二叉搜索树的退化危机普通的二叉搜索树BST有个经典问题如果插入顺序恰好是升序或降序树会退化成一条链表。我举个例子连续插入 1、2、3、4、5二叉搜索树的形态会变成只有右孩子的“斜树”——查找 1 要一路走到最左下角查找 5 也要 O(n) 时间明明是个树结构却干出了链表的活。之所以会退化是因为普通 BST 只保证“左小右大”这个局部约束完全不管整棵树的高度是否可控。这时候 AVL 树出现了它的核心约束只有一个任何节点的左右子树高度差不超过 1。一旦插入或删除导致某个节点失衡就立即通过旋转把树重新“扶正”。这样带来的收益非常实际一棵 n 个节点的 AVL 树高度严格控制在 O(log n)精确点说大概 1.44 log2(n)查找、插入、删除的时间复杂度就稳定在 O(log n)。代价是每次变更结构后要做额外的平衡维护但这个代价换来了可预期的性能上限对搜索密集型场景非常值。1.2 平衡因子的定义与计算方法要判断一个节点是否失衡先得定义“高度”和“平衡因子”。我习惯把空节点高度记为 0叶子节点高度记为 1。一个节点的平衡因子Balance FactorBF定义为 左子树高度减去右子树高度也就是 BF(node) height(left) - height(right)。这个值只有三种合法状态-1、0、1。一旦某个节点的 BF 是 2 或 -2就说明它失衡了必须触发旋转。这里有个容易搞混的细节AVL 的平衡因子有的教材写成“右减左”有的写成“左减右”本身没有对错但会直接影响代码里判断方向的写法。我建议你固定使用“左减右”因为这样和“LL 失衡对应 BF2”“RR 失衡对应 BF-2”的记忆方式是一致的。写代码时只要保证计算函数和旋转判断逻辑配套就行别把两种习惯混着用否则你会看到一堆莫名其妙的符号错误。1.3 失衡的四种基本形态失衡不是随机的它一定发生在某个子树上根据插入点在失衡节点左子树还是右子树以及更下一层的情况可以分成四种。命名方式看的是“路径方向”不是节点数LL 表示新节点插到了失衡节点的左孩子的左子树RR 表示插到了右孩子的右子树LR 表示插到了左孩子的右子树RL 表示插到了右孩子的左子树。这四种失衡和旋转方案的对应关系是LL 用右旋RR 用左旋LR 先左旋左孩子再右旋根RL 先右旋右孩子再左旋根。记住这张对应表后面实现就很清晰。但你光记住“LL 转右”还不够得搞清楚“右旋时到底哪些节点换位置了”这才是手撕代码的关键。2. 旋转机制的本质为什么是这四个操作2.1 LL失衡与右旋左孩子上位我用一个例子走一遍。假设现有节点 30、20插入 10 后30 的左子树高度是 220 下面还有 10右子树高度是 0BF2失衡且形态为 LL。这时候对 30 做右旋把 20 提上来当新子树的根30 挂到 20 的右孩子原来 20 的右孩子如果有变成 30 的左孩子。为什么这样转一下就平衡了核心在于旋转不改变中序遍历顺序。旋转前中序是 10、20、30旋转后中序还是 10、20、30它只改变了树的结构没有破坏 BST 的“左小右大”约定。所有旋转都是如此这是旋转“合法”的根本原因。操作细节上右旋时拿到失衡节点的左孩子作为新根再把新根的右子树“腾出来”挂到失衡节点的左侧这个“腾出来的子树”在代码里通常叫 T2 或 temp。2.2 RR失衡与左旋右孩子上位RR 和 LL 是对称的。比如现有 10、20插入 30此时失衡节点是 10BF-2。对 10 做左旋把 20 提为根10 挂到 20 左孩子20 原来的左孩子变成 10 的右孩子。中序遍历在旋转前后都是 10、20、30。这两个单旋其实不需要死记理解“谁被提上来了、谁被挤下去了”就行右旋是左孩子上位左旋是右孩子上位。“上位”的节点会占据原根的位置原根则变成它的某一侧孩子而被顶掉的那个子树会落到原根身上。这么想任何单旋你都能推出来。2.3 LR失衡先左旋孩子再右旋根LR 的情况比单旋麻烦失衡节点为 30它的左孩子 10 的右子树插入了新节点 20。直接右旋 30 有用吗没用。因为此时 30 的左孩子10的右子树很高直接右旋会把 20 这个子树转到 30 的左孩子位置整体依然不平衡。正确做法是分两步先对失衡节点的左孩子 10 做左旋把 20 从“左孩子的右子树”翻到“左孩子的左子树”整体结构就从 LR 变成了 LL再对失衡节点 30 做右旋。这就是“先左旋孩子再右旋根”的由来。实际操作时你可以直接封装一个 rotate_left_right(node) 函数里面调用两次单旋先 rotate_left(node.left)再把返回值赋给 node.left最后 rotate_right(node)。2.4 RL失衡先右旋孩子再左旋根RL 与 LR 对称失衡节点为 10右孩子 30 的左子树插入了 20。处理方式是先对 30 做右旋把它变成 RR 形态再对 10 做左旋。为了方便记忆你可以用个小口诀LR 是“先左后右”RL 是“先右后左”第一步永远是把双旋变成单旋。到这里我用一张表把四种形态和旋转方案放一起方便你对照着写代码失衡形态平衡因子特征左减右处理方式旋转后子树根LLBF(node) 1且 BF(node.left) 0直接右旋 node原 node.leftLRBF(node) 1且 BF(node.left) 0先左旋 node.left再右旋 node原 node.leftRRBF(node) -1且 BF(node.right) 0直接左旋 node原 node.rightRLBF(node) -1且 BF(node.right) 0先右旋 node.right再左旋 node原 node.right注意这里的“BF(node.left) 0”是删除场景下更严谨的写法后面第 4 节会细说。如果你用的是“右减左”约定整张表的符号全部取反。3. 从零手写AVL树插入与旋转的代码实现3.1 节点结构与基础工具方法我用 Python 写因为表达最直观逻辑完全可以迁到 C、Java、Go。节点结构包含 key、left、right、height。height 存的是“以该节点为根的子树高度”叶子节点高度为 1空节点高度为 0。这和你平常用的“深度”不是一回事别混。基础工具方法我通常写三个必须配套出现def get_height(node): if node is None: return 0 return node.height def update_height(node): if node is not None: node.height 1 max(get_height(node.left), get_height(node.right)) def get_balance(node): if node is None: return 0 return get_height(node.left) - get_height(node.right)get_balance 里一定要判空因为递归过程中会频繁对空子树调用不判空直接访问 node.height 就会崩。update_height 里我顺手也判了空虽然正规调用不会传 None但防御性写法能省掉不少调试时间。3.2 四种旋转的代码实现单旋代码是 AVL 树的“原子操作”我建议背下来但不能死背要理解每个指针为什么这么指。右旋以 y 节点为失衡节点它的左孩子是 xx 的右孩子叫 T2。旋转后 x 上位y 变成 x 的右孩子T2 变成 y 的左孩子。左旋完全对称。def rotate_right(y): x y.left T2 x.right x.right y # x 上位y 落到右侧 y.left T2 # T2 顶替原来 y 的左孩子 update_height(y) update_height(x) return x def rotate_left(x): y x.right T2 y.left y.left x # y 上位x 落到左侧 x.right T2 # T2 顶替原来 x 的右孩子 update_height(x) update_height(y) return y有个极其容易踩的坑旋转后更新高度的顺序。右旋里y 先变成了 x 的孩子所以必须先 update_height(y)再 update_height(x)。如果反过来先更新 x后更新 yx 的高度用到的还是 y 旋转前的高度算出来的值就是错的。这个顺序问题我在网上见过不少人问其实道理很简单谁在下面谁先更新因为它会影响上面的计算。3.3 插入后的再平衡递归回溯的魅力插入逻辑用的是递归因为递归天然具备“从插入点一路回溯到根”的能力。先看完整代码def rebalance(node): update_height(node) balance get_balance(node) if balance 1: if get_balance(node.left) 0: node.left rotate_left(node.left) return rotate_right(node) if balance -1: if get_balance(node.right) 0: node.right rotate_right(node.right) return rotate_left(node) return node def insert(node, key): if node is None: return AVLNode(key) if key node.key: node.left insert(node.left, key) elif key node.key: node.right insert(node.right, key) else: return node return rebalance(node)我用了统一的 rebalance 函数而不是在 insert 里判断四种形态。为什么这么设计因为 rebalance 只看当前节点的平衡因子和左右孩子平衡因子的关系不需要知道“新插入的 key 跑到了哪个方向”所以插入、删除都能复用代码量反而更少。insert 每递归返回一层就调用一次 rebalance这样整个路径上所有失衡节点都会被修正。另外有些教材的插入实现会用if balance 1 and key node.left.key来判断 LLif balance 1 and key node.left.key判断 LR。这在插入场景是对的因为 key 的方向代表新节点的去向。但删除场景下没有新 key 可用所以我还是推荐用 rebalance 这种纯看平衡因子的统一写法一套逻辑走天下。3.4 高度更新时机谁先变成孩子谁先更新很多人写的 AVL 树“时好时坏”根源往往就是高度更新时机不对。记住一条原则递归返回前每一层都要 update_height旋转内部谁先变成别人的孩子谁先更新。具体来说insert 里递归压栈回来第一件事是 rebalancerebalance 第一步就是 update_height(node)。旋转内部右旋先更新 y 再更新 x左旋先更新 x 再更新 y。双旋就是调用两次单旋高度更新自然被两次单旋内部处理掉了不需要额外再更新一次。你可能会问为什么插入后只回溯一遍就行因为 AVL 树的旋转有一个特性插入引起的失衡在第一次旋转后会使得该子树的高度恢复成插入前的高度所以上层的平衡因子不会再变化。这也是“插入最多一次旋转或双旋”这句话的由来。不过删除不一样删除后的失衡可能向上传播多级这个我们放到下一节说。4. 删除操作比插入更隐蔽的失衡4.1 删除的三种基本情况删除逻辑首先要解决“节点怎么删”再解决“删完怎么平衡”。和普通 BST 一样分三种情况叶子节点直接返回 None让父节点的孩子指针指向空即可。只有一个孩子把孩子顶上来返回孩子节点。有两个孩子用中序后继右子树的最小节点或前驱替换当前节点的值然后递归删除那个后继节点。我习惯用中序后继因为它在右子树最左下角删除它符合“叶子或只有一个孩子”的简单场景。def min_value_node(node): while node.left is not None: node node.left return node def delete(node, key): if node is None: return None if key node.key: node.left delete(node.left, key) elif key node.key: node.right delete(node.right, key) else: if node.left is None: return node.right if node.right is None: return node.left successor min_value_node(node.right) node.key successor.key node.right delete(node.right, successor.key) return rebalance(node)这里有个细节找到后继后不是直接断开后继节点而是把后继的 key 复制到当前节点再递归删除右子树里的那个后继。这么做的好处是删除操作始终发生在叶子附近不会出现“删一个中间节点导致指针混乱”的麻烦。4.2 删除后不能再用 key 判断形态删除后的 rebalance 和插入有很大的不同插入时我们知道新 key 是从哪条路径插进去的所以可以用key node.left.key判断方向删除时当前子树高度下降可能来自左子树也可能来自右子树而且没有任何新 key 可以参考所以必须靠节点自身的平衡因子以及左右孩子的平衡因子来判断。判断逻辑就是我前面 rebalance 函数里写的那两条当前节点 BF 1说明左子树高。如果左孩子的 BF 0说明是 LR 型先左旋左孩子否则是 LL 型直接右旋。当前节点 BF -1说明右子树高。如果右孩子的 BF 0说明是 RL 型先右旋右孩子否则是 RR 型直接左旋。注意这里对 LL 型而言判断条件是get_balance(node.left) 0。很多教材在删除场景写 0其实 0的情况在删除时也会出现此时直接右旋同样合法且效果正确。这也是用统一 rebalance 的好处之一不容易漏边界。4.3 删除的连锁失衡可能一路旋到根插入时旋转一次就能让整棵子树恢复原高但删除不是这样。删除可能导致某个子树高度减 1第一次旋转只修复了局部子树的平衡却可能让往上几层的节点从“没失衡”变成“失衡”。所以删除必须从递归返回路径上每一层都执行 rebalance一路检查到根节点为止。举个例子你删掉一棵很深平衡树的某个叶子这棵树最下层的失衡被一次旋转修复了但修复后它所在子树的高度又减了 1导致它的父节点失衡于是父节点也要转。如果父节点转完它所在子树的高度又变了爷爷节点也要跟着处理。正因为如此删除的 rebalance 调用不能像插入那样“大概率只转一次”而是要老老实实让每一层递归都执行一次完整判断。你只要保证每层都return rebalance(node)这个问题就被递归天然解决了。5. 常见问题与排查技巧实录5.1 旋转后平衡因子更新错位症状插入后树还是不平衡甚至出现“转完更歪了”的情况。原因 99% 是旋转内部高度更新顺序写反了。我见过有人把右旋写成# 错误示范 def rotate_right(y): x y.left T2 x.right x.right y y.left T2 update_height(x) update_height(y) return x表面看只是两行顺序调换但 x 的高度更新时y 还是旧的左孩子关系旋转已发生但 y 的高度没变算出来的 x.height 就比实际小或大。调试方法很简单在 get_balance 前后打印 node.key 和左右子树高度对比旋转前中后的值是不是符合预期。5.2 递归回溯时节点高度没更新症状插入后只有局部子树平衡了往上两层还是失衡甚至 root 的平衡因子始终不对。这种问题的根源往往不是旋转本身而是递归函数的返回路径上少了更新高度的步骤。有些人写的 insert只有走到 None 新建节点时设置高度回到中间节点时只做旋转判断忘了在返回前调 update_height。结果就是新节点插入后它的父节点、祖父节点的 height 全是旧值平衡因子自然算错。正确做法是像我的 rebalance 函数那样进入函数第一步就 update_height不管当前节点需不需要旋转高度都要先刷新。5.3 测试用例怎么覆盖四种旋转想确认自己的 AVL 实现正确最直接的方法是构造四个最小失衡场景分别验证四种旋转。给你一套我常用的插入序列构造 LL依次插入 30、20、10。插入 10 后30 的左子树高度为 2右子树为 0触发右旋。构造 RR依次插入 10、20、30。对称地触发左旋。构造 LR依次插入 30、10、20。插入 20 后30 的左孩子 10 的右子树高了先左旋 10 再右旋 30。构造 RL依次插入 10、30、20。先右旋 30 再左旋 10。验证方式我强烈建议写一个递归断言函数def assert_avl(node): if node is None: return True if abs(get_balance(node)) 1: raise AssertionError(fnode {node.key} unbalanced, bf{get_balance(node)}) assert_avl(node.left) assert_avl(node.right)再配合中序遍历必须是升序这个 BST 性质双重检查。每次插入后都调用 assert_avl基本能保证旋转写对了。5.4 画图调试比日志更有效我个人练 AVL 树最受益的习惯不是打日志而是写一个简短的括号表示法打印函数把树结构直接打印出来。例如一个平衡的树打印成(20(10,30))一看就知道树的形状。你也可以用层序遍历打印配合缩进看左右结构。调试旋转时我通常是手工构造上面那四个用例然后看打印结果是不是和预期形态一致。最后一个经验插入练熟后一定要把删除也测试到位。很多人只测插入导致 delete 里的 rebalance 从来没被触发过面试真让手撕删除时就露馅。我建议你准备一组较长的随机序列比如插入 1 到 100 的乱序再按随机顺序删除其中一半每步都跑 assert_avl。跑通之后你对“连锁失衡”的理解会扎实很多。AVL 树这个东西第一次写总觉得繁琐但你把旋转的指针变化画清楚、把统一 rebalance 的套路固定下来之后它就是一套非常机械的流程。以后再看到红黑树、跳表那些“近似平衡”的结构你也能立刻意识到它们为什么愿意放宽“高度差不超过 1”这个条件——毕竟保持严格平衡的维护成本在真实场景里有时候比收益还高。能完全搞懂 AVL 的人再去理解其他平衡结构基本就是降维打击。