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

AVL节点高度必须自底向上实时更新：从插入点沿父指针回溯，每次调用updateHeight(node)重算高度（node->height = 1 + max(getHeight(left), getHeight(right))），若高度未变则剪枝终止；旋转前须确保高度与平衡因子准确，右旋等操作需完整执行指针重连、父子关系修复及两节点高度重算。

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

AVL 节点高度怎么维护才不崩？

AVL 树的核心是每个节点的 height 必须实时准确，否则 getBalanceFactor() 算出来就是错的，后续旋转判断全失效。常见错误是只在插入/删除后递归更新一次，但没考虑子树高度变化可能只影响路径上少数几个祖先节点——应该从修改点向上回溯更新，直到某节点高度不再变化为止。

实操建议：

updateHeight(node) 只需一行：node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
插入后用 while 循环沿 parent 指针上溯，每次调用 updateHeight()，若当前高度未变就 break（剪枝）
别在 getHeight() 里加空指针判空逻辑——统一用宏或内联函数返回 -1，比如 #define getHeight(n) ((n) ? (n)->height : -1)，避免运行时分支开销

左旋 / 右旋代码怎么写才不出错？

旋转不是“交换左右指针”那么简单，漏掉 parent 更新、子树重挂、高度重算，就会导致树断裂或平衡因子错乱。典型症状是旋转后出现 segmentation fault 或插入后树高暴涨（说明子树没正确挂回）。

以右旋为例（rotateRight(node)），关键三步必须齐全：

保存 node->left 为 newRoot
把 newRoot->right 挂到 node->left，并更新其 parent（如有）
把 node 挂到 newRoot->right，同时更新 node->parent 和 newRoot->parent

示例片段（无 parent 字段可省略 parent 操作）：

Node* rotateRight(Node* node) {
    Node* newRoot = node->left;
    node->left = newRoot->right;
    if (newRoot->right) newRoot->right->parent = node;
    newRoot->right = node;
    newRoot->parent = node->parent;
    node->parent = newRoot;
    updateHeight(node);
    updateHeight(newRoot);
    return newRoot;
}

插入后四类失衡场景怎么精准触发对应旋转？

失衡只发生在插入路径上某个节点的平衡因子变成 +2 或 -2 时，但具体选哪种旋转（LL/LR/RR/RL），取决于插入位置相对于该节点的“方向组合”。直接记口诀容易混淆，更可靠的是看 node->left->balanceFactor 或 node->right->balanceFactor 的符号：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

当 getBalanceFactor(node) == 2（左重）：
　　若 getBalanceFactor(node->left) >= 0 → LL 型，用 rotateRight(node)
　　若 getBalanceFactor(node->left) == -1 → LR 型，先 rotateLeft(node->left) 再 rotateRight(node)
当 getBalanceFactor(node) == -2（右重）：
　　若 getBalanceFactor(node->right) → RR 型，用 <code>rotateLeft(node)
　　若 getBalanceFactor(node->right) == 1 → RL 型，先 rotateRight(node->right) 再 rotateLeft(node)

注意：LR/RL 中第一次旋转后，原 node->left 或 node->right 的高度已变，必须在第二次旋转前重新计算其 balance factor。

合并与分裂在 AVL 上真有必要实现吗？

标准 AVL 树不定义 merge 和 split——那是 Treap、Splay 或 B-Tree 的操作。强行给 AVL 加这两个接口，会破坏 O(log n) 平衡保证：合并两棵 AVL 树最坏要遍历全部节点重建；分裂则需中序遍历截断，再分别建树。实际项目中，除非你在写支持区间操作的扩展 AVL（类似 order statistic tree），否则用 insert + erase 组合更安全。

如果真要支持：