Преобразовать карту с несколькими значениями в дерево?

Question

Учитывая случайным образом распределенный набор ключей, каждый ключ которого сопоставлен с набором значений, как бы вы преобразовали его в несколько деревьев?

Пример набора данных

• NB ₂ => {NC ₂ ND ₂ } < br />
• ND ₁ => {NG ₁ NH ₁ }
  
• NA ₁ => {NB ₁ }
• NB ₁ => {NC ₁ ND ₁ NE ₁ }
  
• NA ₂ => {NB ₂ }
  
• NC ₁ => {NF ₁ }
  
• NE ₁ => {NI ₁ NJ ₁ NK ₁ }
  

Результирующее дерево для NA ₁

NA<sub>1</sub>
`-- NB<sub>1</sub>
    |-- NC<sub>1</sub>
    |   `-- NF<sub>1</sub>
    |-- ND<sub>1</sub>
    |   |-- NG<sub>1</sub>
    |   `-- NH<sub>1</sub>
    `-- NE<sub>1</sub>
        |-- NI<sub>1</sub>
        |-- NJ<sub>1</sub>
        `-- NK<sub>1</sub>

Результирующее дерево для NA ₂

NA<sub>2</sub>
`-- NB<sub>2</sub>
    |-- NC<sub>2</sub>
    `-- ND<sub>2</sub>

Answer 1

Мне неизвестны какие-либо библиотечные методы, которые будут выполнять это преобразование. Вот как я это сделаю. Это довольно просто, ИМО.

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 для любых общих поддеревьев во входных данных.

Остерегайтесь, что я не отлаживал этот код: -)

Answer 2

Когда вы говорите о преобразовании их в набор деревьев, вы говорите о способе представления их в памяти?

Или, может быть, алгоритм, по которому мы будем обходить ваш набор ключей и значений и помещать их в это представление в памяти?

Или вы говорите о графическом представлении?