AVL树合并不能直接memcpy或swap指针，因会破坏BST性质和AVL平衡；须以中序前驱/后继为根递归合并，并每次更新高度与平衡；split需严格维护高度信息，update_height和balance_node必须安全处理空指针及子树BF。
AVL 树节点合并：为什么不能直接 memcpy 或 swap 指针
AVL 树的合并（merge）不是把两棵树根节点简单拼接，而是要求结果仍为 AVL 树，且保持中序遍历有序。常见错误是试图用 std::swap 交换左右子树指针后调用 rebalance —— 这会破坏 BST 性质，因为两棵树值域可能重叠。
正确做法是：取左树最大节点（inorder predecessor）或右树最小节点（inorder successor）作为新根，递归合并剩余部分。核心约束是：左树所有键
- 若
left_max->key key成立，可用join（一种 merge 的特例），时间复杂度 O(log n) - 否则必须先对右树按
left_max->key做split，得到right_left和right_right，再分别与左树合并 - 每次递归后必须调用
update_height和balance_node，仅靠一次顶层rebalance不够
AVL 树节点分裂：split 操作必须返回两个根，且不破坏高度信息
split(root, key) 要返回 std::pair：左子树含所有 ≤ key 的节点，右子树含所有 > key 的节点。关键陷阱是分裂过程中旋转会导致某一边高度突变，但返回前未更新父节点高度，导致后续 join 或插入失败。
实操建议：
- 递归 split 后，无论是否发生旋转，都必须显式调用
update_height(node)，不能依赖旋转函数内部更新（有些实现只更新被旋节点，漏掉祖父） - 若在某层发生右旋，原
root变成右子节点，则新左树根是root->right，但它的height值可能已过期，需立即重算 - 分裂边界处理：当
root == nullptr，返回{nullptr, nullptr}；当root->key == key，通常将root归入左树，并把root->right递归 split 后并入右树
AVL 合并与分裂共用的核心辅助函数：update_height 和 balance_node
update_height 看似简单，但它是所有平衡操作的可信基点。错误写法如 node->height = 1 + max(node->left->height, node->right->height) 会在子节点为 nullptr 时解引用空指针。
正确实现必须处理空指针：
int get_height(Node* n) {
return n ? n->height : 0;
}
void update_height(Node* n) {
if (n) n->height = 1 + std::max(get_height(n->left), get_height(n->right));
}
balance_node 不能只判断 bf = get_height(l) - get_height(r) 就决定旋转类型，还要检查子树的平衡因子以区分 LR/RL 情况：
- BF = 2 且
get_height(left->left) >= get_height(left->right)→ LL 旋转 - BF = 2 且
get_height(left->left) right)→ LR 旋转（先左旋 left，再右旋 root） - 同理处理 BF = -2 的 RR / RL
实际工程中应避免手写 merge/split：优先用 std::set + extract（C++17）
纯手写 AVL 的 merge 和 split 在真实项目中极少单独使用。它们逻辑密集、边界多、调试成本高，且 C++ 标准库已提供更稳健的替代路径。
例如，要合并两个有序集合：
- 若数据量不大（std::set::insert，均摊 O(log n) —— 简单、安全、可读性强
- 若需高性能合并且允许临时内存，用
std::vector提取两集合内容，std::inplace_merge，再重建std::set（O(n) 时间，O(n) 空间） - C++17 起，
std::set::extract可 O(1) 拆出节点，配合自定义分配器可模拟 split 行为，比手写 AVL 分裂更可靠
手写 AVL merge/split 真正适用的场景极窄：嵌入式无 STL、教学演示、或作为更复杂结构（如 order statistic tree）的底层组件。此时务必对每个指针操作加 assert(node != nullptr)，并在单元测试中覆盖 height=0/1/2 的全部旋转组合。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
