C++ 实现二叉平衡树 AVL 的节点合并与分裂算法及其高度平衡维护【源码】-C++-PHP中文网

不能直接拼接，因高度差易超1而失衡；必须满足左右树高度差≤1且配合中间键构造新根，或先旋转再递归合并；生产中更倾向批量插入后重建。

c++ 实现二叉平衡树 avl 的节点合并与分裂算法及其高度平衡维护【源码】

AVL 树节点合并：为什么不能直接拼接左右子树

AVL 树不支持像普通二叉搜索树那样简单地「合并两棵子树」，因为合并后高度差极易突破 1。例如，把一棵高度为 5 的左子树和高度为 3 的右子树强行挂到新根下，根节点的平衡因子就变成 2，违反 AVL 定义。

真正可行的合并，只适用于「高度差 ≤ 1」的两棵 AVL 树 + 一个中间键值（即 merge(left_avl, key, right_avl)）。此时需构造新根，再递归调整路径上的平衡：

若 abs(height(left_avl) - height(right_avl)) ≤ 1，直接以 key 为根、左右为子树，返回即可
若 left_avl 高出 2，且其右子树更高 → 先对 left_avl 做 rightLeftRotate()，再递归合并
若 right_avl 高出 2，且其左子树更高 → 先对 right_avl 做 leftRightRotate()，再递归合并

注意：标准 AVL 实现中几乎不暴露 merge 接口，它本质是 insert 的逆操作变体，实际项目中更常通过批量 insert + 重建来替代。

AVL 树节点分裂：split(root, key) 的边界处理陷阱

分裂是指给定键 key，将 AVL 树拆成两棵：左树含所有 的节点，右树含所有 <code>≥ key 的节点。难点不在逻辑，而在旋转后子树归属和高度更新的同步。

常见错误是分裂后未重算子树高度，导致后续插入/删除触发错误旋转。正确做法是：每次递归返回前，必须调用 updateHeight(node)；且分裂结果的两棵子树，其根节点高度要独立维护，不可复用原树缓存值。

示例关键片段：

C++14

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

下载

pair<node node> split(Node* node, int key) {
    if (!node) return {nullptr, nullptr};
    if (node->key right, key);
        node->right = left;
        updateHeight(node); // 必须立即更新！
        return {node, right};
    } else {
        auto [left, right] = split(node->left, key);
        node->left = right;
        updateHeight(node);
        return {left, node};
    }
}</node>

漏掉任意一处 updateHeight，后续 getBalanceFactor 就会失真。

高度更新与平衡因子计算：别信 cached height 字段

很多教程让节点缓存 height 字段，看似提升性能，实则埋雷——只要一次旋转或子树替换没同步更新，整棵树的平衡判断就全错。

更稳健的做法是：在 getBalanceFactor(node) 中实时计算，或仅在 updateHeight 被显式调用后才信任缓存值。推荐后者，并强制所有修改子指针的地方（如 rotateLeft、split、merge）末尾加 updateHeight：

rotateLeft(y) 后必须 updateHeight(y) 和 updateHeight(x)（x 是 y 的新父）
任何 node->left = ... 或 node->right = ... 赋值后，若该 node 非空，立刻 updateHeight(node)
updateHeight 必须写成 node->height = 1 + max(getHeight(node->left), getHeight(node->right))，其中 getHeight 对空指针返回 0