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

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

节点必须按左排序。

Answer 1

我可能会考虑探索的方法是按左排序，然后您可以迭代一次。

当您到达节点左侧时，您“打开”了一个节点并将其粘贴到堆栈中。

当您到达要处理的新节点时，您会通过确定堆栈顶部的节点的右侧是否小于左侧的新节点来检查是否应关闭堆栈顶部的节点。如果是，则将其从堆栈中移除(关闭它)并且您已经处理了它的所有子项。然后检查新的栈顶，直到找到一个仍然打开的栈顶。然后将当前节点作为子节点添加到堆栈顶部的节点，然后打开该节点(因此它位于堆栈顶部)。

您链接的维基百科页面上的图表 (http://en.wikipedia.org/wiki/Nested_set_model) 启发了我这样做。

我的算法基本上是沿着中间的线行进，每当你进入其中一个集合时，我称之为打开和离开一组就是关闭。很明显，您最近打开但未关闭的集合将位于堆栈的顶部，因此您将 child 放置在该位置。

由于排序，我认为这个的复杂度应该是 O(nlogn)。剩下的只是 O(n)。