將原始樹合併到結果樹中的步驟

Question

擁有原始和「最終」/ 結果樹。我想比較這些樹木並「重現」這些步驟，這些步驟將被攜帶以獲得相同的結果。

現實生活中的例子：在數據庫中有原始樹。工作人員已準備好更改（在App中生成新的結果樹），現在我們需要更新數據庫。我們無法刪除數據庫並重新上傳，因爲可能有尚未生成的數據。

類/表定義：

class TreeNode 
{ 
    public string Text { get; set; } 
    public TreeNode Parent { get; set; } 

    /* some other properties */ 
} 

實施例的樹木：

Origin       Result 
|A        |A 
| -1       | -2 
| -2       |C 
|B        | -3 
| -5       |D 
| --£       | -1 
|C        | --£ 
|F        | -5 
| -7       |E 
|H        | -6 
           |G 
           | -4 
           |H 

我希望是有一個算法，通過該我將被允許處理時的對象是加入 ，刪除或移動。

重要信息：有其他家長不應該刪除和加入後面的對象，相反，他們應該只有下其他家長感動！刪除會導致數據丟失。

實施例：

Mark B as removed 
Mark F as removed 
Add D 
Add E 
Add G 
Move 1 under D 
Move 5 under D 
Mark 7 as removed 
Add 3 under C 
Add 6 under E 
Add 4 under G 
Move £ under 1 
Removed 7 
Removed F 
Removed B 

---

自己的解決方案

我創建樣品與的Win-形式和的TreeView。我的算法僅適用於每個級別的基礎（例如，將1從A移動到D），但不能跨越。元素是第一個被刪除的市場，最後被刪除。

代碼：

//Recursive loop to find all nodes in Nth level 
private IEnumerable<TreeNode> getNodesOnLevel(TreeNodeCollection aCollection, int aLevel) 
{ 
    var lResultTreeNodeCol = new List<TreeNode>(); 

    if (aLevel == 1) 
     return aCollection.Cast<TreeNode>(); 

    foreach(TreeNode nNode in aCollection) 
    { 
     lResultTreeNodeCol.AddRange(getNodesOnLevel(nNode.Nodes, aLevel - 1)); 
    } 

    return lResultTreeNodeCol; 
} 

//Called once 
public void UpdateTrees(TreeNodeCollection aCollectionA, TreeNodeCollection aCollectionB) 
{ 
    List<TreeNode> lRemoved = new List<TreeNode>(); 
    for (int i = 1; UpdateWithLevel(aCollectionA, aCollectionB, i, ref lRemoved) > 0; i++) 
    { 
    } 
    var lRem = lRemoved.LastOrDefault(); 
    do 
    { 
     W($"Removed {lRem.Text}"); 
     lRemoved.Remove(lRem); 
    } while ((lRem = lRemoved.LastOrDefault()) != null); 

} 

//Called per level 
private int UpdateWithLevel(TreeNodeCollection aCollectionA, TreeNodeCollection aCollectionB, int level, ref List<TreeNode> aRemoved) 
{ 
    int lNumOfUpdates = 0; 
    var colA = getNodesOnLevel(aCollectionA, level); 
    var colB = getNodesOnLevel(aCollectionB, level); 

    //Search Original collection, compare to Result collection 
    foreach (TreeNode nodeA in colA) 
    { 
     //Find nodeA in Result collection 
     var lNodeAinColB = colB.FirstOrDefault((a) => a.Text == nodeA.Text); 

     if(lNodeAinColB == null) //NodeA not found in result collection - delete 
     { 
      aRemoved.Add(nodeA); 
      W($"Mark {nodeA.Text} as removed"); 
      lNumOfUpdates++; 
     } 
     else if((lNodeAinColB.Parent?.Text ?? "") != (nodeA.Parent?.Text ?? "")) //NodeA exists in Result collection, different parrent -> must be moved 
     { 
      W($"Move {nodeA.Text} under {lNodeAinColB.Parent.Text}"); 
      lNumOfUpdates++; 
     } 
    } 

    //Search Result collection, if Original collection does not have nodeB, we must create it (add) 
    foreach (TreeNode nodeB in colB) 
    { 
     if (!colA.Contains(nodeB, new TestNodeEquality())) 
     { 
      W($"Add {nodeB.Text}" + ((nodeB.Parent != null)?$" under {nodeB.Parent.Text}":"")); 
      lNumOfUpdates++; 
     } 
    } 

    return lNumOfUpdates; 
} 

