时间戳

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

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

问题描述

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

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

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

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

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

我也不知道如何处理第三种情况。

标签： arrayssortingdata-structurestime-complexityavl-tree

解决方案

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

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

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

  • isAtEnd - 如果您遍历了整个树，则返回 true
  • peek - 返回树中的当前项
  • 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;
}

推荐阅读