从完整二叉搜索树顺序转换为排序顺序的算法，反之亦然

Question

这个问题类似于Sorted list to complete BST array representation但也许更具体地集中。这个问题可以用来解决Inserting node dynamically in Complete Binary Search Tree .

考虑 complete binary tree在内存中表示为连续数组 a[0..n)，其中元素 a[0] 是树的根，并且对于任何节点 a [i]，它有左子 a[2*i+1] 和右子 a[2*i+2] (如果这些索引是小于n)。

C++ 程序员会熟悉这种表示形式，因为 std::make_heap 使用它。 。 std::make_heap(a, a+n) 接受一个未排序的数组(可以将其视为未排序的完整二叉树)并排列其元素(可以将其视为树旋转)以将树变成完整的二叉树 heap其中每个节点的值都大于其子节点的值。我们说结果数组是“最大堆顺序”。

另一方面，如果每个节点的值大于其左子节点但小于其右子节点，则我们说完全二叉树是完全二叉搜索树。在这种情况下，假设结果数组是“级别顺序”。^[1]

虽然给定的元素集有许多允许的“最大堆顺序”，但每个元素集只有一个唯一的“级别顺序”。

以下向量按级别顺序排列:

std::vector<int> v1 = { 3, 1, 4, 0, 2 };

// corresponds to the complete binary search tree
//    3
//  1   4
// 0 2

std::vector<int> v2 = { 6, 3, 8, 1, 5, 7, 9, 0, 2, 4 };

// corresponds to the complete binary search tree
//        6
//    3       8
//  1   5   7   9
// 0 2 4

我正在寻找一系列有效的算法，用于:

1. 将未排序的序列排列为级别顺序
2. 将排序序列排列为级别顺序
3. 将级别顺序序列排列为排序顺序

当我说高效时，我指的是无需深度递归、无需动态内存分配、无需临时数组即可工作的算法。我已经知道排列不能特别快地完成；我希望 O(n lg n)。

请注意，第 2 部分和第 3 部分基本上要求提出一个映射 OldIndex -> NewIndex；一旦你有了这样的函数，你就可以使用 one of these algorithms 就地进行排列。 .

第 1 部分要求实现 nonstd::make_searchtree 类比 std::make_heap 。第 3 部分要求实现 nonstd::sort_searchtree 类比 std::sort_heap .

---

[1] — 我基本上创造了“级别顺序”这个术语。如果您知道此顺序的更广泛认可的学术术语，请发表评论!

Answer 1

我们可以得到 1 的 Theta(n log n) 时间算法和 2 和 3 的线性时间算法，如下所示。对于 1，我们排序并应用 2。对于 2，我们使用逆 Faro shuffle并进行旋转以使叶子到达数组的末尾，然后在删除叶子的子树上“递归”(尾递归，因此它实际上只是一个 for 循环)。对于 3，我们以相反的顺序执行 2 的逆步骤。

下面的 C++ 代码使用 Theta(n log n) Faro 洗牌/逆洗牌算法，因为它比 Peiyush Jain's algorithm 更容易。请注意，对于任何实际的 n 值，Peiyush 的算法在实际硬件上可能不会更快，因为其缓存利用率较差。

我已经在一个输入上测试了下面的代码。特此警告您。

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

namespace {

// Transforms [a0 b0 a1 b1 ... an-1 bn-1 an] to [a0 a1 ... an b0 b1 ... bn-1]
// and returns an iterator to b0. The running time is Theta(n log n). If you're
// feeling ambitious, you could try Peiyush Jain's linear-time algorithm.
template <typename RandomAccessIterator>
RandomAccessIterator InvertFaroShuffle(RandomAccessIterator first,
                                       RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits<RandomAccessIterator>::difference_type;
  Index size = last - first;
  assert((size & 1) == 1);
  if (size == 1) {
    return last;
  }
  RandomAccessIterator middle = first + (((size + 1) >> 2) << 1);
  return std::rotate(InvertFaroShuffle(first, middle - 1), middle,
                     InvertFaroShuffle(middle, last));
}

// Theta(n log n)-time algorithm for #2.
template <typename RandomAccessIterator>
void SortedToLevelOrder(RandomAccessIterator first, RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits<RandomAccessIterator>::difference_type;
  Index size = last - first;
  if (size <= 1) {
    return;
  }
  unsigned height = 1;
  while ((Index{2} << height) - 1 < size) {
    height++;
  }
  for (unsigned level = height; level > 0; level--) {
    Index effective_size = std::min((Index{2} << level) - 1, size);
    Index leaf_count =
        std::min(Index{1} << level, size - ((Index{1} << level) - 1));
    InvertFaroShuffle(first, first + 2 * leaf_count - 1);
    std::rotate(first, first + leaf_count, first + effective_size);
  }
}

// Theta(n log n)-time algorithm for #1.
template <typename RandomAccessIterator>
void UnsortedToLevelOrder(RandomAccessIterator first,
                          RandomAccessIterator last) {
  std::sort(first, last);
  SortedToLevelOrder(first, last);
}

// Transforms [a0 a1 ... an b0 b1 ... bn-1] to [a0 b0 a1 b1 ... an-1 bn-1 an].
// The running time is Theta(n log n). If you're feeling ambitious, you could
// try Peiyush Jain's linear-time algorithm.
template <typename RandomAccessIterator>
void FaroShuffle(RandomAccessIterator first, RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits<RandomAccessIterator>::difference_type;
  Index size = last - first;
  assert((size & 1) == 1);
  if (size == 1) {
    return;
  }
  Index half = (size + 1) >> 1;
  RandomAccessIterator middle = first + half;
  Index quarter = half >> 1;
  middle = std::rotate(first + quarter, middle, middle + quarter);
  FaroShuffle(first, middle - 1);
  FaroShuffle(middle, last);
}

// Theta(n log n)-time algorithm for #3.
template <typename RandomAccessIterator>
void LevelOrderToSorted(RandomAccessIterator first, RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits<RandomAccessIterator>::difference_type;
  Index size = last - first;
  if (size <= 1) {
    return;
  }
  unsigned height = 1;
  while ((Index{2} << height) - 1 < size) {
    height++;
  }
  for (unsigned level = 1; level < height + 1; level++) {
    Index effective_size = std::min((Index{2} << level) - 1, size);
    Index leaf_count =
        std::min(Index{1} << level, size - ((Index{1} << level) - 1));
    std::rotate(first, first + (effective_size - leaf_count),
                first + effective_size);
    FaroShuffle(first, first + 2 * leaf_count - 1);
  }
}

void PrintList(const std::vector<int>& list) {
  for (int elem : list) {
    std::cout << ' ' << elem;
  }
  std::cout << '\n';
}

}  // namespace

int main() {
  std::vector<int> list(10);
  std::iota(list.begin(), list.end(), 0);
  PrintList(list);
  SortedToLevelOrder(list.begin(), list.end());
  PrintList(list);
  LevelOrderToSorted(list.begin(), list.end());
  PrintList(list);
}