用 C++ 实现二维 kd 树构造算法

Question

我正在开展一个个人项目，用 C++ 实现二维 kd 树构造算法。
我知道有些库已经做到了这一点，但我想获得 C++ 编程经验
（如果您有个人项目要显示，则有助于恢复）

输入：点数以及点本身（可以从命令行读取输入）

我希望它在 O(n log n) 时间内运行，可以这样做吗，如果是的话，有人可以提供一些伪代码来帮助我开始，提前致谢。

Answer 1

我最近一直在玩 kd-trees。这是一些未经测试的代码。 kd树的构建分两个阶段完成；遍历点列表，O(n)，并沿每个维度排序，O(nlogn)。所以，是的，你可以在 O(nlogn) 时间内构建 kd 树。

不过，在树中搜索（假设您正在寻找最近的邻居）会变得更加棘手。我还没有找到任何易于理解的文档。

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)