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

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

0 голосов
/ 17 февраля 2019

Этот вопрос похож на Сортированный список для завершения представления массива 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] - я в основном придумал этот термин «порядок уровней».Если вы знаете более широко признанный академический термин для этого заказа, пожалуйста, оставьте комментарий!

1 Ответ

0 голосов
/ 18 февраля 2019

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

В приведенном ниже коде C ++ используется алгоритм тэта (n log n) Faro shuffle / inverse shuffle, поскольку он проще, чем алгоритм Пейюша Джайна .Обратите внимание, что алгоритм Пейюша не может быть быстрее на реальном оборудовании для любого реалистического значения 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);
}
...