ネストされたセット階層を表すノードのリストがあるとします (例は疑似 c# にあります)。
class Node
{
public decimal left;
public decimal right;
public decimal id;
public void AddChild(Node child) {...}
...
}
List<Node> nodes = GetFlatNodesWithoutChildrenSetFromDatabase();
これらの値は何らかのデータベースに保存されているため、フィールド と が入力さleft
れますright
。id
このフラット リストを階層に変換する効率的な方法は何ですか。つまり、各親ノードに適切な子ノードを入力することを意味します。
1 つの方法は、各ノードのすべての祖先を検索し、それらを並べ替えて親ノードを見つけ、そのノードに子ノードを追加することです。
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);
}
しかし、これはかなり非効率的です。
より良い(つまり、より速い)アプローチはありますか?
編集
考えられる解決策(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
。