Tag: data structure

I needed to get my head around how kd-trees work, so I coded up a simple implementation that just builds a tree. Naturally, add, delete, balancing etc methods would be required.

See wikipedia: kd-tree

    /*
     * Builds a kd-tree given an array of points
     */
    var kdtree = function(points, depth) {
        var axis, median, node = {};

        if (!points || points.length == 0) return;

        // alternate between the axis
        axis = depth % points[0].length;

        // sort point array
        points.sort((a, b) => a[axis] - b[axis]);

        median = Math.floor(points.length / 2);

        // build and return node
        node.location = points[median];
        node.left = kdtree(
            points.slice(0, median), depth + 1);
        node.right = kdtree(
            points.slice(median + 1), depth + 1);
        return node;
    }

Example usage would be:

var points = [ [2,3], [5,4], [4,7], [8,1], [7,2], [9,6] ];
kdtree(points, 0);