Балансировка BST

Справка: Меня попросили ответить на этот вопрос в интервью @MS SDE, в третьем раунде. И это не проблема домашней работы. Я также подумал и упомянул о моем подходе ниже.

Вопрос: Измените BST так, чтобы он стал как можно более сбалансированным. Разумеется, вы должны сделать это максимально эффективно.

Подсказка: Интервьюер сказал, что это логичный вопрос, если вы думаете по-другому, вы получите ответ. Не было сложного кодирования.
→ Сказав это, я не думаю, что он ожидал, что я укажу на деревья AVL/RB.

Мое решение: Я предложил, чтобы я сделал обход дерева, взял средний элемент в качестве корня нового дерева (давайте назовем его новым корнем). Затем перейдите в левую часть среднего элемента, возьмите его средний элемент как корень из левого поддерева корневого дерева с корнем. Точно так же для правой части. Выполнение этого рекурсивно даст оптимальный баланс BST.

Почему я размещаю его здесь: Но он не был доволен ответом: (Итак, есть ли способ сделать это без участия стратегии весов/RB-раскраски, или он просто обманывал меня? Пожалуйста, внесите свои мысли.

Duplicate? Нет! Я знаю, что это question, но предлагаемое реквестером решение слишком сложное, а другое говорит о деревьях AVL.

Ответы

Ответ 1

Возможно, вы захотите изучить алгоритм Day-Stout-Warren, который является O (n) -time, O ( 1) -пространственный алгоритм перестройки произвольного двоичного дерева поиска в полное двоичное дерево. Интуитивно алгоритм работает следующим образом:

  • Используя вращения дерева, преобразуйте дерево в вырожденный связанный список.
  • Применяя выборочные вращения к связанному списку, преобразуйте список обратно в полностью сбалансированное дерево.

Красота этого алгоритма заключается в том, что он работает в линейном времени и требует только постоянных издержек памяти; Фактически, он просто преобразует базовое дерево, а не создает новое дерево и копирует старые данные. Это также относительно просто для кодирования.

Надеюсь, это поможет!

Ответ 2

"Сбалансировано как можно" = полное (или полное) двоичное дерево 1. Вы не можете более уравновешивать это.

Решение прост - постройте "пустое" полное двоичное дерево и повторите новое дерево и дерево ввода (одновременно) в обходном пути, чтобы заполнить полное дерево.

Когда вы закончите, у вас будет самое сбалансированное дерево, которое вы можете получить, а временная сложность этого подхода - O(n).

EDIT:
Это должно быть сделано после следующих шагов:

  • Создайте фиктивное полное дерево с узлами n. Все значения для каждого node будет инициализирован некоторым значением мусора.
  • Создайте два итератора: (1) originalIter для исходного дерева, (2) newIter для нового дерева (инициализированного мусором). Оба итератора возвращают элементы в обход последовательности.

  • Сделайте следующее, чтобы заполнить дерево значениями из оригинала:

     while (originalIter.hasNext()):
      newIter.next().value = originalIter.next().value

(1) (из Википедии): Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы максимально удалены

Ответ 3

Алгоритм DSW может решить это время O (n). Алгоритм выглядит следующим образом:

1] Using right-rotation operations, turn the tree into a linked list
   (a.k.a. backbone or vine)
2] Rotate every second node of the backbone about its parent to turn
   the backbone into a perfectly balanced BST.

Ссылка