Алгоритм агрегации значений из дочерних узлов дерева

Question

У меня есть объекты в древовидной структуре, я хотел бы собирать информацию о состоянии от дочерних узлов и обновлять родительский узел с агрегированным статусом. Допустим, узел A имеет дочерние элементы B1, B2, а B1 имеет C1, C2, C3 в качестве дочерних элементов. Каждый из узлов имеет атрибут статуса.

Теперь, если C1, C2, C3 завершены, я бы хотел отметить B1 как завершенный. И если C4, C5, C6, C7 завершены, сделайте B2 завершенным. Когда B1 и B2 оба завершены, отметьте A как завершенный.

Я могу пройти через эти узлы методом грубой силы и сделать обновления, может кто-нибудь предложить эффективный алгоритм для этого.

A { B1 {C1, C2, C3}, Би 2 {C4, C5, C6, C7} }

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

Answer 2

Эли Бендерский правильно понял, общий ответ на эту проблему - прохождение после заказа.

Однако для большей эффективности вы должны использовать все, что вам известно о проблеме. Например, если вы можете разрешить некоторую «устаревание», то может быть лучше кэшировать флаг complete и отметку времени в каждом узле.

Другая возможность состоит в том, что внутренний complete статус узлов редко изменяется. В этом случае может быть гораздо лучше распространять информацию о полноте up . Примерно так:

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;
  }
}

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)

Answer 4

Я не вижу, чтобы вы могли уклониться от "грубой силы".

Я бы использовал шаблон дизайна посетителя.

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

http://sourcemaking.com/design_patterns/visitor