如何实现两棵自平衡BST的节点插入合并（禁止展平为有序数组）

• 缺失核心选择逻辑：需求要求先比较两棵树高度，将高度更小的树节点插入另一棵树，现有代码硬编码把tree1所有节点插入tree2，完全没有高度判断步骤，当tree1高度远大于tree2时会产生大量冗余插入操作，时间复杂度极差。
• 未处理自平衡BST的根节点变更：节点带height字段说明这是AVL树结构的自平衡BST，插入节点触发旋转调整时，树的根节点地址可能发生变化。C语言指针是值传递，现有代码直接传入一级指针tree2调用insert，insert内部如果因为旋转更换了根节点，外层的tree2指针完全不会被更新，直接丢失新根地址，导致树结构损坏、非法内存访问，这是函数无法正常运行的核心原因。
• 原函数用void作为返回值本身设计不合理：合并过程中目标树可能因为旋转更换根节点，没有返回值或输出参数的话，调用者无法拿到合并后的正确根地址。
• （健壮性问题）原代码遍历完源树节点后没有释放源树内存，会产生内存泄漏。

实现完全遵守要求：不将树展平为有序数组，遍历源树节点过程中直接执行插入，无额外数组存储节点值；优先选择高度更小的树作为插入源，保证插入效率；适配自平衡BST插入后根节点变更的特性。
首先补一个简单的高度获取辅助函数，统一处理空树的高度取值（和常规AVL树约定一致，空树高度为-1，不影响高度比较逻辑）：

// 辅助函数：获取树的实际高度
static inline int get_tree_height(struct node* root) {
    return root == NULL ? -1 : root->height;
}

然后写内部遍历插入的辅助函数，递归遍历源树节点逐点插入目标树，全程不生成有序数组：

// 内部辅助：遍历源树所有节点插入目标树，不使用数组暂存节点
static void traverse_insert(struct node* src_root, struct node** dest_root_ptr) {
    if (src_root == NULL) {
        return;
    }
    // 采用和原代码一致的中序遍历，前/中/后序遍历不影响最终插入结果
    traverse_insert(src_root->left_node, dest_root_ptr);
    // 插入节点，同步更新目标树根指针（适配自平衡旋转换根的场景）
    // 注：自平衡BST的C实现常规设计为insert返回调整后的新根，如果你的insert是二级指针传参版本，对应修改传参即可
    *dest_root_ptr = insert(*dest_root_ptr, src_root->value);
    traverse_insert(src_root->right_node, dest_root_ptr);

    // 可选：插入完成后释放源树节点，避免内存泄漏
    free(src_root);
}

最后是对外的合并入口函数，先比较两棵树高度，选择矮树作为插入源：

// 合并入口，返回合并完成后的树的根节点
struct node* merge(struct node* tree1, struct node* tree2) {
    int h1 = get_tree_height(tree1);
    int h2 = get_tree_height(tree2);

    if (h1 <= h2) {
        // tree1更矮，将tree1节点全部插入tree2
        traverse_insert(tree1, &tree2);
        return tree2;
    } else {
        // tree2更矮，将tree2节点全部插入tree1
        traverse_insert(tree2, &tree1);
        return tree1;
    }
}

补充说明：如果你当前的insert函数是无返回值、仅接收一级指针的实现，那这个insert本身存在设计缺陷——它无法在根节点触发旋转时把新根地址传递给外层，单节点插入场景就会出问题，需要先把insert修改为返回新根、或接收二级指针的形式，才能正常配合自平衡逻辑工作。

内容的提问来源于stack exchange，提问作者user19446449