1. 在动手写代码前先把AVL树的账算清楚1.1 为什么需要AVL树二叉搜索树的退化问题AVL树几乎是每个写数据结构的人绕不过去的一座桥。它不像红黑树那样条条框框多也不像B树那样贴近磁盘存储它处在逻辑能完全讲清、代码量又不会糊掉一屏的甜区。但现实是很多人照着博客抄了一份插入旋转跑了几组数据看着没啥问题就以为自己会了直到遇到删除操作才被按在地上摩擦。要理解AVL树得先看它解决的是什么问题。普通二叉搜索树BST在理想情况下查找复杂度是 O(log n)但这个理想情况依赖树长得比较均匀。一旦数据不是随机分布的尤其是有序插入时树就会往一个方向疯狂生长。比如依次插入 1、2、3、4、5每个新节点都挂在右孩子上树彻底退化成一条链表。此时查找数字 5 需要走 5 步数据量大了以后和线性查找没有区别BST 最核心的优势直接归零。AVL 树的解决办法很朴素规定任何节点的左右子树高度差绝对值不能超过 1。只要这个约束成立树高就被限制在 O(log n) 量级查找、插入、删除都能稳定在对数时间里完成。AVL 树是所有平衡树里平衡条件最严格的一种所以它的树高也是所有平衡树里最矮的代价是插入和删除时可能需要做更多的旋转调整。这个取舍在内存里跑的普通场景下完全值得尤其是读多写少、对稳定性敏感的场景。1.2 平衡因子的计算与符号约定AVL 树的旋转触发依据是某个节点的平衡因子balance factor超出了合法区间。常见的定义是balanceFactor height(left) - height(right)合法状态是 -1、0、1分别表示左子树略矮、左右等高、左子树略高。当平衡因子等于 2 或 -2 时说明这个节点的子树已经失衡必须旋转。这里有个很容易忽略的坑高度的定义必须先定死。我采用的是空节点高度为 0叶子节点高度为 1的约定这样 getHeight 对空指针返回 0任何非空节点的高度等于左右子树高度较大值加 1。网上还有约定叶子高度为 0的写法一样能跑但空指针要返回 -1代码写起来容易出边界错误我不太推荐新手用。符号约定也一样。有人习惯 leftHeight - rightHeight有人习惯反着来。理论上怎么定都行但一套代码里必须从头到尾保持一致。我自己习惯左减右的写法因为当平衡因子大于 1 时我能直接反应过来是左子树长高了、需要右旋小于 -1 时是右子树长高了、需要左旋。方向感非常直白不容易在旋转判断里绕晕。2. 节点结构设计一个高度字段引发的连锁反应2.1 最简节点定义与高度字段的作用AVL 树的节点比普通 BST 节点只多了一个东西height。但这个字段是整个平衡机制的传感器它的准确性直接决定了旋转判断对不对。我用 C 写的最小节点结构是这样的struct AVLNode { int key; int height; AVLNode* left; AVLNode* right; explicit AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {} };构造函数里把 height 初始化为 1因为新创建的节点没有左右孩子它自己就是一棵高度为 1 的树。这个细节看起来不起眼但如果忘了初始化或者初始化成 0后面所有高度比较都是错的而且这种错误特别隐蔽程序不会崩只是平衡调整可能莫名其妙多转一次或少转一次。2.2 高度更新函数的两个关键细节高度更新本身只有两行核心逻辑但容易写错的地方藏在细节里int getHeight(AVLNode* node) { return node ? node-height : 0; } void updateHeight(AVLNode* node) { node-height 1 max(getHeight(node-left), getHeight(node-right)); }第一getHeight 必须能处理空指针。如果你用node-height直接访问遇到空节点就会段错误。第二updateHeight 只在非空节点上调用。这两个约定配合好了后面不管旋转还是回溯代码都会非常干净。还有一个常见的反面写法插入或删除完成后对整棵树调用一次全局的重新计算所有高度。乍一看结果也对但这样做每轮操作的复杂度直接从 O(log n) 退化成了 O(n)AVL 树引以为傲的性能优势全部丢掉。正确做法是永远只更新结构发生变化的局部路径上的节点旋转函数内部、递归返回路径上都要及时调整。2.3 要不要带 parent 指针这个问题几乎每次讨论 AVL 树都会吵一轮。我的建议是学习阶段不要用 parent 指针用递归返回值的方案。带 parent 指针的版本在删除节点时确实方便特别是找当前节点的前驱/后继时不用从头遍历。但代价是每次旋转都要同步维护多个节点的 parent 指向顺序稍有差错就出现悬空指针或者树结构被切断。旋转操作本身已经够烧脑了再加上 parent 的更新逻辑很容易让人放弃。递归方案的核心思路是每个递归函数都返回调整后该子树的根节点调用方用这个返回值重新挂接到父节点上。比如node-left insert(node-left, key)如果左子树内部发生了旋转返回的新根就被自动挂回 node 的左边。树的递归结构在这里体现得淋漓尽致代码量少出错概率也低很多。3. 四种旋转的判定条件与实现顺序旋转不是把指针换一下就行3.1 LL 型与 RR 型最基本的单旋失衡情况可以归纳为四种形状LL、RR、LR、RL。LL 的含义是当前节点左子树偏高且造成偏高的节点位于左孩子的左子树里。形状像一个向左倾倒的折线解法是右旋。RR 完全对称向右倾倒解法是左旋。右旋代码AVLNode* rotateRight(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; x-right y; y-left T2; updateHeight(y); updateHeight(x); return x; }左旋是它的镜像版本AVLNode* rotateLeft(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; updateHeight(x); updateHeight(y); return y; }单旋代码总共就几步但里面有一个顺序问题特别关键更新高度时必须先更新旋转后下沉的那个节点再更新上浮的那个节点。比如右旋中y 变成了 x 的右孩子y 的高度依赖 x 的新子树结构如果先算 x 的高度x 拿到的是y 还没有下沉的旧高度最后高度就是错的。顺序反了程序不会立刻报错但会在后续操作的平衡因子判断里埋雷。3.2 LR 型与 RL 型为什么必须先内旋再外旋LR 的情况比较阴当前节点左子树偏高但长高的是左孩子的右子树。此时直接右旋旋转后仍然会有一侧偏高问题没解决。原因是树形结构不是单边倾斜而是中间拐了个弯必须先把这个弯捋直。以 LR 为例对左孩子做一次左旋让局部结构从左-右变成左-左再对当前节点做右旋。整个过程用文本示意z z y / \ / \ / \ x T4 y T4 x z / \ - / \ - / \ / \ T1 y x T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2RL 是 LR 的镜像先对右孩子右旋再对当前节点左旋。这个先内旋、再外旋的顺序不是约定俗成而是结构决定的。你只需要记住一个原则向内拐弯的先向外捋直。实际操作时我不建议背LR 先左旋后右旋这种口诀最好在纸上画出树形跟着指针走一遍几次以后自然就刻进脑子里了。3.3 统一封装一个 balance 函数插入和删除都要做平衡判断所以最好把更新高度、计算平衡因子、选择旋转方案统一封装起来int balanceFactor(AVLNode* node) { return getHeight(node-left) - getHeight(node-right); } AVLNode* balance(AVLNode* node) { updateHeight(node); int bf balanceFactor(node); if (bf 1) { if (balanceFactor(node-left) 0) { node-left rotateLeft(node-left); } return rotateRight(node); } if (bf -1) { if (balanceFactor(node-right) 0) { node-right rotateRight(node-right); } return rotateLeft(node); } return node; }这里的判断逻辑是如果当前节点左子树偏高再看它的左孩子。左孩子的平衡因子小于 0说明是左-右型需要先把左孩子左旋剥掉那个弯否则就是左-左型直接右旋即可。右子树偏高时完全镜像。这个 balance 函数是 AVL 树的核心插入、删除、甚至后续可能的其他修改操作都复用这一份逻辑避免了同一套旋转逻辑被复制多份后改一处漏一处的惨剧。4. 插入和删除的完整回溯逻辑旋转点选对了代码自然就顺了4.1 插入递归返回路径上的自动调整有了 balance 函数插入代码短得让人意外AVLNode* insert(AVLNode* node, int key) { if (!node) { return new AVLNode(key); } if (key node-key) { node-left insert(node-left, key); } else if (key node-key) { node-right insert(node-right, key); } else { return node; } return balance(node); }递归从叶子节点一层层返回每返回一层就调用 balance 修正一次。这样天然保证了从插入点往上所有可能失衡的祖先节点都会被检查到。为什么只需要检查祖先路径上的节点因为插入操作只改变了从新节点到根路径上那些子树的高度其他节点的高度和平衡因子完全没动。这也是平衡树操作复杂度能保持在 O(log n) 的根本原因。4.2 删除三种情况的处理与级联失衡删除比插入麻烦主要是节点本身有三种情况没有孩子、有一个孩子、有两个孩子。完整实现如下AVLNode* findMin(AVLNode* node) { while (node-left) { node node-left; } return node; } AVLNode* remove(AVLNode* node, int key) { if (!node) { return nullptr; } if (key node-key) { node-left remove(node-left, key); } else if (key node-key) { node-right remove(node-right, key); } else { if (!node-left || !node-right) { AVLNode* child node-left ? node-left : node-right; delete node; return child; } AVLNode* successor findMin(node-right); node-key successor-key; node-right remove(node-right, successor-key); } return balance(node); }前两种情况处理相对直接删除叶子节点后返回空指针删除单孩子节点后返回那个唯一的孩子让父节点直接挂接。对于有两个孩子的节点我采用最常见的策略找右子树中的最小节点中序后继把它的 key 复制到当前节点再递归去右子树里删除这个后继节点。这相当于把删除双子节点问题降级成删除一个至少有一个孩子被顶替的节点简化了处理逻辑。删除真正的难点在于一次旋转修正后局部子树的高度可能又下降了一层从而触发父节点甚至更高祖先的失衡。这就是所谓的级联失衡。所以 balance 必须放在递归返回路径上逐层执行而不是只在删除成功的那一层做完就收工。4.3 删除场景中的一处判定细节回到 balance 函数里的判定逻辑if (bf 1) { if (balanceFactor(node-left) 0) { node-left rotateLeft(node-left); } return rotateRight(node); }这里我用的是 0也就是左孩子平衡因子为负数时才做 LR 双旋为 0 或正数都走 LL 单旋。插入场景下左孩子平衡因子为 0 的情况几乎不会出现但删除场景可能出现删除导致当前节点右子树变矮、平衡因子从 1 变成 2而左孩子的左右子树恰好等稿。此时直接右旋是合法的旋转后整棵子树依然满足平衡条件不需要多做一次内旋。所以这个判定在插入和删除里都能通用反而是网上有些写法写成了对负数判断太严格或漏掉 0 的情况在删除测试里容易翻车。4.4 重复键的处理策略插入时遇到相同 key我的代码直接返回当前节点不做任何操作相当于 AVL 树默认不存重复键。如果业务上需要支持计数更稳妥的做法是在节点里加一个 count 字段或者在外部用 map 计数否则插入重复键的语义会很模糊测试也没法设计。删除时同样只删一个匹配 key 的节点如果树里根本没有这个 key递归会走到空节点返回空指针安全退出。实际使用时可以先调用查找确认 key 存在再执行删除避免误删逻辑。5. 测试AVL树别只验证没崩要验证结构5.1 中序遍历检查 BST 有序性写完 AVL 树第一件事不是看平衡因子而是先确认它仍然是二叉搜索树。旋转操作很容易把中序顺序打乱而中序遍历输出必须严格递增这是最基本的结构底线。void inorder(AVLNode* node, vectorint out) { if (!node) { return; } inorder(node-left, out); out.push_back(node-key); inorder(node-right, out); }这个检查在每次插入或删除后做一次能快速排除指针接错导致树结构被破坏的问题。但注意它只能证明 BST 性质成立不能证明 AVL 树平衡性质成立。所以还需要下一步。5.2 递归校验 AVL 性质的完整断言验证 AVL 性质时要同时检查三件事左右子树高度差不能超过 1、每个节点自己存的 height 字段必须等于真实高度、整棵树在中序上保持有序。int verifyAVL(AVLNode* node, bool ok) { if (!node) { return 0; } int leftHeight verifyAVL(node-left, ok); int rightHeight verifyAVL(node-right, ok); if (abs(leftHeight - rightHeight) 1) { ok false; } if (node-height ! 1 max(leftHeight, rightHeight)) { ok false; } return node-height; }这个函数每调用一次是 O(n) 的复杂度所以不适合放在线上效率要求高的代码里但它非常适合测试阶段。每轮随机操作后跑一次就能把树长歪了和高度字段没更新这两类 bug 同时暴露出来。其中高度字段没更新这一类单纯看平衡因子还不容易发现只有对比节点真实高度才能抓到。5.3 随机化压力测试结构固定几组手工用例远远不够AVL 树能不能撑住得靠随机化测试来压。我给一个常用的测试骨架void stressTest() { AVLNode* root nullptr; vectorint keys; unordered_setint pool; for (int i 0; i 100000; i) { int key rand(); root insert(root, key); if (pool.insert(key).second) { keys.push_back(key); } if (i % 1000 0) { bool ok true; verifyAVL(root, ok); assert(ok); } } // 随机打乱删除顺序 random_shuffle(keys.begin(), keys.end()); for (int key : keys) { root remove(root, key); bool ok true; verifyAVL(root, ok); assert(ok); } assert(root nullptr); }随机测试的关键不是跑完不崩而是每操作一批就立刻验证结构。如果你在 1000 次操作后才发现树坏了定位 bug 的搜索空间会非常大如果每 1000 次甚至每 100 次就验证一次就能把问题范围缩小很多。5.4 边界用例设计表手写的边界用例也不能省尤其这些场景场景输入方式需要关注的点递增插入1, 2, 3, ..., 1000触发大量 RR 单旋递减插入1000, 999, ..., 1触发大量 LL 单旋之字形插入1, 3, 2, 5, 4, ...触发 LR/RL 双旋重复键插入相同 key 反复插入确认树不膨胀、顺序不变删除叶子节点逐个删除叶子删除后平衡恢复删除单孩子节点删除只有一个孩子的节点确认返回值正确挂接删除双孩子节点删除内部节点确认中序后继替换正确删除根节点反复删除当前根确认根指针更新正确这些用例不需要复杂工具手工构造几十个 key 的序列就够了。关键是覆盖每一种旋转类型和每一种删除情况而不是只追求数据量大。5.5 可视化打印辅助定位当断言失败时可视化打印树结构比猜 bug 高效得多。我常用一个横向打印的辅助函数void dumpTree(AVLNode* node, int depth 0) { if (!node) { return; } dumpTree(node-right, depth 1); cout string(depth * 4, ) node-key (h node-height ) endl; dumpTree(node-left, depth 1); }这样打印出来的树根在左边右子树在上方左子树在下方眼睛一扫就能看出哪个节点的左右子树高度明显不对进而定位是旋转写错了还是高度更新漏了。6. 我在实现和调试过程中踩过的几个典型坑6.1 旋转后高度更新顺序搞反这是我自己最早犯的错。右旋函数里先写了updateHeight(x)再写updateHeight(y)结果 x 拿到的是 y 还没有下沉时的高度导致 x 的高度比真实值小 1。这 1 的误差不会让代码立刻崩但在下一次插入或删除时平衡因子计算就会偏离真实情况可能触发多余的旋转甚至让一个已经失衡的地方被漏掉。后来我把 updateHeight 的调用顺序写死在旋转函数里并且注释里标明先更新旋转后在下层的节点再更新在上层的节点。每次拷贝代码时也格外小心。6.2 删除双子节点时直接删除原节点最早写删除遇到双子节点时我脑子里想的是找到后继后把后继节点从树里拆出来然后手一抖去 delete 了当前节点结果当前节点的子树直接丢失整棵树数据错乱中序遍历输出直接缺了一片节点。正确方案是用 key 值复制加递归删除后继节点不要试图去直接移动指针。这样虽然多了一次递归调用但代码简单逻辑不容易出错内存释放也能统一由只有一个或零个孩子那条路径负责。6.3 测试只验证不崩结果树上全是问题写旋转和删除的头一版跑了随机插入 10 万条数据程序稳稳当当没崩我以为 AVL 树写对了。直到我加上 verifyAVL 结构校验才发现平衡因子错误一大堆。原因是测试只检查了有没有段错误、有没有死循环完全没有校验树的 AVL 性质。所以我说测试 AVL 树最忌讳只做黑盒测试。一定要在关键节点加结构断点检查如果不放心性能测试阶段可以每 1000 次操作校验一次兼顾速度和有效性。6.4 高度初始化为 0导致所有叶子节点头重脚轻这个是初学阶段的经典错误。如果把 AVLNode 的 height 初始化为 0那么插入两个节点后根节点的平衡因子可能出现 0看起来很正常但叶子节点高度本身就不对再继续插入时会发现旋转逻辑怎么都对不上号。排查这种问题最直接的方式就是打印每个节点的真实高度和存储高度一对比就露馅。6.5 二分定位 bug 的技巧最后分享一个排错经验。如果随机测试是在第 50000 次操作时失败直接盯着 5 万条记录看肯定崩溃。我的做法是保留每次插入或删除的 key 和操作类型到一个操作序列里然后二分这个序列先回放前半段看看是否触发失败如果没触发就说明 bug 在后半段或者由后段某个操作与前半段结构交互触发。反复缩小范围很快就能定位到一个几十条操作的小序列然后在纸上或调试器里逐步跟踪几乎都能找到问题根因。AVL 树本身不算难难的是把插入、删除、旋转、高度更新、验证这些环节拼成一个完整闭环。每一次重写我对递归返回值即修正入口这个思路的信心就会更强一些。如果你正在被某个旋转问题卡住不妨先把测试的验证做扎实让树告诉你哪里错了真的。 
长河君 · 2026/9/9 21:52:51 · 阅读 1.2k AVL树从旋转到删除：平衡因子计算与完整实现指南
1. 在动手写代码前先把AVL树的账算清楚1.1 为什么需要AVL树二叉搜索树的退化问题AVL树几乎是每个写数据结构的人绕不过去的一座桥。它不像红黑树那样条条框框多也不像B树那样贴近磁盘存储它处在逻辑能完全讲清、代码量又不会糊掉一屏的甜区。但现实是很多人照着博客抄了一份插入旋转跑了几组数据看着没啥问题就以为自己会了直到遇到删除操作才被按在地上摩擦。要理解AVL树得先看它解决的是什么问题。普通二叉搜索树BST在理想情况下查找复杂度是 O(log n)但这个理想情况依赖树长得比较均匀。一旦数据不是随机分布的尤其是有序插入时树就会往一个方向疯狂生长。比如依次插入 1、2、3、4、5每个新节点都挂在右孩子上树彻底退化成一条链表。此时查找数字 5 需要走 5 步数据量大了以后和线性查找没有区别BST 最核心的优势直接归零。AVL 树的解决办法很朴素规定任何节点的左右子树高度差绝对值不能超过 1。只要这个约束成立树高就被限制在 O(log n) 量级查找、插入、删除都能稳定在对数时间里完成。AVL 树是所有平衡树里平衡条件最严格的一种所以它的树高也是所有平衡树里最矮的代价是插入和删除时可能需要做更多的旋转调整。这个取舍在内存里跑的普通场景下完全值得尤其是读多写少、对稳定性敏感的场景。1.2 平衡因子的计算与符号约定AVL 树的旋转触发依据是某个节点的平衡因子balance factor超出了合法区间。常见的定义是balanceFactor height(left) - height(right)合法状态是 -1、0、1分别表示左子树略矮、左右等高、左子树略高。当平衡因子等于 2 或 -2 时说明这个节点的子树已经失衡必须旋转。这里有个很容易忽略的坑高度的定义必须先定死。我采用的是空节点高度为 0叶子节点高度为 1的约定这样 getHeight 对空指针返回 0任何非空节点的高度等于左右子树高度较大值加 1。网上还有约定叶子高度为 0的写法一样能跑但空指针要返回 -1代码写起来容易出边界错误我不太推荐新手用。符号约定也一样。有人习惯 leftHeight - rightHeight有人习惯反着来。理论上怎么定都行但一套代码里必须从头到尾保持一致。我自己习惯左减右的写法因为当平衡因子大于 1 时我能直接反应过来是左子树长高了、需要右旋小于 -1 时是右子树长高了、需要左旋。方向感非常直白不容易在旋转判断里绕晕。2. 节点结构设计一个高度字段引发的连锁反应2.1 最简节点定义与高度字段的作用AVL 树的节点比普通 BST 节点只多了一个东西height。但这个字段是整个平衡机制的传感器它的准确性直接决定了旋转判断对不对。我用 C 写的最小节点结构是这样的struct AVLNode { int key; int height; AVLNode* left; AVLNode* right; explicit AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {} };构造函数里把 height 初始化为 1因为新创建的节点没有左右孩子它自己就是一棵高度为 1 的树。这个细节看起来不起眼但如果忘了初始化或者初始化成 0后面所有高度比较都是错的而且这种错误特别隐蔽程序不会崩只是平衡调整可能莫名其妙多转一次或少转一次。2.2 高度更新函数的两个关键细节高度更新本身只有两行核心逻辑但容易写错的地方藏在细节里int getHeight(AVLNode* node) { return node ? node-height : 0; } void updateHeight(AVLNode* node) { node-height 1 max(getHeight(node-left), getHeight(node-right)); }第一getHeight 必须能处理空指针。如果你用node-height直接访问遇到空节点就会段错误。第二updateHeight 只在非空节点上调用。这两个约定配合好了后面不管旋转还是回溯代码都会非常干净。还有一个常见的反面写法插入或删除完成后对整棵树调用一次全局的重新计算所有高度。乍一看结果也对但这样做每轮操作的复杂度直接从 O(log n) 退化成了 O(n)AVL 树引以为傲的性能优势全部丢掉。正确做法是永远只更新结构发生变化的局部路径上的节点旋转函数内部、递归返回路径上都要及时调整。2.3 要不要带 parent 指针这个问题几乎每次讨论 AVL 树都会吵一轮。我的建议是学习阶段不要用 parent 指针用递归返回值的方案。带 parent 指针的版本在删除节点时确实方便特别是找当前节点的前驱/后继时不用从头遍历。但代价是每次旋转都要同步维护多个节点的 parent 指向顺序稍有差错就出现悬空指针或者树结构被切断。旋转操作本身已经够烧脑了再加上 parent 的更新逻辑很容易让人放弃。递归方案的核心思路是每个递归函数都返回调整后该子树的根节点调用方用这个返回值重新挂接到父节点上。比如node-left insert(node-left, key)如果左子树内部发生了旋转返回的新根就被自动挂回 node 的左边。树的递归结构在这里体现得淋漓尽致代码量少出错概率也低很多。3. 四种旋转的判定条件与实现顺序旋转不是把指针换一下就行3.1 LL 型与 RR 型最基本的单旋失衡情况可以归纳为四种形状LL、RR、LR、RL。LL 的含义是当前节点左子树偏高且造成偏高的节点位于左孩子的左子树里。形状像一个向左倾倒的折线解法是右旋。RR 完全对称向右倾倒解法是左旋。右旋代码AVLNode* rotateRight(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; x-right y; y-left T2; updateHeight(y); updateHeight(x); return x; }左旋是它的镜像版本AVLNode* rotateLeft(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; updateHeight(x); updateHeight(y); return y; }单旋代码总共就几步但里面有一个顺序问题特别关键更新高度时必须先更新旋转后下沉的那个节点再更新上浮的那个节点。比如右旋中y 变成了 x 的右孩子y 的高度依赖 x 的新子树结构如果先算 x 的高度x 拿到的是y 还没有下沉的旧高度最后高度就是错的。顺序反了程序不会立刻报错但会在后续操作的平衡因子判断里埋雷。3.2 LR 型与 RL 型为什么必须先内旋再外旋LR 的情况比较阴当前节点左子树偏高但长高的是左孩子的右子树。此时直接右旋旋转后仍然会有一侧偏高问题没解决。原因是树形结构不是单边倾斜而是中间拐了个弯必须先把这个弯捋直。以 LR 为例对左孩子做一次左旋让局部结构从左-右变成左-左再对当前节点做右旋。整个过程用文本示意z z y / \ / \ / \ x T4 y T4 x z / \ - / \ - / \ / \ T1 y x T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2RL 是 LR 的镜像先对右孩子右旋再对当前节点左旋。这个先内旋、再外旋的顺序不是约定俗成而是结构决定的。你只需要记住一个原则向内拐弯的先向外捋直。实际操作时我不建议背LR 先左旋后右旋这种口诀最好在纸上画出树形跟着指针走一遍几次以后自然就刻进脑子里了。3.3 统一封装一个 balance 函数插入和删除都要做平衡判断所以最好把更新高度、计算平衡因子、选择旋转方案统一封装起来int balanceFactor(AVLNode* node) { return getHeight(node-left) - getHeight(node-right); } AVLNode* balance(AVLNode* node) { updateHeight(node); int bf balanceFactor(node); if (bf 1) { if (balanceFactor(node-left) 0) { node-left rotateLeft(node-left); } return rotateRight(node); } if (bf -1) { if (balanceFactor(node-right) 0) { node-right rotateRight(node-right); } return rotateLeft(node); } return node; }这里的判断逻辑是如果当前节点左子树偏高再看它的左孩子。左孩子的平衡因子小于 0说明是左-右型需要先把左孩子左旋剥掉那个弯否则就是左-左型直接右旋即可。右子树偏高时完全镜像。这个 balance 函数是 AVL 树的核心插入、删除、甚至后续可能的其他修改操作都复用这一份逻辑避免了同一套旋转逻辑被复制多份后改一处漏一处的惨剧。4. 插入和删除的完整回溯逻辑旋转点选对了代码自然就顺了4.1 插入递归返回路径上的自动调整有了 balance 函数插入代码短得让人意外AVLNode* insert(AVLNode* node, int key) { if (!node) { return new AVLNode(key); } if (key node-key) { node-left insert(node-left, key); } else if (key node-key) { node-right insert(node-right, key); } else { return node; } return balance(node); }递归从叶子节点一层层返回每返回一层就调用 balance 修正一次。这样天然保证了从插入点往上所有可能失衡的祖先节点都会被检查到。为什么只需要检查祖先路径上的节点因为插入操作只改变了从新节点到根路径上那些子树的高度其他节点的高度和平衡因子完全没动。这也是平衡树操作复杂度能保持在 O(log n) 的根本原因。4.2 删除三种情况的处理与级联失衡删除比插入麻烦主要是节点本身有三种情况没有孩子、有一个孩子、有两个孩子。完整实现如下AVLNode* findMin(AVLNode* node) { while (node-left) { node node-left; } return node; } AVLNode* remove(AVLNode* node, int key) { if (!node) { return nullptr; } if (key node-key) { node-left remove(node-left, key); } else if (key node-key) { node-right remove(node-right, key); } else { if (!node-left || !node-right) { AVLNode* child node-left ? node-left : node-right; delete node; return child; } AVLNode* successor findMin(node-right); node-key successor-key; node-right remove(node-right, successor-key); } return balance(node); }前两种情况处理相对直接删除叶子节点后返回空指针删除单孩子节点后返回那个唯一的孩子让父节点直接挂接。对于有两个孩子的节点我采用最常见的策略找右子树中的最小节点中序后继把它的 key 复制到当前节点再递归去右子树里删除这个后继节点。这相当于把删除双子节点问题降级成删除一个至少有一个孩子被顶替的节点简化了处理逻辑。删除真正的难点在于一次旋转修正后局部子树的高度可能又下降了一层从而触发父节点甚至更高祖先的失衡。这就是所谓的级联失衡。所以 balance 必须放在递归返回路径上逐层执行而不是只在删除成功的那一层做完就收工。4.3 删除场景中的一处判定细节回到 balance 函数里的判定逻辑if (bf 1) { if (balanceFactor(node-left) 0) { node-left rotateLeft(node-left); } return rotateRight(node); }这里我用的是 0也就是左孩子平衡因子为负数时才做 LR 双旋为 0 或正数都走 LL 单旋。插入场景下左孩子平衡因子为 0 的情况几乎不会出现但删除场景可能出现删除导致当前节点右子树变矮、平衡因子从 1 变成 2而左孩子的左右子树恰好等稿。此时直接右旋是合法的旋转后整棵子树依然满足平衡条件不需要多做一次内旋。所以这个判定在插入和删除里都能通用反而是网上有些写法写成了对负数判断太严格或漏掉 0 的情况在删除测试里容易翻车。4.4 重复键的处理策略插入时遇到相同 key我的代码直接返回当前节点不做任何操作相当于 AVL 树默认不存重复键。如果业务上需要支持计数更稳妥的做法是在节点里加一个 count 字段或者在外部用 map 计数否则插入重复键的语义会很模糊测试也没法设计。删除时同样只删一个匹配 key 的节点如果树里根本没有这个 key递归会走到空节点返回空指针安全退出。实际使用时可以先调用查找确认 key 存在再执行删除避免误删逻辑。5. 测试AVL树别只验证没崩要验证结构5.1 中序遍历检查 BST 有序性写完 AVL 树第一件事不是看平衡因子而是先确认它仍然是二叉搜索树。旋转操作很容易把中序顺序打乱而中序遍历输出必须严格递增这是最基本的结构底线。void inorder(AVLNode* node, vectorint out) { if (!node) { return; } inorder(node-left, out); out.push_back(node-key); inorder(node-right, out); }这个检查在每次插入或删除后做一次能快速排除指针接错导致树结构被破坏的问题。但注意它只能证明 BST 性质成立不能证明 AVL 树平衡性质成立。所以还需要下一步。5.2 递归校验 AVL 性质的完整断言验证 AVL 性质时要同时检查三件事左右子树高度差不能超过 1、每个节点自己存的 height 字段必须等于真实高度、整棵树在中序上保持有序。int verifyAVL(AVLNode* node, bool ok) { if (!node) { return 0; } int leftHeight verifyAVL(node-left, ok); int rightHeight verifyAVL(node-right, ok); if (abs(leftHeight - rightHeight) 1) { ok false; } if (node-height ! 1 max(leftHeight, rightHeight)) { ok false; } return node-height; }这个函数每调用一次是 O(n) 的复杂度所以不适合放在线上效率要求高的代码里但它非常适合测试阶段。每轮随机操作后跑一次就能把树长歪了和高度字段没更新这两类 bug 同时暴露出来。其中高度字段没更新这一类单纯看平衡因子还不容易发现只有对比节点真实高度才能抓到。5.3 随机化压力测试结构固定几组手工用例远远不够AVL 树能不能撑住得靠随机化测试来压。我给一个常用的测试骨架void stressTest() { AVLNode* root nullptr; vectorint keys; unordered_setint pool; for (int i 0; i 100000; i) { int key rand(); root insert(root, key); if (pool.insert(key).second) { keys.push_back(key); } if (i % 1000 0) { bool ok true; verifyAVL(root, ok); assert(ok); } } // 随机打乱删除顺序 random_shuffle(keys.begin(), keys.end()); for (int key : keys) { root remove(root, key); bool ok true; verifyAVL(root, ok); assert(ok); } assert(root nullptr); }随机测试的关键不是跑完不崩而是每操作一批就立刻验证结构。如果你在 1000 次操作后才发现树坏了定位 bug 的搜索空间会非常大如果每 1000 次甚至每 100 次就验证一次就能把问题范围缩小很多。5.4 边界用例设计表手写的边界用例也不能省尤其这些场景场景输入方式需要关注的点递增插入1, 2, 3, ..., 1000触发大量 RR 单旋递减插入1000, 999, ..., 1触发大量 LL 单旋之字形插入1, 3, 2, 5, 4, ...触发 LR/RL 双旋重复键插入相同 key 反复插入确认树不膨胀、顺序不变删除叶子节点逐个删除叶子删除后平衡恢复删除单孩子节点删除只有一个孩子的节点确认返回值正确挂接删除双孩子节点删除内部节点确认中序后继替换正确删除根节点反复删除当前根确认根指针更新正确这些用例不需要复杂工具手工构造几十个 key 的序列就够了。关键是覆盖每一种旋转类型和每一种删除情况而不是只追求数据量大。5.5 可视化打印辅助定位当断言失败时可视化打印树结构比猜 bug 高效得多。我常用一个横向打印的辅助函数void dumpTree(AVLNode* node, int depth 0) { if (!node) { return; } dumpTree(node-right, depth 1); cout string(depth * 4, ) node-key (h node-height ) endl; dumpTree(node-left, depth 1); }这样打印出来的树根在左边右子树在上方左子树在下方眼睛一扫就能看出哪个节点的左右子树高度明显不对进而定位是旋转写错了还是高度更新漏了。6. 我在实现和调试过程中踩过的几个典型坑6.1 旋转后高度更新顺序搞反这是我自己最早犯的错。右旋函数里先写了updateHeight(x)再写updateHeight(y)结果 x 拿到的是 y 还没有下沉时的高度导致 x 的高度比真实值小 1。这 1 的误差不会让代码立刻崩但在下一次插入或删除时平衡因子计算就会偏离真实情况可能触发多余的旋转甚至让一个已经失衡的地方被漏掉。后来我把 updateHeight 的调用顺序写死在旋转函数里并且注释里标明先更新旋转后在下层的节点再更新在上层的节点。每次拷贝代码时也格外小心。6.2 删除双子节点时直接删除原节点最早写删除遇到双子节点时我脑子里想的是找到后继后把后继节点从树里拆出来然后手一抖去 delete 了当前节点结果当前节点的子树直接丢失整棵树数据错乱中序遍历输出直接缺了一片节点。正确方案是用 key 值复制加递归删除后继节点不要试图去直接移动指针。这样虽然多了一次递归调用但代码简单逻辑不容易出错内存释放也能统一由只有一个或零个孩子那条路径负责。6.3 测试只验证不崩结果树上全是问题写旋转和删除的头一版跑了随机插入 10 万条数据程序稳稳当当没崩我以为 AVL 树写对了。直到我加上 verifyAVL 结构校验才发现平衡因子错误一大堆。原因是测试只检查了有没有段错误、有没有死循环完全没有校验树的 AVL 性质。所以我说测试 AVL 树最忌讳只做黑盒测试。一定要在关键节点加结构断点检查如果不放心性能测试阶段可以每 1000 次操作校验一次兼顾速度和有效性。6.4 高度初始化为 0导致所有叶子节点头重脚轻这个是初学阶段的经典错误。如果把 AVLNode 的 height 初始化为 0那么插入两个节点后根节点的平衡因子可能出现 0看起来很正常但叶子节点高度本身就不对再继续插入时会发现旋转逻辑怎么都对不上号。排查这种问题最直接的方式就是打印每个节点的真实高度和存储高度一对比就露馅。6.5 二分定位 bug 的技巧最后分享一个排错经验。如果随机测试是在第 50000 次操作时失败直接盯着 5 万条记录看肯定崩溃。我的做法是保留每次插入或删除的 key 和操作类型到一个操作序列里然后二分这个序列先回放前半段看看是否触发失败如果没触发就说明 bug 在后半段或者由后段某个操作与前半段结构交互触发。反复缩小范围很快就能定位到一个几十条操作的小序列然后在纸上或调试器里逐步跟踪几乎都能找到问题根因。AVL 树本身不算难难的是把插入、删除、旋转、高度更新、验证这些环节拼成一个完整闭环。每一次重写我对递归返回值即修正入口这个思路的信心就会更强一些。如果你正在被某个旋转问题卡住不妨先把测试的验证做扎实让树告诉你哪里错了真的。