添加樹視圖分支的最有效的算法

Question

我必須構建將分支（節點）添加到樹視圖。我努力確定最低的O（n）技術是什麼。

我的數據給出如下：

Id ParentId Value 

0 null  Bob 
1 0   Amy 
2 1   Susan 
3 1   Matt 
4 2   Keith 
5 4   Craig 
6 4   Derrick 

所以樹看起來像：

所有我能想出是n^2算法，該算法對每個條目掃描每隔一個條目查看它們是否屬於子節點。 我也正在刪除數組中的條目，以便在添加時進行掃描。所以如果內存服務（可能不是），它會比n^2少一點。

有沒有更好的技術？

Answer 1

假設你的語言有某種list/vector/resizable數組類型，這很容易。

爲每個ID創建一個空列表。遍歷每一行，如果ParentId不爲null，則將該Id添加到ParentId的列表中。

你現在有O（n）時間的每個條目的孩子。