如何高效地把嵌套集合到一个对象层次 [英] How to transform nested sets efficiently into a object hierarchy

问题描述

假如我有重新present一组嵌套层次结构的节点列表（例子是伪C＃）。

Suppose I have a list of nodes which represent a nested set hierachy (examples are in pseudo c#).

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

List<Node> nodes = GetFlatNodesWithoutChildrenSetFromDatabase();

字段离开，右键和 ID GET填充，因为这些值存储在数据库中的一些

The fields left, right and id get filled, since these values are stored in some database.

什么是将这款平板名单成层次结构的有效途径，这意味着填写相应的子节点的每个父节点？

What is an efficient way to transform this flat list into a hierachy, that means filling in the appropriate children nodes for each parent node?

一个办法就是找到每个节点的所有祖先，对它们进行排序，找到父节点和子节点添加到该节点。

One way is just to find all ancestors of each node, sort them to find the parent node and add the child node to that node.

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

但是，这是相当低效。

But this is rather inefficient.

有没有更好的（这意味着更快）的办法？

Is there a better (that means faster) approach?

修改

可能的解决方案（所建议的克里斯）：

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

节点必须由，责令离开。

推荐答案

我会想探索的方法是通过左命令，然后就可以通过仅仅一次迭代。

The method I might think about exploring is to order by left and then you can just iterate through once.

您打开的节点，当你到了左边，把它贴在一个堆栈。

You "open" a node when you get to its left and stick it on a stack.

当你到了一个新的节点来处理，你是否在堆栈顶部的节点应该通过确定其右侧小于左侧的新节点关闭。如果你从堆栈中删除（关闭它），并且您已经处理了所有的孩子。然后，您做检查堆栈新的顶部，直到你找到一个仍处于打开状态。然后，作为子添加当前节点到节点上的堆叠的顶部和该节点随后打开（如此这般堆栈的顶部）。

When you get to a new node to process you check if the node on the top of the stack should be closed by determining if its right is less than the new nodes left. If it is you remove it from the stack (closing it) and you have processed all its children. You then do the check for the new top of the stack til you find one that is still open. You then add the current node as a child to the node on the top of the stack and that node is then opened (so it goes on the top of the stack).

您链接的维基百科页面（http://en.wikipedia.org/wiki/Nested_set_model）上图是什么启发了我这一点。

The diagram on the wikipedia page you linked (http://en.wikipedia.org/wiki/Nested_set_model) is what inspired me to this.

我的算法基本上向下行进在中间行，只要你进入集中的一个就是我所说的开口，留下一组正在缩小。显然，最新的一组已打开，但没有关闭将会对堆栈的顶部，因此，当你把孩子。

My algorithm basically travels down the line in the middle and whenever you enter one of the sets is what I refer to as opening and leaving a set is closing. Clearly the most recent set you have opened but not closed will be on the top of the stack and thus where you put the children.

我觉得这应该是O（nlogn）由于排序的复杂性。它剩下的只是为O（n）。

I think the complexity of this should be O(nlogn) due to the sort. The rest of it is just O(n).

这篇关于如何高效地把嵌套集合到一个对象层次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！