Implement a 2-dimensional kd-tree construction algorithm in C++

Question

I'm working on a personal project to implement a 2-dimensional kd-tree construction algorithm in C++.
I know there are libraries that already do this, but I want to gain experience in C++ programming
(helps in resume if you have personal projects to show)

Input: number of points, and the points themselves (input can be read in from command line)

I want this to run in O(n log n) time, can this be done, if so can someone provide some pseudo-code to help get me started, thanks in advance.

Answer 1

I've been playing around with kd-trees recently. Here's some untested code. kd-tree construction in done in 2 stages; traversing the list of points, O(n), and sorting along each dimension, O(nlogn). So, yes, you can construct kd-trees in O(nlogn) time.

Searching through the tree (say you are looking for nearest neighbors), gets trickier though. I haven't found any easy-to-follow documentation for that.

struct Node
{
    int[2] point;
    Node* left;
    Node* right;
}

Node* createtreeRecursive (int** values /* int[2][len] */, int len, int dim = 2, int depth = 0)
{
    // If empty, return
    if (value <= 1) return null;

    // Get axis to split along
    int axis = depth % dim;

    int** sorted = sortAlongDim (values, axis);

    int mid = len / 2;
    Node* curr = new Node ();
    curr.point[0] = sorted [0][mid];
    curr.point[1] = sorted [1][mid];

    int** leftHalf = values;
    int** rightHalf = &(values [mid]);

    curr.left = createtreeRecursive (leftHalf, mid, dim, depth + 1);
    curr.right = createtreeRecursive (rightHalf, len - mid, dim, depth + 1);

    return curr;
}

int** sortAlongDim (int** values, int axis)