Оптимальное решение для обхода дерева и суммирования значений узлов при условии

Question

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

То, что я хочу сделать, это пройти дерево, и для каждого узла я хочу суммировать значения из всех узлов-потомков, кроме потомков с более низким рангом и всех узлов под ними (независимо от ранга).Дерево не имеет специальных свойств, так как каждый узел может иметь <0, Integer.MAX_VALUE> дочерних элементов.Не существует правил, применяемых к отношениям между родителем и детьми в отношении ранга или значения.

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

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

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

Answer 1

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

Вот алгоритм времени O (n log n) с динамическими деревьями .(Я знаю. Их очень трудно реализовать. Я стараюсь не включать их в ответы.)

Сортировка узлов по наибольшему и наименьшему ранжированию и инициализация полностью отключенного динамического дерева с их значениями.Для каждого упорядоченного узла выполните динамические древовидные операции для

1. Сообщите его текущее значение (O (log n), амортизируйте, выведите это значение в конце концов) и
2. Если это не кореньдобавьте его значение к каждому из значений его предков (O (log n) амортизируется), а затем свяжите его со своим родителем (также O (log n) амортизируется).

Эффект шага 2является то, что динамическое значение каждого узла является суммой исходных значений его потомков (относительно текущего дерева).

Answer 2

Позвольте a, b, c быть узлами.Предположим, что a является предком или b, а b является предком c.

Обратите внимание: если b.rank > c.rank и a.rank > b.rank, то a.rank > c.rank.Это приводит нас к выводу, что sum_by_rank из a равен сумме sum_by_rank(b) + b.value для каждого b прямого потомка a, имеющего ранг ниже a.

Это предполагает следующую рекурсию:

ComputeRank(v)
    if v is null
       return

    let sum = 0
    foreach child in v.children
        ComputeRank(child)
        if child.rank <= v.rank 
            sum += child.sumByRank + child.value

    v.sumByRank = sum

К концу алгоритма у каждого узла будет sumByRank, как вам требуется (если я правильно понял).Обратите внимание, что для каждого узла n во входном дереве алгоритм посетит n ровно один раз и запросит его еще раз при посещении своего предшественника.Это постоянное число раз, означающее, что алгоритм займет O(N) времени.

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

Answer 3

Я предлагаю вам постфиксный DFS.Для каждого узла сохраните ссылку своего предшественника.

• sum_by_rank для листа - это пустой dict;
• sum_by_rank для любого узла - это dict ranks of all subnodes -> values of all subodes.Если два или более подузлов имеют одинаковый ранг, просто добавьте их значения.

Постфиксный DFS позволяет вычислять суммы снизу вверх.

Вот некоторая программа на Python 3.7 дляиграть с (код, вероятно, не оптимизирован):

from dataclasses import dataclass
from typing import List, Dict

@dataclass
class Node:
    value: int
    rank: int
    sum_by_rank: Dict[int, int]
    children: List[object]

tree = Node(5, 0, {}, [
        Node(4,2, {}, [Node(3,1, {}, [])]),
        Node(7,2, {}, [Node(11,1, {}, [Node(7,8, {}, [])])]),
        Node(8,4, {}, [Node(3,3, {}, []), Node(9,5, {}, []), Node(4,2, {}, [])]),
    ])

def dfs(node, previous=None):
    for child in node.children:
        dfs(child, node)
        node.sum_by_rank[child.rank] = node.sum_by_rank.get(child.rank, 0) + child.value # add this children rank -> value
        # add the subtree rank -> value 
        for r,v in child.sum_by_rank.items():
            node.sum_by_rank[r] = node.sum_by_rank.get(r, 0)+v

dfs(tree)
print (tree)
# Node(value=5, rank=0, sum_by_rank={2: 15, 1: 14, 8: 7, 4: 8, 3: 3, 5: 9}, children=[Node(value=4, rank=2, sum_by_rank={1: 3}, children=[Node(value=3, rank=1, sum_by_rank={}, children=[])]), Node(value=7, rank=2, sum_by_rank={1: 11, 8: 7}, children=[Node(value=11, rank=1, sum_by_rank={8: 7}, children=[Node(value=7, rank=8, sum_by_rank={}, children=[])])]), Node(value=8, rank=4, sum_by_rank={3: 3, 5: 9, 2: 4}, children=[Node(value=3, rank=3, sum_by_rank={}, children=[]), Node(value=9, rank=5, sum_by_rank={}, children=[]), Node(value=4, rank=2, sum_by_rank={}, children=[])])])

Следовательно, чтобы получить sum узла, просто добавьте значения, связанные с рангами, большими или равными рангу узла.В Python:

sum(value for rank, value in node.sum_by_rank.items() where rank >= node.rank)

Answer 4

Редактировать Не правильный ответ, не решает проблему, заданную ОП (см. Комментарий)
Старый ответ (до редактирования) Вы можете видеть, что эту проблему (как и большинство проблем на деревьях) можно решить с помощью рекурсивного подхода. Это связано с тем, что sum value узла зависит только от sum values и соответствующих ranks его дочерних элементов.

Вот псевдокод, описывающий решение.

get_sum(my_node, result_arr):
    my_sum = 0
    for child in my_node.children():
        get_sum(child, result_arr)        // we compute the sum value of the children
        if rank(child) >= rank(my_node):  // if child node is big enough add its sum
            my_sum += result_arr[child]
     result_arr[my_node] = my_sum         // store the result somewhere

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