从子树节点聚合值的算法

Question

我有一些树形结构的对象，希望从子节点聚合状态信息并将聚合后的状态更新到父节点。例如，节点A有子节点B1、B2，B1有子节点C1、C2、C3。每个节点都有一个状态属性。

现在如果C1、C2、C3都完成了，我想将B1标记为已完成。如果C4、C5、C6、C7完成了，则将B2标记为已完成。当B1和B2都完成时，将A标记为已完成。

我可以通过 brute force 方法遍历这些节点并进行更新，但是否有高效的算法可以实现呢？

A { B1 { C1、C2、C3 }, B2 { C4、C5、C6、C7 } }

- tech20nn

---

任何能够帮助节省CPU周期/内存的东西。 - tech20nn

你的树有多大？你执行这个操作的频率是多少？你能容忍一些“陈旧”吗？通常解决这个问题更有效的方法不是通过低级优化，而是利用你对问题的所有知识。你可以在某些子树中缓存结果，在子节点变为不完整时向上传播“不完整”标志等。 - Philippe Beaudoin

我有大约5000棵树。每棵树都有3到4层深度。每一层可能有20-50个节点。我计划每天运行一次此过程。可以按需运行单个树的处理过程。看起来，使用这些数据，我可能不需要缓存，但我会探索一下。感谢您提出这些重要参数。 - tech20nn

根据更新频率，看起来您可以计算自上次运行以来的新/更新节点（如果相对于整个数据集而言很小），并向上传播更改。否则，从上到下重新计算。 - harschware

是的，每个节点上的最后更新时间戳是我的算法的一部分。 - tech20nn

Answer 1

你需要进行后序遍历 - 先访问节点的子节点，然后递归地标记节点本身。

类似以下伪代码：

iscomplete(node):
  if node == Null:
     return False
  elsif no children:
     return some "complete" value according to node value
  else:
     for child in node.children:
         if not iscomplete(child):
             return False

  return True

- Eli Bendersky

---

如果您不断将状态向上传递到树的父节点，从而在每次更改子节点时适当地标记父节点，那么您可以避免遍历整个树。当然，这需要子节点知道其父节点，但是可以通过简单检查根节点来找出整体状态。 - Yuval

@Yuval: 是的，这是一种权衡。这在某些情况下可能更加高效，具体取决于您更改子元素和查询状态的频率。 - Eli Bendersky

Answer 2

Eli Bendersky的做法是正确的，这个问题的一般答案是后序遍历。

然而，为了更有效率，你需要利用你所知道的一切关于这个问题的信息。例如，如果你可以允许一些"过时"，那么在每个节点中缓存一个complete标志和时间戳可能会更好。

另一种可能性是节点内部的complete状态很少改变。在这种情况下，向上传播完整信息可能会更好。类似这样：

class NodeWithCompletenessInfo : public Node {

  private bool internalComplete; // Am I personally done?
  private bool childrenComplete; // Are my children done?

  public bool isComplete() {
    return internalComplete && childrenComplete;
  }

  public void markComplete() {
    internalComplete = true;
    if( isComplete() )
      parent.markChildComplete();
  }

  public void markIncomplete() {
    if( isComplete() )
      parent.markChildIncomplete();
    internalComplete = false;
  }

  private void markChildComplete() {
    for( child in children ) {
      if( !child.isComplete() )
        return;
      childrenComplete = true;
    }
    if( isComplete() )
      parent.markChildComplete()
  }

  private void markChildIncomplete() {
    if( isComplete() )
      parent.markChildIncomplete();
    this.childrenComplete = false;
  }
}

- Philippe Beaudoin

---

感谢Philippe提供全面的逻辑。 - tech20nn

Answer 3

如果你知道哪些是叶节点，那么

 A { 
    B1 
        {C1, C2 = false, C3},
    B2 
        {C4, C5=false, C6=false, C7} 
  } // those not marked false are true ;)

not_complete_leaf_nodes_with_different_parents = [ C2 , C5]

mark_not_complete(node):
    node.complete = false
    if parent != null
        mark_not_complete(node.parent)

for each in not_complete_leaf_nodes_with_different_parents:
    mark_not_complete(each.parent)

- Pratik Deoghare

Answer 4

我认为你无法避免“暴力破解”。

我会使用访问者设计模式。

http://www.javaworld.com/javaworld/javatips/jw-javatip98.html

http://sourcemaking.com/design_patterns/visitor

- Yaneeve

---

使用“设计模式”来解决微不足道的算法树遍历问题。天哪...这是什么时代啊 ;-) - Eli Bendersky

既然他没有具体说明他的代码，我想我会给他更“强大”的工具。 - Yaneeve

我无法理解如何使用访问者模式来解决树遍历问题。 - harschware

客户端决定了访问（遍历）的顺序，而不是访问者。访问者会响应遍历。由于访问者不会维护有关遍历的状态，这正是为什么访问者模式无法帮助的原因（例如，如果要创建“ StatusCompleteVisitor”之类的内容）。除非我漏了什么，否则我认为访问者模式不适用于此用例。 - harschware