我有一个关于kd树算法中空间划分方法的问题。
假设我在平面上有点，坐标为（x，y）。假设当点在同一条线上时，我们不是处于特定的情况。我在想为什么我们需要交替分割坐标，在一个级别上，使用x轴，在下一个级别，使用y轴。重要的是，如果我们只使用x方向来分割空间，我们总是有一个二叉树，搜索算法总是取log（n）的平均值（假设我们有一个相对平衡的树）。
当我通过交替的分割方向来分割空间时，什么能给我更多的帮助？我想知道它是否与多维中的一些一般概率性质有关？
我认为问题出现在您开始搜索树时，例如使用窗口查询（矩形查询）。
让我们假设一个矩形数据集，其中-1,000和1,000之间的点在每个方向上均匀分布。如果按x排序，那么应该返回(-900 < x < 900) && (1 < y < 10)的所有点的查询可能必须扫描几乎整个树。只有当您的查询仅限制x而不限制y（即(1<x<10) && (-inf<y<+inf)）时，log(n)搜索才会起作用。