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

AVL节点合并不能直接拼接左右子树，因会破坏高度差约束（bf=height(left)−height(right)∈{−1,0,1}），导致后续旋转判断失效；必须构造新根、重算height、自底向上rebalance并正确处理旋转后指针与高度更新。

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

因为 AVL 树的平衡性依赖于每个节点的 height 和左右子树高度差（bf = height(left) - height(right)），直接拼接会破坏高度信息和平衡因子，导致后续 rotate 判断失效。合并必须从底层向上重建高度，并在回溯路径上逐层检查并修复平衡。

常见错误现象：segmentation fault 出现在旋转后访问空指针，或 bf 突然变成 ±3 —— 这说明某次合并后没更新 height，后续旋转基于错误高度计算，转错了方向或转过了头。

合并操作本质是“构造新根 + 递归合并子树”，不是 root->left = left_tree; root->right = right_tree;
必须重算新根的 height：node->height = 1 + max(height(node->left), height(node->right));
合并后需从新根开始调用 rebalance()，不能只靠单次旋转——连续失衡可能跨多层

分裂不是简单按值切开，而是以某个键 k 为界，把原树拆成两棵：左树所有键 ，右树所有键 <code>>= k。关键在于分裂过程本身会扰动路径上所有祖先的高度和平衡因子，必须边分裂边修复。

使用场景：实现可持久化集合、区间查询分治、或配合 merge 实现更高级的平衡树（如 Treap 变种）。

分裂函数签名通常为：pair<avlnode avlnode> split(AVLNode* root, int k)</avlnode>
若 root == nullptr，直接返回 {nullptr, nullptr}；否则根据 root->val 与 k 关系决定向哪边递归分裂，并把当前节点挂到对应结果子树的“最边位置”（左分裂时挂右子树最左，右分裂时挂左子树最右）
每次递归返回后，必须立即对当前 root 调用 update_height() 和 rebalance()，否则父层分裂拿到的是失衡子树
分裂不改变原始树结构，但返回的两个子树是全新拓扑——别试图复用原节点指针而不更新其 height

AVL 的四种旋转（LL、RR、LR、RL）由失衡节点的 bf 和其子节点的 bf 共同决定，但新手常错在：判断 bf 前没更新子树高度，或旋转后忘了重设参与旋转节点的 height。

C++14

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

下载

典型错误：LLRotate 后 new_root->height 正确，但漏了 old_root->height，下一次对该节点的 bf 计算就出错。

bf == 2 && get_bf(root->left) >= 0 → LL；bf == 2 && get_bf(root->left) → LR
bf == -2 && get_bf(root->right) → RR；<code>bf == -2 && get_bf(root->right) > 0 → RL
所有旋转函数末尾必须显式调用 update_height() 更新涉及的两个节点（例如 LLRotate 中的 old_root 和 new_root）
不要在 rebalance() 外层缓存 get_bf() 结果——子树可能已被旋转修改，必须实时读取

当你用 split 得到两棵树，再用 merge 把它们和一个新节点组合，看似自然，但 C++ 中节点指针所有权极易混乱：谁该 delete？临时树是否意外释放了还在用的节点？

性能影响：频繁 new/delete 会拖慢速度，而全用栈对象又无法支持任意深度递归分裂。

推荐统一用智能指针（std::unique_ptr<avlnode></avlnode>），让 merge 和 split 移动所有权而非裸指针交接
如果坚持裸指针，merge(AVLNode* a, AVLNode* b) 必须明确约定：a、b 的所有权移交至 merge 内部，调用方不得再访问原指针
分裂返回的 pair 中两个指针互斥——绝不能把左树的某个节点再塞进右树，AVL 不允许重复节点，也不允许交叉引用
测试时务必覆盖边界：空树 merge、单节点 split、重复键插入后分裂——这些场景最容易暴露 height 未更新或旋转方向反了

真正难的不是写出四类旋转，而是确保每次高度更新都发生在正确时机、每个指针的生命周期都被清晰约束。一旦漏掉一次 update_height() 或误判了一次 bf 符号，整棵树就 quietly 失衡了，debug 时得靠打印整棵树的 val/height/bf 三元组才看得清。