Алгоритмы преобразования порядка полного бинарного дерева поиска в отсортированный порядок и наоборот

Question

Этот вопрос похож на Сортированный список для завершения представления массива BST, но, возможно, более конкретно. Этот вопрос можно использовать для динамического решения проблемы вставки узла в полное дерево двоичного поиска.

Рассмотрим полное двоичное дерево, представленное в памяти как непрерывный массив 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) берет несортированный массив (который можно рассматривать как несортированное полное двоичное дерево) и переставляет его элементы (которые можно рассматривать как повороты дерева), чтобы превратить дерево в полную двоичную кучу, где значение каждого узла больше, чем любой из его дочерних элементов. Мы говорим, что результирующий массив находится в "порядке максимальной кучи".

С другой стороны, если значение каждого узла больше, чем его левый потомок, но меньше, чем его правый потомок, то мы говорим, что полное двоичное дерево является полным двоичным деревом поиска. В этом случае предположим, что результирующий массив находится в "порядке уровня". ^[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; Если у вас есть такая функция, вы можете выполнить перестановку на месте, используя один из этих алгоритмов.

Часть 1 просит об осуществлении nonstd::make_searchtree по аналогии с std::make_heap, Часть 3 просит об осуществлении nonstd::sort_searchtree по аналогии с std::sort_heap,

---

[1] - Я в основном придумал этот термин "уровень порядка". Если вы знаете более широко признанный академический термин для этого заказа, пожалуйста, оставьте комментарий!

Answer 1

Мы можем получить алгоритм тета (n log n) времени для 1 и алгоритм линейного времени для 2 и 3 следующим образом. Для 1 мы сортируем и применяем 2. Для 2 мы используем обратное перемешивание Фаро и вращение, чтобы получить листья до конца массива, затем "recurse" (хвостовая рекурсия, так что это фактически просто цикл for) на поддерево с удаленными листьями. Для 3 мы делаем обратные шаги 2 в обратном порядке.

Приведенный ниже код C++ использует алгоритм тэта (n log n) Фаро в случайном порядке / обратного перемешивания, поскольку он проще, чем алгоритм Пейюша Джайна. Обратите внимание, что алгоритм Пейюша не может быть быстрее на реальном оборудовании для любого реалистического значения n из-за его плохого использования кэша.

Я проверил код ниже буквально на одном входе. Настоящим вас предупреждают.

#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);
}