How to do a search on a k-dimensional tree (KDTree)

Question

How to do a search on a k-dimensional tree (KDTree)

Navigation

#1 by (1 votes)

1

I have a tree 2 dimensions and its structure is as follows:

public class KDNodo{
   int x;
   int y;
   KDNodo left;
   KDNodo rigth;
}
public KDTree{
    KDNodo root;
}

It is necessary to have in the odd levels the x is taken and that the nodes that have values lower than x are put to the left and those that have values superior or equal to the right.

Even levels do the same but with the y.

Can someone give me an example of a search? Thanks.

java

asked by UnaiLopez 19.11.2017 в 12:50

source

1 answer

why does my toolbar appear below the fragments elements? SVG with height auto not shown in firefox

score 1 · Accepted Answer

I do not understand the configuration of your tree well, but if I take it literal I would do these methods to insert:

public class KDTree{
    KDNodo root;


    public void insertaNodo(KDNodo nodo) {
        if (nodo == null) {
            throw new IllegalArgumentException();
        }
        if (root == null) {
            root = nodo;
        }
        else {
            insertaParEn(nodo, root);
        }
    }

public void insertaParEn(KDNodo nuevo, KDNodo actual) {
    if (nuevo.x < actual.x) {
        if (actual.left == null) {
            actual.left = nuevo;
        }
        else {
            insertaInparEn(nuevo, actual.left);
        }
    }
    else if (actual.rigth == null) {
        actual.rigth = nuevo;
    }
    else {
        insertaInparEn(nuevo, actual.rigth);
    }
}

public void insertaInparEn(KDNodo nuevo, KDNodo actual) {
    if (nuevo.y < actual.y) {
        if (actual.left == null) {
            actual.left = nuevo;
        }
        else {
            insertaParEn(nuevo, actual.left);
        }
    }
    else if (actual.rigth == null) {
        actual.rigth = nuevo;
    }
    else {
        insertaParEn(nuevo, actual.rigth);
    }
}