0

我有一个关于在 kd-tree 算法中划分空间的方式的问题。

假设我在平面上有点，具有 (x,y) 坐标。假设当点在同一条线上时，我们不在特定情况下。我在想为什么我们需要交替分割坐标，在一个级别，使用 x 轴，下一个级别，使用 y 轴。如果我们只使用 x 方向来分割空间，那么重要的是，我们总是有一棵二叉树，并且搜索算法总是取 log(n) 的平均值（假设我们有相对平衡良好的树）。

当我通过交替分割方向分割空间时，什么给了我更多？我想知道它是否与多维中的一些一般概率属性有关？

4

1 回答 1

0

我认为当您开始搜索树时会出现问题，例如使用窗口查询（矩形查询）。

-1,000让我们假设一个矩形数据集，在每个方向之间和每个方向上都有均匀分布的点1,000。如果您按 排序x，则应返回所有点的查询(-900 < x < 900) && (1 < y < 10)可能必须扫描几乎整个树。仅当您的查询仅限制而不是IE 时，log(n)搜索才会起作用。xy(1<x<10) && (-inf<y<+inf)

于 2015-11-13T12:05:20.820 回答