我正在尝试编写自己的KD-Tree实现，并最终编写kNN实现。 而且我很难理解 KD 树如何构建搜索树。
在维基百科上，它说它找到值的中位数并将其用作树的根。
但是，当存在许多维度时，您将如何计算中位数？
你找不到几个维度的中位数（事实上，多维数字没有有意义的顺序）。在 kd 树的每个级别，您都专注于一个维度。您根据此维度选择中位数，忽略其他分量。
请注意，您可以使用除中位数以外的许多条件，具体取决于您要执行的操作。 同样，选择一个好的方案来决定每个节点的维度是一门艺术，尽管几乎每个方案都是正确的。
不需要找到中位数： 来自维基百科：
另请注意，不需要选择中点。在那 在这种情况下，结果只是不能保证树 将平衡。避免编码复杂内容的简单启发式方法 线性时间中位数查找算法，或使用 O（n log n） 类型的 所有n个点，就是用排序来求一个固定个数的中位数 随机选择的点作为分割平面。在实践中， 这种技术通常会导致树木平衡良好。
来自维基百科的KD树
您可以简单地根据一个维度对点进行排序，然后选择中位数作为根，然后递归构造子树（与其他维度排序）下面是一个实现：https://github.com/tavaresdong/cs106l/blob/master/KDTree/src/KDTree.h