使用常量内存对O(n)中的BST进行排序

Question

这不是作业.只是一个有趣的任务:)

给出完整的二进制搜索三个由数组表示.使用常量内存在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

Answer 1

有可能,人们称之为功课可能还没有尝试解决它.

我们使用以下作为子例程:

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).

这可以通过归纳证明.