Лучший обход «порядка» для копирования сбалансированного бинарного дерева в дерево AVL с минимальными поворотами

Question

У меня есть два двоичных дерева. Один, A, к которому я могу получить доступ к его узлам и указателям (left, right, parent) и B, к которому у меня нет доступа ни к одному из его внутренних компонентов. Идея состоит в том, чтобы скопировать A в B путем итерации по узлам A и выполнения insert в B. B, являясь деревом AVL, существует ли обход A (предзаказ, порядок, порядок), чтобы при вставке элементов в B?

было минимальное количество поворотов Редактировать:

• Дерево A сбалансировано, я просто не знаю точную реализацию;
• Итерация по дереву A должна выполняться с использованием только указателей (язык программирования C и нет структуры данных очереди или стека, которую я мог бы использовать).

Answer 1

Если исходное дерево не обязательно AVL-сбалансировано, вы не можете просто скопировать его.

Чтобы гарантировать, что в новом дереве нет перебалансировки, вы должны создать complete двоичное дерево, и вы должны вставить узлы в порядке BFS / уровень, чтобы каждое промежуточное дерево также было завершено.

"Полное" дерево - это дерево, в котором каждый уровень заполнен, за исключением, возможно, последнего. Поскольку каждое полное дерево сбалансировано по AVL, а каждое промежуточное дерево завершено, повторная балансировка не требуется.

Если вы не можете скопировать исходное дерево в массив или другую структуру данных, то вы ' Вам нужно будет выполнить log (N) в порядке обхода исходного дерева, чтобы скопировать все узлы. Во время первого обхода вы выбираете и копируете root. Во время второго вы выбираете и копируете уровень 2. Во время третьего вы копируете уровень 3 и т. Д. c.

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

Поскольку каждый обход занимает O (N) времени, общее время, потраченное на обход, составляет O (N log N). Однако, поскольку вставки занимают O (log N) времени, это то же самое, что и вставка, поэтому обходы журнала N не увеличивают сложность всего процесса.

Answer 2

Перебалансировка в AVL происходит, когда глубина одной части дерева превышает глубину какой-либо другой части дерева более чем на единицу. Таким образом, чтобы избежать запуска перебалансировки, вы хотите подавать узлы в дерево AVL по одному уровню за раз; то есть, кормите все узлы с уровня N исходного дерева, прежде чем кормите его любым узлом с уровня N + 1.

. Это упорядочение будет достигнуто путем обхода оригинала в ширину tree.

---

Редактировать

OP добавлено:

Итерация по дереву A должна выполняться только с помощью указателей (программирование язык - C, и нет никакой структуры данных очереди или стека, которую я мог бы использовать).

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

Он влияет на то, как вы будете реализовывать обход в ширину. Если вы не можете использовать предопределенную очередь, то есть несколько способов реализовать собственную очередь в C: массив, если это разрешено, или некоторое разнообразие связанного списка - очевидный выбор.

Если Вы не можете использовать динамическое выделение памяти c, а размер исходного дерева не ограничен, так что вы можете построить очередь, используя фиксированный буфер, размер которого наихудший, а затем вы можете отказаться от очереди. основанный подход и вместо этого использовать рекурсию, чтобы посетить последовательно более глубокие уровни дерева. (Представьте себе рекурсивный обход, который останавливается, когда он достигает указанной глубины в дереве, и выдает результат только для узлов на этой указанной глубине. Оберните эту рекурсию в while или for l oop, который выполняется с глубины от нуля до максимальной глубины дерева.)