Разделите дерево на равные части, удалив ребро

Question

Я ищу алгоритм для разбиения дерева с N узлами (где максимальная степень каждого узла равна 3), удаляя из него одно ребро, чтобы два дерева, полученные в результате, были как можно ближе кN / 2.Как найти ребро, которое является «наиболее центрированным»?

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

Моя идея - найти самый длинный путь в дереве, а затем выбрать ребро в середине самого длинного пути.Работает ли это?

Оптимально, я ищу решение, которое гарантировало бы, что ни одно из деревьев не имеет более 2N / 3 узлов.

Спасибо за ваши ответы.

Answer 1

Я не верю, что ваш первоначальный алгоритм работает по той причине, о которой я упоминал в комментариях. Тем не менее, я думаю, что вы можете решить это за O (n) время и пространство, используя модифицированный DFS.

Начните с обхода графика, чтобы подсчитать, сколько всего узлов; назовите это n. Теперь выберите произвольный узел и создайте для него корень дерева. Теперь мы будем рекурсивно исследовать дерево, начиная с корня, и вычислим для каждого поддерева, сколько узлов в каждом поддереве. Это можно сделать с помощью простой рекурсии:

• Если текущий узел пуст, вернуть 0.
• В противном случае:
  • Для каждого дочернего элемента вычислите количество узлов в поддереве с корнем этого дочернего элемента.
  • Возвращает 1 + общее количество узлов во всех дочерних поддеревьях

В этот момент мы знаем для каждого ребра, какое разделение мы получим, удаляя это ребро, поскольку, если поддерево ниже этого ребра имеет в себе k узлов, разлив будет (k, n - k). Таким образом, вы можете найти лучший отрезок, чтобы выполнить итерацию по всем узлам и найти тот, который уравновешивает (k, n - k) наиболее равномерно.

Подсчет узлов занимает время O (n), а выполнение рекурсии посещает каждый узел и ребро не более O (1) раз, так что также требуется время O (n). Нахождение лучшего среза занимает дополнительное время O (n), а чистая продолжительность выполнения O (n). Поскольку нам нужно хранить количество узлов поддерева, нам также понадобится O (n) памяти.

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

Answer 2

Если вы видите мой ответ на Алгоритм «разделяй и властвуй» для деревьев , вы увидите, что я найду узел, который разбивает дерево на 2 почти равных по размеру дерева (алгоритм снизу вверх), теперь выпросто нужно выбрать один из краев этого узла, чтобы сделать то, что вы хотите.

Ваш текущий подход не работает, если у вас есть полное двоичное дерево, теперь добавьте путь длины 3*log n к одному из листьев(назовите его bad лист), ваш самый длинный путь будет в пределах одного из других листьев до конца пути, соединенного с этим bad листом, и ваш средний край будет в этом пути (фактически после того, как вы прошли плохой лист) и если вы разделите базу на этом ребре, у вас будет часть O(log n) и другая часть размером O(n).