Do I need Generics for these node and tree classes?

I want to implement KD tree. I have defined class Node as follows:

public static class Node{
    int id;
    public double x;
    public double y;
    public Node leftChild;
    public  Node rightChild;
    Node(int id, double x, double y){
        this.id = id;
        this.x = x;
        this.y = y;
        leftChild = null;
        rightChild = null;
    }
}

Then I have defined class KDTree in which I want to implement method contains(Node t):

public static class KDTree{
    Node root;
    KDTree(Node root){
        this.root = root;
    }
    boolean contains(Node t){
        if (t == null)
            return false;
        if (t.x == root.x && t.y == root.y)
            return true;
        else
            return ...; //something else
    }
}

Do I need to use generics in class KDTree? I'm not aware of when it is a good practice to use generics and when it is not? It would be nice if someone can recommend me an article on when we have to use generics and when we don't have to.

As far as I read the declaration public static class KDTree means "class KDTree contains objects that extends type Node". Is there any way to declare that class KDTree contains only objects of type Node?

Class Node represents a point in the plane, given by its x and y coordinate. Class KDTree is a tree-structure that stores the points in such a way that it is easy to answer queries of the type: give me m nearest points to my point p(x1, y1). This is the method that I use to construct KDTree:

public static Node buildKDTree(List list, boolean depth, int begin, int end){
    int middle = median(list, depth, begin, end);
    Node root = list.get(middle);
    root.leftChild = buildKDTree(list, !depth, begin, middle-1);
    depth = !depth;
    root.rightChild = buildKDTree(list, !depth, middle+1, end);
    return root;
}

I think that you have confused yourself with your code, and the way that data structures are intended to be implemented.

What you have done that is unconventional, and causing the confusion, is that you have exposed the Node class as a public class, and you have a constructor that takes Nodes as input.

Node is normally an implementation detail of a data astructure (your KDTree) that is transparent to others. Consider Java's LinkedList, that has Node instances, but you never see those Node instances, just like ArrayList has an internal array, etc.

Your KDTree should contain the Node class as an inner (nested) private class, and the users of your KDTree should never be able to see/access those nodes. Your KDTree class should abstact that interaction away.

The constructor for your KDTree should be able to construct off the base values of the node, or be an empty constructor, and have an add method that takes the base values.

Consider something that looks like:

public static class KDTree {

    private static class Node{
        int id;
        public double x;
        public double y;
        public Node leftChild;
        public  Node rightChild;

        Node(int id, double x, double y){
            this.id = id;
            this.x = x;
            this.y = y;
            leftChild = null;
            rightChild = null;
        }
    }

    private Node root = null;

    public KDTree(){
        // empty constructor
    }

    public boolean add(int id, double x, double y) {
        Node toadd = new Node(id, x, y);

        .... add toadd to hierarchy....

    }

    public boolean contains(int x, int y) {
        .....
    }

}

Note, the Node is private, and not visible outside the KDTree class.

It is possible that you need some other form of data structure to represent the actual data in the Node, like a Point class, and, your Node could have a reference to a Point instance. Point strikes me as being a data structure you need anyway, and probably already have.

Note that your x and y values are doubles, and any time I see == comparisons with doubles, I caution people that it is not as reliable as you would expect:

if (t.x == root.x && t.y == root.y)

Be careful there, it's possible that t.x and root.x are very, very, very close to each other, but not quite the same, due to some rounding value in a calculation, or something at the 15th decimal place, or something.

StackExchange Code Review Q#56176, answer score: 5