如何從其節點列表中更快地更新樹，然後O（n^2）？

鑑於：列表N節點。每個節點由2個數字組成：nodeID和parentID。 parentID可能是null（如果它是根節點）。如何從其節點列表中更快地更新樹，然後O（n^2）？

是否有算法從時間複雜度高於O（N^2）的節點列表中重新創建樹？

每個節點可能有0個或更多的孩子。

的算法的帶O

簡短說明（N^2）的複雜性：

find a root Node, put it to a Queue 
    while Queue is not empty 
     parentNode = Queue.pop() 
     loop through nodes 
      if currentNode.parentId = parentNode.id 
       parentNode.addChild(currentNode) 
       queue.push(currentNode) 
       nodes.remove(currentNode)

看來，這個算法具有O（N^2）時間複雜度（與係數小，也許0.25）。但是我在這裏計算複雜度可能是錯誤的。

來源

2012-02-16 Roman

對於每個節點，初始化一個子節點列表，併爲每個節點更新父節點的子節點列表。複雜度O（n）。

For node in NodeList: 
    node.childList = [] 

For node in NodeList: 
    if node.parent is not NULL: 
     node.parent.childList.append(&node)

如果父鏈接不可用，則創建一個哈希映射。 FWIW，對於每個插入或查找，散列映射的最壞情況複雜度爲O（logn）。所以最終的複雜性變成O（nlogn）。

來源

2012-02-16 17:57:09 ElKamina

雖然此方法通常有效，但它看起來像Roman正在使用ID，並且對實際父對象的引用尚未知道。 – Kaganar 2012-02-16 18:01:36

@Kaganar：只是想添加相同的評論 – Roman 2012-02-16 18:04:40

@Kaganar如果鏈接不可用，您可以創建哈希映射。但複雜性不會保持O（n）。 – ElKamina 2012-02-16 18:11:53

由於您已經獲得了樹（隊列）的外部結構，因此我假設您不介意使用一點額外內存來更快地完成工作。

做在同一個哈希表中的兩個概念上的步驟：

首先作出這樣的涉及節點ID，以自己的實際節點的哈希表。
然後根據哈希表中的父節點ID查找節點的父節點，並將子節點添加到該父節點。

更多編程：

for each node 
    add node to hash table indexed by node's parent 
for each node 
    if parent is null set node as the root 
    otherwise look up in the hash table the parent from the parent ID of the node 
    add the node as a child of the found parent

與這種技術，你不必與有效的樹，直到最後一刻結束了唯一的潛在問題。（也就是說，根節點可能沒有孩子，直到最後一個鏈接。）根據你在樹上做什麼，這可能是一個問題。

如果這是一個問題，您最終可能會對沒有該問題的數據結構（只是一個沒有附加數據的香草樹）執行相同的操作，然後鏡像該結構。

總的來說，這應該是O(N)的平均值。

來源

2012-02-16 18:00:08 Kaganar

我不知道你的輸入是什麼，但我們假設它是某種無序列表。

然後，您可以創建一個樹結構，只需將它們放入一個允許通過其nodeID查找它們的數據結構即可。例如，一個數組可以做到這一點。然後，你有一棵只與父母方向相連的樹。假設節點ID是唯一的，則可以在線性時間內從無序列表轉換到此陣列。

爲了讓樹也鏈接到孩子的方向，你可以準備具有數據結構（例如列表）的節點來容納孩子，然後做第二遍，將每個節點添加到它的子節點父母的孩子名單。這也可能是線性時間。

來源

2012-02-16 21:07:19 Svante

如何從其節點列表中更快地更新樹，然後O（n^2）？

回答

相關問題