找到对以数组和 AVL 树形式组织的数据进行排序的最佳解决方案

Question

这是我在数据结构考试中遇到的练习题。我们想从两组大小为 n 的数字 A 和 B 中得到排序后的整数序列。

A 和 B 组织成未排序的数组。
A 和 B 组织成数组，其中只有第一个排序。
A 和 B 被组织成 AVL 树。

在每种情况下，我都希望将结果存储在另一个大小为 2*n 的数组 C 中。

对于第一种情况，我认为只需将所有元素复制到第二个数组中，这将花费 O(2n)，然后使用快速排序将它们全部排序在一起，这将花费 O(2nlog2n)。

对于第二种情况，有没有更快的方法，还是我应该像以前一样将它们全部复制并排序？

第三种情况我也不知道怎么办。

Answer 1

你的解是渐近最优的。
原地排序B。然后将两个列表简单合并到最终列表中。复杂度是 O(n log n) 排序 B 数组，O(2n) 合并。
开始对两棵树进行非递归中序遍历，使用显式堆栈来维护状态，并合并到单个输出数组中。复杂度为 O(2n).

非递归中序树遍历见https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

基本上，您修改该代码以创建具有以下方法的 tree_traversal class：

isAtEnd - returns如果你遍历了整棵树，则为真
查看 - returns 树中的当前项目
next - 移动到树中的下一个项目

实例化每棵树的中序遍历，然后进行标准的合并。类似于：

a = new int[2*n]; // allocate output array
ix = 0; // output index
t1 = new tree_traversal(tree_a);
t2 = new tree_traversal(tree_b);
while (!t1.isAtEnd() && !t2.isAtEnd())
{
    if (t1.peek() < t2.peek())
    {
        a[ix] = t1.peek();
        t1.next();
    }
    else
    {
        a[ix] = t2.peek();
        t2.next();
    }
    ++ix;
}
// at this point, you've reached the end of one tree
// empty the other
while (!t1.isAtEnd())
{
    a[ix] = t1.peek();
    t1.next();
    ++ix;
}
while (!t2.isAtEnd())
{
    a[ix] = t2.peek();
    t2.next();
    ++ix;
}

找到对以数组和 AVL 树形式组织的数据进行排序的最佳解决方案

Find the most optimal solution for sorting data organized in arrays and in AVL trees

arrays

sorting

data-structures

time-complexity

avl-tree