如何将嵌套集有效转换为对象层次结构

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();