avl树节点合并与分裂操作均在o(log n)内完成：合并通过高度比较与旋转维持平衡；分裂沿路径递归分割并回溯修复；全程需更新平衡因子、严格处理指针安全与边界异常。
一、AVL树节点合并操作的核心实现
AVL树的节点合并指将两棵满足AVL性质的子树T1和T2，以及一个中间键值k，构造出一棵新的AVL树，使得T1中所有键值小于k，T2中所有键值大于k，且整棵树保持高度平衡。该操作需在O(log n)时间内完成，关键在于递归选取高度较高子树的根作为新根，并通过旋转调整平衡因子。
1、判断T1与T2的高度差：若|height(T1) − height(T2)| ≤ 1，则以k为根，T1为左子树、T2为右子树，直接计算新节点平衡因子并返回。
2、若height(T1) > height(T2) + 1：递归将T2与k合并入T1的右子树，得到临时子树R；随后对T1执行右旋或先左后右双旋，使其恢复AVL性质。
3、若height(T2) > height(T1) + 1：递归将T1与k合并入T2的左子树，得到临时子树L；随后对T2执行左旋或先右后左双旋，更新平衡因子并返回新根。
二、AVL树节点分裂操作的核心实现
分裂操作将一棵AVL树T按给定键值k划分为两棵AVL子树：左子树L包含所有键值小于k的节点，右子树R包含所有键值大于等于k的节点。该过程不破坏原有结构的平衡性，需沿查找路径向下递归分割，并在回溯时逐层修复平衡因子。
1、若T为空，令L = nullptr，R = nullptr，直接返回。
2、若T->key right为L′与R′，令L = T，L->right = L′，再对L执行平衡因子重算与必要旋转，R = R′。
3、若T->key ≥ k：递归分裂T->left为L′与R′，令R = T，R->left = R′，再对R执行平衡因子重算与必要旋转，L = L′。
三、平衡因子更新与旋转辅助函数实现
合并与分裂过程中，每次子树结构变动后必须立即更新节点平衡因子，并根据其值决定是否触发旋转。平衡因子定义为左子树高度减右子树高度，合法范围为{-1, 0, 1}。超出范围即需旋转修正。
1、定义get_height(node)函数：若node为空返回-1，否则返回node->height字段值。
2、定义update_balance(node)函数：node->balance = get_height(node->left) − get_height(node->right)。
3、当node->balance == 2且node->left->balance ≥ 0时，执行右单旋；当node->balance == 2且node->left->balance == −1时，执行先左后右双旋。
4、当node->balance == −2且node->right->balance ≤ 0时，执行左单旋；当node->balance == −2且node->right->balance == 1时，执行先右后左双旋。
四、合并与分裂的边界处理与内存安全保证
AVL树合并与分裂涉及频繁的指针重定向与节点复用，必须严格避免悬空指针、重复释放及未初始化访问。所有新建节点须显式初始化height与balance字段，所有删除节点前须置空其子指针并调用delete。
1、在合并入口处检查T1与T2是否为同一地址，若是则直接抛出逻辑错误异常，禁止自合并。
2、分裂操作中，若k等于某节点key，该节点及其右子树全部划入R，其左子树参与递归分裂；此时需确保原节点不再保留在L中。
3、每次旋转后，被旋转子树的根节点height字段必须依据子树高度重新计算：height = max(get_height(left), get_height(right)) + 1。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
