如何將嵌套集有效轉換爲對象層次結構

Question

假設我有一個表示嵌套集合層次結構的列表（示例在僞c＃中）。

class Node 
{ 
    public decimal left; 
    public decimal right; 
    public decimal id; 
    public void AddChild(Node child) {...} 
    ... 
} 

List<Node> nodes = GetFlatNodesWithoutChildrenSetFromDatabase(); 

字段left，right和id得到填補，因爲這些值存儲在數據庫中的一些。

什麼是將這個扁平列表轉換爲層次的有效方式，這意味着爲每個父節點填充適當的子節點？

一種方法是找到每個節點的所有祖先，對它們進行排序以找到父節點並將子節點添加到該節點。

foreach (var n in nodes) 
{ 
    var parent = nodes.Where(i => i.left < n.left && i.right > n.right).OrderBy(i => i.right - n.right).FirstOrDefault(); 
    if (parent != null) 
     parent.AddChild(n); 
} 

但是這樣效率很低。

有沒有更好的（這意味着更快）的方法？

編輯

可能的解決方法（as suggested by Chris）：

var stack = new Stack<Node>(nodes.Take(1)); 
foreach (var n in nodes.Skip(1)) 
{ 
    while (stack.Peek().right < n.left) 
     stack.Pop(); 

    stack.Peek().addChild(n); 
    stack.Push(n); 
} 

節點必須由left訂購。

Answer 1

我可能會考慮的探索方法是按左排序，然後您可以迭代一次。

當您到達其左側並將其粘貼到堆棧上時，您會「打開」一個節點。

當您到達一個新節點進行處理時，通過確定其右側是否小於剩餘的新節點，檢查堆棧頂部的節點是否應該關閉。如果是從堆棧中刪除它（關閉它），並且您已經處理完所有子項。然後檢查堆疊的新頂部，直到找到一個仍處於打開狀態的堆疊頂部。然後，將當前節點作爲子節點添加到堆棧頂部的節點，然後打開該節點（以便它位於堆棧的頂部）。

您鏈接到的維基百科頁面上的圖（http://en.wikipedia.org/wiki/Nested_set_model）激發了我對此的啓發。

我的算法基本上向下行進在中間的線，只要你進入集中的一個就是我稱之爲開放，留下一組被關閉。很明顯，您打開但未關閉的最新設置將位於堆棧的頂部，因此您放置孩子的位置。

我認爲這種複雜性應該是O（nlogn）由於排序。其餘的只是O（n）。

Answer 2

我知道這個問題是相當古老的（我沒有發現任何其他問題/關於這個主題的信息），我不知道「僞C＃」，但只是爲了防止你們中的一些與遞歸算法混爲一談對於嵌套集列表=>樹算法，這是我來（在斯卡拉）：

def retrieveUserFolderTree(user: User): Future[List[Folder]] = { 
    // Get a list of user's folders orderred by left asc 
    val dbFoldersPromise = folderDAO.findUserFolders(user) 

    dbFoldersPromise.map { 
    case rootFolder :: tail => generateChildren(0, rootFolder.right, tail) 
    case Nil => Nil 
    } 
} 

private def generateChildren(currentLeft: Int, currentRight: Int, dbFolders: Seq[DBFolder]): List[Folder] = { 
    dbFolders match { 
    case dbFolder :: tail if dbFolder.left > currentRight => Nil 
    case dbFolder :: tail if dbFolder.left > currentLeft => Folder(dbFolder.id, dbFolder.name, generateChildren(dbFolder.left, dbFolder.right, tail)) :: generateChildren(dbFolder.right, currentRight, tail) 
    case dbFolder :: tail => generateChildren(currentLeft, currentRight, tail) 
    case Nil => Nil 
    } 
} 

希望這將有助於某人。

Answer 3

也許我錯過了某個步驟，但是當我使用上述邏輯進行這項工作時，我最終在堆棧中複製了一些元素。它們像預期的那樣在樹中，另外它們也位於根節點上方的棧頂。我不得不在最後添加一個小循環來清理堆棧。

 var stack = new Stack<DvrNode>(nodes.Take(1)); 
     foreach (var n in nodes.Skip(1)) 
     { 
      while (stack.Peek().Right < n.Left) 
       stack.Pop(); 

      ((List<DvrNode>)stack.Peek().Children).Add(n); 
      stack.Push(n); 
     } 

     while (stack.Peek().Left != 1) 
      stack.Pop();