0

ネストされたセット階層を表すノードのリストがあるとします (例は疑似 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。

4

3 に答える 3

3

私が探求しようと考えている方法は、左から順番に並べて、一度だけ反復することです。

ノードの左側に移動してノードを「開き」、スタックに貼り付けます。

処理する新しいノードに到達したら、スタックの一番上のノードを閉じる必要があるかどうかを確認するために、その右側が新しいノードの左側よりも小さいかどうかを判断します。その場合は、スタックから削除して (閉じて)、すべての子を処理しました。次に、まだ開いているスタックが見つかるまで、スタックの新しいトップのチェックを行います。次に、現在のノードを子としてスタックの一番上のノードに追加すると、そのノードが開かれます (つまり、スタックの一番上になります)。

あなたがリンクしたウィキペディアのページ ( http://en.wikipedia.org/wiki/Nested_set_model ) の図は、私がこれに触発されたものです。

入れ子集合図

私のアルゴリズムは基本的に真ん中の線をたどり、セットの 1 つに入るときはいつでも、私は開始と呼び、セットを離れることを閉じます。明らかに、開いたが閉じていない最新のセットがスタックの一番上にあるため、子を配置する場所になります。

並べ替えのため、これの複雑さは O(nlogn) になるはずです。残りは O(n) です。

于 2012-06-01T15:11:38.837 に答える
0

どこかでステップを逃したのかもしれませんが、上記のロジックを使用してこれに取り組んでいたときに、重複したスタック上の要素がいくつかありました。それらは予想どおりツリーにありましたが、さらにルートノードの上のスタックの一番上にもありました。スタックをクリーンアップするために、最後に小さなループを追加する必要がありました。

        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();
于 2016-05-03T15:41:52.337 に答える
0

質問がかなり古いことは知っています（トピックに関する他の質問/情報は見つかりませんでした）。「疑似C＃」はわかりませんが、ネストされたセットリストの再帰アルゴリズムに苦労する人がいる場合に備えて=>ツリーアルゴリズム、これが私がたどり着いたものです（scalaで）：

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

これが誰かを助けることを願っています。

于 2014-10-27T21:20:40.830 に答える