從子樹節點聚合值的算法

我有一個樹形結構的對象，我想聚合子節點的狀態信息並用彙總狀態更新父節點。假設節點A有孩子B1，B2，B1有孩子C1，C2，C3。每個節點都有一個狀態屬性。從子樹節點聚合值的算法

現在如果C1，C2，C3全部完成，那麼我想將B1標記爲完成。如果C4，C5，C6，C7完成，則B2完成。當B1和B2都完整標記A完成時。

我可以通過蠻力方法通過這些節點並進行更新，有人可以建議一個有效的算法來做到這一點。

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

2010-03-24 tech20nn

凡是有利於節省CPU週期/內存。 – tech20nn 2010-03-24 17:27:23

你的樹有多大？你多久執行一次該操作？你能允許一些「陳舊」嗎？解決這個問題的方法通常不是通過低級優化，而是通過使用關於問題的所有知識。你可以在一些子樹中緩存結果，當孩子變得不完整時在樹上傳播「不完整」的標誌等。 – 2010-03-24 17:33:56

我有大約5000棵樹。每棵樹的深度都是3到4級。每個級別可能有大約20-50個節點。我計劃每天運行一次這個過程。個別樹木的處理可按需運行。看起來像我可能不需要緩存的數據，但我會探索它。感謝提出這些重要參數。 – tech20nn 2010-03-24 17:54:50

需要後序遍歷 - 第一訪問節點的孩子，然後遞歸地標記節點本身。

類似的信息（僞）：

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

來源

2010-03-24 17:20:30

如果持續向樹中抽取狀態，可以避免遍歷整個樹，從而在每次更改孩子時都適當地標記父節點。當然，這要求孩子知道父母，但是可以通過對根的簡單檢查來了解總體狀況。 – Yuval 2010-03-24 17:48:40

@Yuval：是的，這是一個折衷。在某些情況下，這可能會更有效率，具體取決於您更換孩子的頻率以及您查詢狀態的頻率。 – 2010-03-24 17:52:52

@Yuval：看到我的答案下面的一些僞代碼。 – 2010-03-24 17:58:02

-1

我看不到，你可以迴避「蠻力」。

我會使用訪客設計模式。

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

http://sourcemaking.com/design_patterns/visitor

來源

2010-03-24 17:24:37 Yaneeve

使用「設計模式」來解決微不足道的算法樹遍歷。 Geez ...什麼日子在我們身上;-) – 2010-03-24 17:29:30

由於他沒有具體說明他的代碼，我想我會給他更多「強大的」工具 – Yaneeve 2010-03-24 17:37:20

（-1）我看不出如何解決樹遍歷問題訪客模式。 – harschware 2010-03-24 18:22:50

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

來源

2010-03-24 17:24:45

感謝Philippe的綜合邏輯。 – tech20nn 2010-03-26 11:54:54

如果你知道哪些是葉節點則

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)

來源

2010-03-24 17:41:38

從子樹節點聚合值的算法

回答

相關問題