C++ 实现二叉平衡树 AVL 的节点合并、分裂及旋转自平衡算法全流程【源码】-C++-PHP中文网

avl树旋转必须先更新子树高度再更新根高度，否则高度错乱导致失衡判断错误；插入和删除后需自底向上回溯检查平衡因子并旋转，删除可能触发多次旋转。

c++ 实现二叉平衡树 avl 的节点合并、分裂及旋转自平衡算法全流程【源码】

AVL 树的 `rotateLeft` 和 `rotateRight` 必须更新高度且先更新子树再更新根

很多实现卡在旋转后树高错乱，根本原因是没按顺序更新 height 字段。AVL 依赖高度差判断是否失衡，而高度必须是子树最大高度加 1 —— 所以必须先递归更新子节点高度，再算当前节点。

典型错误写法：node->height = max(height(node->left), height(node->right)) + 1 写在旋转前，或漏掉某一支子树的更新。

rotateRight 后：先更新 newRoot->right（原 root）的高度，再更新 newRoot 自身高度
rotateLeft 同理：先更新 newRoot->left（原 root），再更新 newRoot
高度计算函数必须处理空指针：int height(Node* n) { return n ? n->height : 0; }

插入后自平衡不能只看当前节点，要沿父路径向上检查并旋转

插入一个节点可能只让某一层失衡，但旋转可能把失衡“推高”——比如在右子树插入导致根节点左高右低差为 2，执行 rotateRight 后，新根的高度变化可能让祖父节点再次失衡。所以必须从插入点向上回溯到根，对每个节点检查平衡因子，并在首次失衡处旋转（一次插入最多触发一次旋转，但需确保路径上所有祖先高度已更新）。

递归插入返回更新后的子树根指针，每层返回前调用 updateHeight 和 balance
balance 函数根据平衡因子（height(left) - height(right)）决定：±2 时旋转，±1 或 0 时不操作
注意四种情况：LL、RR、LR、RL —— LR 是先对左孩子 rotateLeft，再对当前节点 rotateRight；RL 反之

AVL 没有标准意义上的“节点合并”和“分裂”，那是 B-tree 的操作

这是最容易误解的一点。AVL 是二叉搜索树（BST）的自平衡变种，只支持单节点插入/删除，不支持像 B-tree 那样把两个满节点合并成一个，也不支持把一个超载节点分裂成两个。所谓“合并”在 AVL 中实际是 delete 后的再平衡，“分裂”并不存在。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

如果你看到某些资料提 AVL 合并，大概率混淆了数据结构：

B-tree / B+tree 支持 merge 和 split，因为节点可存多个键，且有阶数约束
AVL 节点只有 left/right 指针和一个 key，插入删除都走 BST 规则，失衡靠旋转修复
强行模拟“合并两棵 AVL 树”？只能把一棵全取出来插入另一棵 —— 时间复杂度 O(n log m)，不是 O(log n)

删除节点后自平衡比插入更易出错：需持续向上回溯直到根，且可能触发多次旋转

插入最多导致一条路径失衡，而删除可能让某节点平衡因子从 0 变成 ±2，其祖先也可能从 ±1 变成 ±2 —— 所以删除后必须从被删节点的父节点开始，一路向上至根，逐个检查并旋转。而且一次删除可能触发多次旋转（比如某次 rotateRight 后，祖父又失衡，再 rotate）。

删除后不要只检查直接父节点，要用栈或递归返回机制保存路径
推荐写法：递归 remove 返回更新后的子树根，每次返回前做 updateHeight → getBalanceFactor → 若失衡则 balance → 返回新根
特别注意“双子节点”删除场景：用中序后继替换后，要对后继原位置做删除 —— 这个子删除同样要触发回溯平衡

真正难的不是写出四个旋转函数，而是确保每次修改指针后，所有相关节点的 height 值准确、更新顺序正确、回溯范围完整。哪怕一个 height 少更新一次，后续所有平衡判断都会失效。