Сложность времени с древовидной структурой данных - PullRequest
Новая
       12

Сложность времени с древовидной структурой данных

0 голосов
/ 24 марта 2020

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

       A(5)
       / \
     C(2) D(8)
      |
     B(10)

Значение поддерева C будет равно 10, значение поддерева A будет равно 10, а значение поддерева D будет равно 8 et c. Я пытаюсь уменьшить сложность следующего кода с O (n ^ 2) до O (n). То есть я пытаюсь переместиться вверх по дереву без использования вложенного l oop. Я пробовал это с рекурсией, но я не слишком хорош в рекурсии, поэтому итерационное решение ниже. Любая помощь будет оценена. Кроме того, возможно ли сделать это без рекурсивного решения? 

         node = subtree_a
         while node.parent != None:
             children = node.parent.children
             for child in children:
                 if (child.subtree_value > node.parent.subtree_value):
                     node.parent.set_subtree_val(child.subtree_value)
             node = node.parent\

1 Ответ

1 голос
/ 24 марта 2020

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

Очень простой нисходящий Рекурсивный подход будет следующим: 

def calc_subtree_value(node):
    val = node.value
    for child in node.children: # we don't need a base case, this forks for leaf nodes too
        calc_subtree_value(child)
        if child.subtree_value > val:
            val = child.subtree_value
    node.subtree_value = val

Это займет O (N) время, где N - количество узлов в поддереве, так как оно посещает каждый из них ровно один раз. Как я отмечаю в комментарии, нам не нужен явный базовый случай, потому что l oop над дочерними элементами делает то, что мы хотим (ничего), если нет дочерних элементов для проверки больших значений поддерева.

...