Суммируйте дочерние значения и сохраняйте значения, вычисленные в промежуточных шагах

Question

struct node { 
    int value; 
    struct node* left; 
    struct node* right; 
    int left_sum;
    int right_sum;
} 

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

Будет ли проще сделать это снизу, добавив ссылку struct node* parent к определению узла?

Answer 1

Нет, это явно упражнение в рекурсии. Подумайте о том, что означает сумма. Это ноль плюс «сумма всех значений от корня вниз».

Интересно, что «сумма всех значений от корневого узла вниз» представляет собой значение корневого узла плюс «сумма всех значений от его левого узла вниз» плюс"сумма всех значений от его правого узла вниз".

Надеюсь, вы видите, куда я иду.

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

Завершающим условием в данном случае является листовые узлы дерева или, для упрощения кода, за пределами листовых узлов.

Проверьте следующий псевдокод:

def sumAllNodes (node):
    if node == NULL:
        return 0
    return node.value + sumAllNodes (node.left) + sumAllNodes (node.right)

fullSum = sumAllNodes (rootnode)

Это действительно все, что нужно сделать. Со следующим деревом:

           __A(9)__
          /        \
      B(3)          C(2)
     /    \             \
D(21)      E(7)          F(1)

При использовании псевдокода сумма равна значению A (9) плюс суммы левого и правого поддеревьев.

Левое поддерево A - это значение B (3) плюс суммы его левого и правого поддеревьев.

Левое поддерево B - это значение D (21) плюс суммы его левого и правого поддеревьев.

Левое поддерево D является значением NULL (0).

Позже правое поддерево A - это значение C (2) плюс суммы его его левого и правого поддеревьев, его левое поддерево пустое, его правое поддерево F (1).

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

---

И другая часть вашего вопроса не очень полезна, хотя, конечно, могут быть неустановленные требования, которые я не принимаю во внимание, потому что они, ну ... неустановленные: -)

Есть ли способ сохранить значения, рассчитанные на промежуточных этапах, и сохранить их как left_sum и right_sum в дочерних узлах?

Вы никогда не будете повторно использовать суммы для данного поддерева. Во время вычисления суммы вы должны вычислить только B-and-below поддерево один раз как часть добавления его к A и C-and-below поддереву.

Вы можете сохранить эти значения так, чтобы B содержал и значение, и две суммы (левую и правую) - это означало бы, что каждое изменение в дереве должно распространяться вплоть до root, но это выполнимо.

Теперь есть некоторые ситуации, в которых это может быть полезно. Например, если само дерево меняется очень редко, но вы хотите, чтобы сумма была очень частой, имеет смысл использовать производительность при обновлении, чтобы стоимость амортизировалась при большом количестве операций чтения.

Я иногда использую этот метод с базами данных (которые в основном читаются гораздо чаще, чем записаны), но это необычно видеть в "нормальных" двоичных деревьях.

Другая возможная оптимизация: просто сохраните сумму в виде отдельной переменной в объекте дерева. Инициализируйте его до нуля, а затем, при каждом добавлении узла, добавляйте его значение к сумме.

При удалении узла вычтите его значение из суммы. Это дает вам очень быструю O (1) функцию «возврат суммы» без необходимости распространяться вверх при обновлении.

Недостатком является то, что у вас есть только сумма для дерева в целом, но мне трудно найти подходящий вариант использования для получения суммы поддеревьев. Если у вас есть такой вариант использования, то я бы выбрал что-то вроде:

def updateAllNodes (node):
    if node == NULL:
        return 0
    node.leftSum = updateAllNodes (node.left)
    node.rightSum = updateAllNodes (node.right)
    return node.value + node.leftSum + node.rightSum

change the tree somehow (possibly many times)
fullSum = updateAllNodes (root)

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

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

Таким образом, код вроде:

fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)

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