3
\$\begingroup\$

I want to construct KD-Tree from unsorted List of points in the plane (i.e. 2-KD-Tree). To do so I used the method from Wikipedia: http://en.wikipedia.org/wiki/Kd-tree#Construction This is my code:

public static Node buildKDTree(List<Node> list, boolean depth){
    if(depth){
        Collections.sort(list, Node.xComparator);
    }
    else{
        Collections.sort(list, Node.yComparator);
    }
    int middle = list.size()/2;
    Node root = list.get(middle);
    List<Node> left = new ArrayList<Node>();
    for (int i = 0; i < middle; i++) {
        left.add(list.get(i));
    }
    List<Node> right = new ArrayList<Node>();
    for (int i = middle+1; i < list.size(); i++) {
        right.add(list.get(i));
    }
    root.leftChild = buildKDTree(left, !depth);
    depth = !depth;
    root.rightChild = buildKDTree(right, !depth);
    return root;
}

The implementation of Node class is not impotrant (I think). What I dont like in my code is that in each iteration I spend O(n) time to copy the first half of the sorted list into new list (left) and then do the same for the other half of the list(right). Is there any way to avoid this? I was thinking to include indexes begin and end as parameters to my method but I dont see how it would speed up, since I dont know method for collectios that will sort the collection partly, i.e. from begin to middle and then from middle to end.

\$\endgroup\$
1
\$\begingroup\$
List.subList(low, high)

Is probably the easiest approach to take to the list management without requiring the copying of a lot of nodes. It does make a lot of Lists though, which are very short lived. This should be fine. If you really needed to keep things under control, then you would replace the sublist implementation with one that uses Arrays.sort(a[], low, high, Comparator)

Reviewing the code as is:

root.leftChild = buildKDTree(left, !depth);
depth = !depth;
root.rightChild = buildKDTree(right, !depth);

This looks to me like a bug - I would expect each layer of the tree to be sorted in the same direction, so flipping the bit doesn't make sense. Instead

root.leftChild = buildKDTree(left, !depth);
root.rightChild = buildKDTree(right, !depth);

I don't like using the boolean to control the direction of the insert -- the variable is answering a question about direction, not logical truth. An enum would be a more readable fit

private enum SORT_DIRECTION {
    X_SORT, Y_SORT;
}

Alternatively, it might be clearer to track how deep you are in the tree, and choose the direction of the sort based on the depth. In that case, depth would be an int, and you would use something like a modulus operation to choose which way you want the comparators to go.

Comparator<Node> order = Node.xComparator;

if(0 == (depth % 2){
    order = Node.yComparator;
    Collections.sort(list, Node.xComparator);
}
Arrays.sort(nodes, low, high, order);

Or better, explicitly spell out what you are doing

Comparator order = getOrderForDepth(Node, depth); Arrays.sort(nodes, low, high, order);

When dealing with recursion, my usual recommendation is to have a different function set up your pre conditions, and return the root.

Node buildKDTree(List list) { int depth = 0; return buildKDTree(list, depth); }

Finally, when implementing something recursively, make sure that you have a clear and obvious terminating condition (in other words, you need to handle the case where there are no more sub trees). In this case, it's probably easiest to manage if the buildKDTree method handles an empty List.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.