1

ランダムに分散されたキーのセットが与えられ、各キーが値のセットにマップされている場合、それを複数のツリーに変換するにはどうすればよいでしょうか?

サンプルデータセット

  • NB 2 => {NC 2 ND 2 }
  • ND 1 => {NG 1 NH 1 }
  • NA 1 => {NB 1 }
  • NB 1 => {NC 1 ND 1 NE 1 }
  • NA 2 => {NB 2 }
  • NC 1 => {NF 1 }
  • NE 1 => {NI 1 NJ 1 NK 1 }

NA 1の結果ツリー

NA 1 
`-- NB 1 
    |-- NC 1 
    | `-- NF 1 
    |-- ND 1 
    | |-- NG 1 
    | `-- NH 1 
    `-- NE 1 
        |-- NI 1 
        |-- NJ 1 
        `-- NK 1

NA 2の結果ツリー

NA 2 
`-- NB 2 
    |-- NC 2 
    `-- ND 2
4

2 に答える 2

3

この変換を行うライブラリメソッドを私は知りません。これが私がそれをする方法です。それはかなり簡単です、IMO。

public class Tree {
    public Tree(String key) {
        // ...
    }
    public void addChild(Tree child) {
        // ...
    }
}

public Set<Tree> transform(Map<String, List<String>> input) {
    // Potential tree roots.  We start with all LHS keys as potential roots,
    // and eliminate them when we see their keys on the RHS.
    Set<String> roots = new HashSet<String>(input.keySet());

    // This map associates keys with the tree nodes that we create for them
    Map<String, Tree> map = new HashMap<String, Tree>();

    for (Map.Entry<String, List<String>> entry : input.entrySet()) {
        String key = entry.getKey();
        List<String> childKeys = entry.getValue();
        Tree tree = map.get(key);
        if (tree == null) {
            tree = new Tree(key);
            map.put(key, tree);
        }
        for (String childKey : childKeys) {
            roots.remove(childKey);
            Tree child = map.get(childKey);
            if (child == null) {
                child = new Tree(childKey);
                map.put(childKey, child);
            }
            tree.addChild(child);
        }
    }
    Set<Tree> res = new HashSet<Tree>(roots.size());
    for (String key : roots) {
        res.add(map.get(key));
    }
    return res;
}

編集：入力がDAG（有向非巡回グラフ）のセットを表す場合、このアルゴリズムは「機能する」ことに注意してください。ただし、結果として得られるツリーのセットは、入力データ内の一般的なサブツリーのTreeNodeインスタンスを共有することに気づきました。

私はこのコードをデバッグしていないことに注意してください:-)

于 2009-08-09T03:09:28.453 に答える
0

それらを木の集合に変換するというのは、メモリ上でそれらを表現する方法について話しているのですか?

それとも、一連のキーと値を調べてメモリ内表現に入れるアルゴリズムでしょうか?

それとも、グラフィカルな表現について話しているのですか?

于 2009-08-09T02:05:39.163 に答える