What is the best datastructure for hierarchical data representation in java?

Question

I need to create a data structure in java which can represents hierarchy of data. Example use case is shown in the image below.

an organization hierarchy

In my case only the leaves level will have data, and the internal nodes should act like indexes. I should be able to get data from the data structure using multiple keys(Composite keys).

Is it okay to use nested maps, or should I implement an m way tree(B tree/B+ tree) for this use case.

You should implement proper classes, as the different hierarchy levels have a set type (university -> faculty -> field). — Kayaman, Oct 07 '19 at 10:50
refer https://stackoverflow.com/questions/3522454/java-tree-data-structure — GaneshSreeju, Oct 07 '19 at 10:55
Thanks for responding. In my usecase only the leaf level will have values, internal nodes should act like indexes. — Vishnu Prakash, Oct 07 '19 at 10:56

score 1 · Answer 1 · answered Oct 07 '19 at 10:59

If the structure of the nested data is constant you could use normal classes with properties.

If the structure is dynamic I would use Maps, the interface and ignore the implementation.

About using using a custom tree structure, if you can use classes, thats better. If you use Maps, I would start with a HashMap and if you find it to be a problem your can replace your Map to something else later.

score 1 · Answer 2 · answered Oct 07 '19 at 11:53

Obviously you have to use Tree like data structure. Here is the sample code of that.

High level code idea

class Entity{  
    // declare you attributes and below two properties

    List<Entity> children;

    boolean isleafNode;// for parent node its 'false' and for leaf node it will 'true'

    }

score 1 · Answer 3 · answered Oct 07 '19 at 17:05

you can implement Trie for this use case. Iterate over composite key and return data if found.

class definition:

public class TrieNode {
    private HashMap<String, TrieNode> children;
    private Data data;
    private boolean isLeaf;

   // ...
}

find query will look like:

public Data find(List<String> compositeKey) {
    TrieNode current = root;
    for (String key: compositeKey) {
        TrieNode node = current.getChildren().get(key);
        if (node == null) {
            return null;
        }
        current = node;
    }
    if(current.isLeaf()) {
       return current.getData();
    } else {
       return null;
    }         
}

insert will look like:

public void insert(List<String> compositeKey, Data data) {
    TrieNode current = root;

    for (String key: compositeKey) {
        current = current.getChildren()
          .computeIfAbsent(key, c -> new TrieNode());
    }
    current.setLeaf(true);
    current.setData(data);
}

What is the best datastructure for hierarchical data representation in java?

3 Answers3