使用常数内存在O(n)时间复杂度下对二叉搜索树进行排序。

Question

使用常数内存在O(n)时间复杂度下对二叉搜索树进行排序。

arraysalgorithmsortingbinary-tree

15

这不是作业，只是一个有趣的问题 :)

给定一个用数组表示的完全二叉搜索树，在常数内存下以O(n)的时间复杂度对数组进行排序。

示例：

树：

              8
           /     \
          4       12
         /\       / \
        2  6     10  14
       /\  /\    /\   /\
      1 3 5  7  9 11 13 15

数组：8、4、12、2、6、10、14、1、3、5、7、9、11、13、15

输出结果：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15

- gtikok

它总是完美平衡的吗？ - astorcas

3

更好的是，它总是完整的。 - polygenelubricants

1

@NickLarsen：那个数组只是一个例子，我们不能从中推断出数字是1..N。无论如何，假设那样会让问题变得愚蠢。 - Aryabhatta

@I__: 你为什么要把这个标记为作业？此外，使用“元”标签现在已经不被赞同了：http://blog.stackoverflow.com/2010/08/the-death-of-meta-tags/ - Aryabhatta

顺便说一下，我真的很喜欢你的回答：http://stackoverflow.com/questions/2336054/find-pointers-from-pointee/2336070#2336070 - Alex Gordon

显示剩余5条评论

2个回答

2

思考一下O(1)的原地算法，但现在先给出O(N)的解法。

一个O(N)空间复杂度的解决方案：

如果你可以使用一个O(N)大小的输出数组，那么你可以简单地进行中序遍历。每次访问一个节点，就将它添加到输出数组中。

以下是Java实现代码：

import java.util.*;
public class Main {
    static void inorder(int[] bst, List<Integer> sorted, int node) {
        if (node < bst.length) {
            inorder(bst, sorted, node * 2 + 1);
            sorted.add(bst[node]);
            inorder(bst, sorted, node * 2 + 2);
        }
    }
    public static void main(String[] args) {
        int[] bst = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
        final int N = bst.length;
        List<Integer> sorted = new ArrayList<Integer>();
        inorder(bst, sorted, 0);
        System.out.println(sorted);
        // prints "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]"
    }
}

附件

在ideone.com上的源代码和输出

- polygenelubricants

1

由于它需要不断的内存，我认为不可能有一个输出数组。但是中序遍历当然是正确的方法。 - Janick Bernet

这还不够。排序后，数组本身应该也被排序。 - gtikok

@inflagranti：是的，这是O(n)空间复杂度。为什么不能有其他方法呢？实际上，可以看看我的答案，其中一个不是按顺序的。 - Aryabhatta

是的，我并不是说按顺序遍历是唯一正确的方法。但我认为通过按顺序遍历应该可以实现。 - Janick Bernet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

这是可能的，那些称其为作业的人可能还没有尝试解决它。

我们将以下内容用作子程序：

Given an array a1 a2 ... an b1 b2 .. bn, convert in O(n) time and O(1) space to

b1 a1 b2 a2 ... bn an

可以在这里找到解决方案: http://arxiv.org/abs/0805.1598

我们使用以下方式。

对于前2^(k+1)-2个元素进行如上交错，从k=1开始重复进行k=2,3等，直至超出数组的末尾。

例如，在您的数组中，我们得到（通过括号标识的交错集合）

 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15   
[ ][ ]

 4, 8, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15   (k = 1, interleave 2)
[        ][        ]  

 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15   (k = 2, interleave 6)
[                      ][                     ]

 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15   (k = 3, interleave 14)

因此，总时间为n + n/2 + n/4 + ... = O(n)。使用的空间为O(1)。

可以通过归纳证明这是有效的。