Я ищу наиболее эффективный алгоритм, чтобы взять дерево (хранится как список ребер; ИЛИ как список отображений из родительского узла в список дочерних узлов); и создайте для КАЖДОГО узла список всех узлов, произошедших от него (конечный уровень и не конечный уровень).
Реализация должна быть с помощью циклов вместо повторения, из-за масштаба; и в идеале должно быть O (N).
Этот вопрос SO охватывает стандартное достаточно очевидное решение для поиска ответа для ОДНОГО узла в дереве. Но, очевидно, повторение этого алгоритма на каждом узле дерева крайне неэффективно (от вершины моей головы, от O (NlogN) до O (N ^ 2)).
Корень дерева известен. Дерево имеет абсолютно произвольную форму (например, не является N-ным, не сбалансировано каким-либо образом, имеет форму или форму, не имеет одинаковой глубины) - в некоторых узлах есть 1-2 дочерних элемента, в некоторых - 30 тыс. Дочерних элементов
На практическом уровне (хотя это не должно влиять на алгоритм) дерево имеет ~ 100K-200K узлов.
источник
Ответы:
Если вы действительно хотите ПРОИЗВОДИТЬ каждый список в виде разных копий, вы не можете надеяться, что в худшем случае вы получите пробел, превосходящий n ^ 2. Если вам просто нужен доступ к каждому списку:
Я бы выполнил обход дерева по порядку, начиная с корня:
http://en.wikipedia.org/wiki/Tree_traversal
Затем для каждого узла в дереве сохраните минимальный порядковый номер и максимальный порядковый номер в своем поддереве (это легко поддерживается с помощью рекурсии - и вы можете смоделировать это с помощью стека, если хотите).
Теперь вы помещаете все узлы в массив A длины n, где узел с порядковым номером i находится в позиции i. Затем, когда вам нужно найти список для узла X, вы смотрите в A [X.min, X.max] - обратите внимание, что этот интервал будет включать в себя узел X, который также можно легко исправить.
Все это выполняется за O (n) время и занимает O (n) пространство.
Надеюсь, это поможет.
источник
Неэффективная часть - это не обход дерева, а построение списков узлов. Казалось бы, разумно создать такой список:
Поскольку каждый узел-потомок копируется в список каждого родителя, мы получаем в среднем O (n log n) сложности для сбалансированных деревьев и O (n²) наихудший случай для вырожденных деревьев, которые действительно связаны списками.
Мы можем перейти к O (n) или O (1) в зависимости от того, нужно ли вам выполнять какую-либо настройку, если мы используем ленивый способ вычисления списков. Предположим,
child_iterator(node)
что у нас есть дочерние элементы этого узла. Затем мы можем определить тривиальноdescendant_iterator(node)
:Нерекурсивное решение намного сложнее, поскольку управление итератором является сложным (сопрограммы!). Я обновлю этот ответ позже сегодня.
Поскольку обход дерева - это O (n) и итерация по списку также линейна, этот трюк полностью откладывает стоимость до тех пор, пока она не будет оплачена. Например, распечатка списка потомков для каждого узла имеет O (n²) сложность в наихудшем случае: перебор всех узлов равен O (n) и, следовательно, перебор всех потомков каждого узла, независимо от того, хранятся ли они в списке или вычисляются по запросу ,
Конечно, это не сработает, если вам нужна фактическая коллекция для работы.
источник
Этот короткий алгоритм должен сделать это, посмотрите на код
public void TestTreeNodeChildrenListing()
Алгоритм фактически последовательно проходит через узлы дерева и ведет список родителей текущего узла. Согласно вашему требованию текущий узел является дочерним для каждого родительского узла, который добавляется к каждому из них как дочерний.
Конечный результат сохраняется в словаре.
источник
Обычно вы просто используете рекурсивный подход, поскольку он позволяет вам переключать порядок выполнения так, чтобы вы могли вычислить количество листьев, начиная с листьев вверх. Поскольку для обновления текущего узла вам потребуется использовать результат вашего рекурсивного вызова, потребуется специальное усилие для получения хвостовой рекурсивной версии. Если вы не предпримете это усилие, тогда, конечно, этот подход просто взорвет ваш стек для большого дерева.
Учитывая, что мы поняли, что основная идея состоит в том, чтобы получить порядок зацикливания, начинающийся с листьев и возвращающийся обратно к корню, естественная идея, которая приходит в голову, - выполнить топологическую сортировку дерева. Результирующая последовательность узлов может проходить линейно, чтобы суммировать количество листьев (при условии, что вы можете проверить, является ли узел листом
O(1)
). Общая временная сложность топологического вида равнаO(|V|+|E|)
.Я предполагаю, что ваше
N
число узлов, которое|V|
обычно (из номенклатуры DAG). РазмерE
с другой стороны сильно зависит от арности вашего дерева. Например, двоичное дерево имеет не более 2 ребер на узел, поэтомуO(|E|) = O(2*|V|) = O(|V|)
в этом случае это приведет к общемуO(|V|)
алгоритму. Обратите внимание, что из-за общей структуры дерева у вас не может быть чего-то подобногоO(|E|) = O(|V|^2)
. Фактически, поскольку каждый узел имеет уникального родителя, вы можете иметь не более одного ребра для подсчета на узел, когда вы рассматриваете только родительские отношения, поэтому для деревьев у нас есть гарантия того, чтоO(|E|) = O(|V|)
. Поэтому приведенный выше алгоритм всегда линейен по размеру дерева.источник