C++ 实现二叉平衡树 AVL 的节点合并与分裂算法逻辑

AVL树节点合并不能直接memcpy或链表拼接，因其必须同时维持BST性质、节点高度（height）和平衡因子（bf）三重约束；若仅拼接而未更新height、回溯rebalance、修正parent指针及旋转后节点高度顺序，则必然导致失衡、高度错乱或BST破坏。

c++ 实现二叉平衡树 avl 的节点合并与分裂算法逻辑 _ 源码【源码】

AVL 树节点合并：为什么不能直接 memcpy 或链表拼接

AVL 树的合并不是把两棵树头尾一接就完事——合并后必须维持 height、balance factor 和 BST 性质三重约束。常见错误是写个 merge(root1, root2) 函数，却没考虑：哪棵树的所有节点都小于另一棵？是否已知 root1 的最大值 root2 的最小值？若无此前提，直接合并必然破坏 BST 结构。

真正可用的合并需满足前提：两棵 AVL 树 A 和 B，且 A 中所有键 max(A) ）。此时可构造新根节点，左子树为 A、右子树为 B，再递归更新高度并做必要旋转。

不要尝试在原地修改两棵树的指针来“缝合”，这会破坏各自平衡性
合并后的新根高度为 max(height(A), height(B)) + 1，但 balance factor 可能为 ±2，必须调用 rebalance()（即四种旋转的统一封装）
时间复杂度不是 O(1)，而是 O(|h₁ − h₂|)，因为只需从新根向下最多调整一层不平衡点

AVL 树节点分裂：split(key) 返回左右两棵子树的正确姿势

分裂操作常被误认为“找到 key 后砍一刀”，但 AVL 要求分裂后左右两棵树各自仍是合法 AVL 树。关键在于：不能只按 key 值切开，而要沿搜索路径做“带平衡的拆解”——每经过一个节点，根据 key 与当前节点值关系，决定该节点及其某子树归属左/右结果，并在回溯时对参与分裂的子树重新平衡。

典型实现用递归 split(node, key)，返回 pair，语义为：first 是所有 ≤ key 的节点构成的 AVL 树，second 是所有 > key 的节点构成的 AVL 树。

若 node == nullptr，直接返回 {nullptr, nullptr}
若 key key，则当前节点及其右子树全归右结果，对左子树递归 split(left, key)，再把返回的左部分和当前节点组装成新左树，并调用 rebalance()
若 key >= node->key，对称处理：当前节点及左子树归左结果，递归分裂右子树
漏掉回溯时的 updateHeight() 和 rebalance()，会导致分裂后树高错乱或失衡

rebalance() 实现中四个旋转函数的触发条件与指针修正细节

很多人写出 LL、RR、LR、RL 四个旋转函数，但调用逻辑出错：不是看当前节点 balance factor 就决定旋转类型，而是要看**失衡节点的较高子树的更高子树方向**。例如 balance factor = 2（左高），还需检查 node->left->balance：若为 1，是 LL；若为 -1，才是 LR。

C++14

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

下载

旋转本身不难，难在旋转后三个节点（原根、新根、孙子）的 height 必须立即更新，且顺序不能错——必须先更新最深层节点，再向上更新。否则 height 计算错误，后续判断还会误触发旋转。

LL 旋转后：新根（原左子）高度 = max(height(left->left), height(left->right)) + 1；原根高度 = max(height(original->left), height(original->right)) + 1
所有旋转中，parent 指针（如有）必须同步修正；若用裸指针实现，旋转后需显式赋值 newRoot->parent = oldParent 等
别在旋转函数里调用 rebalance() 自己——这是死循环起点

实际工程中更推荐跳过手写 split/merge，改用 std::set + extract（C++17）

除非教学或嵌入式极端受限场景，否则不建议在生产代码中手写 AVL 的 split/merge。C++17 的 std::set::extract() 已提供 O(log n) 拆出单个节点的能力，配合 std::set::merge()（C++17）可实现集合级合并，底层虽非 AVL 但红黑树同样保证 O(log n) 和有序性，且经充分测试。

若真需基于 key 范围分裂，可用两次 lower_bound 定位区间，再用 extract 配合循环搬移节点——虽然略慢于理论最优 AVL 分裂，但稳定、无内存泄漏风险、不依赖自定义平衡逻辑。