我還沒有找到一個適合我的問題，也不是寶貴的資源&我真的想避免重複輪的任何話題。

問題（S）：

• 有現有&工作alghoritm（名稱/參考）？什麼是這種被稱爲（Tree Diff/Merge/Lookup/..）的alghorithms/actions？

• 我可以以任何方式優化alghoritm嗎？

Answer 1

我不認爲你在這裏需要一些複雜的遞歸算法。簡單地說你的結果節點名稱父字典和檢查：

• 原來的節點是否在字典
• 原始節點的父代是否改變
• 是否有結果的節點，其不存在於原始節點中

字典還提供了O（1）用於搜索節點，因此也將是一種優化。同樣涉及Except操作，這是快速設置操作。

代碼：

var originalNodes = new List<TreeNode>(); // TreeNodeCollection 
var nodes = new List<TreeNode>();   // TreeNodeCollection 
var parentByName = nodes.ToDictionary(n => n.Text, n => n.Parent); 

foreach(var originalNode in originalNodes) 
{ 
    TreeNode parent; 
    if (!parentByName.TryGetValue(originalNode.Text, out parent)) 
    { 
     // removed - there is no key for original node name 
     continue; 
    } 

    if (originalNode.Parent?.Text != parent?.Text) 
    { 
     // moved from originalNode.Parent to parent 
     continue; 
    } 
} 

// these guys are added 
var added = parentByName.Keys.Except(originalNodes.Select(n => n.Text)) 

Answer 2

我沒有一個C＃周圍的環境，所以我想我可以在Python實現這一點 - 他們稱之爲可執行的僞代碼，對不對？ ;）

def node(id, children=[]): 
    assert all(isinstance(child, dict) for child in children) 
    return {'id': id, 'children': children} 

tree1 = [ 
    node('a', [ 
     node('1'), 
     node('2'), 
    ]), 
    node('b', [ 
     node('5', [ 
      node('*'), 
     ]), 
    ]), 
    node('c'), 
    node('f', [ 
     node('7'), 
    ]), 
    node('h'), 
] 


tree2 = [ 
    node('a', [ 
     node('2'), 
    ]), 
    node('c', [ 
     node('3'), 
    ]), 
    node('d', [ 
     node('1', [ 
      node('*'), 
     ]), 
     node('5'), 
    ]), 
    node('e', [ 
     node('6'), 
    ]), 
    node('g', [ 
     node('4'), 
    ]), 
    node('h'), 
] 

def walk(tree, fn, parent=None): 
    for node in tree: 
     fn(node, parent) 
     walk(node.get('children',()), fn, parent=node) 


def get_all_nodes_and_parents(tree): 
    nodes = {} 
    parents = {} 
    def add_node(node, parent): 
     nodes[node['id']] = node 
     parents[node['id']] = (parent['id'] if parent else None) 
    walk(tree, add_node) 
    return (nodes, parents) 


def treediff(t1, t2): 
    n1, p1 = get_all_nodes_and_parents(t1) 
    n2, p2 = get_all_nodes_and_parents(t2) 
    new_nodes = set(n2.keys()) - set(n1.keys()) 
    del_nodes = set(n1.keys()) - set(n2.keys()) 

    for node_id in sorted(new_nodes): 
     yield 'create node %s' % node_id 

    for node_id in sorted(del_nodes): 
     yield 'delete node %s' % node_id 

    for node_id in n2: 
     if p1.get(node_id) != p2.get(node_id): 
      yield 'move node %s from %s to %s' % (node_id, p1.get(node_id), p2.get(node_id)) 

for op in treediff(tree1, tree2): 
    print(op) 

此輸出

create node 3 
create node 4 
create node 6 
create node d 
create node e 
create node g 
delete node 7 
delete node b 
delete node f 
move node 3 from None to c 
move node 1 from a to d 
move node * from 5 to 1 
move node 5 from b to d 
move node 6 from None to e 
move node 4 from None to g 

進一步的改善將是直接在他們的新父母來創建新的節點，但是這將需要增加的複雜性保持創造秩序的軌道，所以家長在他們的新孩子面前被創造。