Tree representation in java

Question

I am working on my thesis work that is relevant to the artificial intelligent domain.

I want to make a real time recommendation system so I need to represent the decisions with a tree.

My main question is how can I represent this tree in an efficient way? I want to mention that the tree will be traversing both bottom-up and up to bottom. Also the tree is not binary and the node that it has are quite many (over 100).

Right now I have create a node class like the above:

public class node {

    private String nodeName;
    private expectedValue ev;
    private boolean isLeaf;
    private boolean isRoot;
    private List<node> listOfChildren = new ArrayList<node>();
    private node parent;


    public node(String nodeName) {
        super();
        this.nodeName = nodeName;
    }


    public node(String nodeName, boolean isLeaf, boolean isRoot, List<node> listOfChildren, node parent) {
        super();
        this.nodeName = nodeName;
        this.isLeaf = isLeaf;
        this.isRoot = isRoot;
        this.listOfChildren = listOfChildren;
        this.parent = parent;
    }


    public void initializeNode(boolean isLeaf, boolean isRoot, List<node> listOfChildren, node parent) {
        this.isLeaf = isLeaf;
        this.isRoot = isRoot;
        this.listOfChildren = listOfChildren;
        this.parent = parent;
    }


    //getter and setter here......  
}

But I believe that it is not the most efficient way to represent a tree....

So, what is an efficient way to represent a tree in Java and is there a way to create the tree dynamically or do I have to initialise it one by one node?

Thank you!

I flagged it as 'too broad'/'opinion based' as there is no correct answer to your request. It also depends a lot on the exact requirements of the tree. Btw, you don't need "isLeaf" (listOfChildern.size() == 0) or "IsRoot" (parent == null). — Reinard, Jan 07 '16 at 11:49
Why do you "believe it is not the most efficient way to represent a tree"? What are some of the problems you see with it? — Dima, Jan 07 '16 at 11:49
Possible duplicate of [Tree implementation in Java (root, parents and children)](http://stackoverflow.com/questions/19330731/tree-implementation-in-java-root-parents-and-children) — Rob Audenaerde, Jan 07 '16 at 12:04
@Dima : Because of the fact that this system is going to run real time and also the tree has a lot of nodes, i believe that the overhead of the lists (for example list Of Children) is too big and it could be done in a more efficient and "elegant" way. — MixPap, Jan 07 '16 at 12:13
In order to elicit a most helpful answer, can you provide data / estimates on the relative frequency of operations (add, update, delete; possibly shuffle, reattach, etc.) on the nodes, possibly taking into account typical sequences of operations? Since the target is a recommendation system, optimizing for minimized query times might be the best way to go. — collapsar, Jan 07 '16 at 12:15
@MixPap You'll have the overhead one way or the other unless you can guarantee a fan-out bound and can afford to allocate the maximum number of child slots for each node upon creation ( this still requires effectively list management if deletions and reinsertions are permitted at runtime). A more sophisticated scheme would provide for both, preallocated child slots and dynamic list management, entailing overhead of its own. However, I feel that in a recommender system, non-mutating queries occur more frequently than changes to the tree, so lists may be less expensive than you think. — collapsar, Jan 07 '16 at 12:23
@MixPap "too big" is a relative term. "You think the overhead is too big" _compared to what_? — Dima, Jan 07 '16 at 13:15

Idos · Answer 1 · 2016-01-07T12:30:49.247

2

I think you don't need so many variables to be passed to your constructor. It could be much simpler. I would recommend to have a separate static inner class (nested class) for the Node. Also take advantage of java generics (<T>) Something like this:

public class MyTree<T> {

    private Node<T> root;

    public MyTree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

As a side note, there is a tree structure implemented in the JDK which you may use even without a swing interface. (javax.swing.tree TreeModel and TreeNode )

edited Jan 07 '16 at 12:30

answered Jan 07 '16 at 11:49

Idos

15,053
14
60
75

(This comment is irrelevant to the content of this reply.)The world is full of strangers. Why making an enemy rather than a friend. I am a bit over reacted to your comment today. Enjoy your journey in S.O. (Strange, I cannot @ you). – smwikipedia Jan 07 '16 at 12:31
@smwikipedia you can delete the comments here :) – Idos Jan 07 '16 at 12:38
1

@ldos They're educative. Let's keep them if it's not against the rules. – smwikipedia Jan 07 '16 at 12:39
@idos thank you for your answer. i was't aware of java generics () so i have to look further to it. – MixPap Jan 08 '16 at 15:24

Tree representation in java

1 Answers1