5

我正在尝试使用 KD-tree 平衡一组（百万 +）3D 点，我有两种方法可以做到这一点。

方式一：

  1. 使用 O(n) 算法找到沿给定轴的数组大小/第 2 大元素并将其存储在当前节点

  2. 遍历向量中的所有元素，并将它们与我刚刚找到的元素进行比较，然后将较小的元素放在 newArray1 中，将较大的元素放在 newArray2 中

  3. 递归

方式二：

  1. 使用快速排序 O(nlogn) 沿给定轴对数组中的所有元素进行排序，获取位置 arraysize/2 处的元素并将其存储在当前节点中。

  2. 然后将索引 0 到 arraysize/2-1 的所有元素放入 newArray1 中，将 arraysize/2 到 arraysize-1 中的所有元素放入 newArray2

  3. 递归

方式 2 似乎更“优雅”，但方式 1 似乎更快，因为中值搜索和迭代都是 O(n)，所以我得到 O(2n)，它只是减少到 O(n)。但同时，即使方式 2 是 O(nlogn) 时间进行排序，将数组拆分为 2 可以在恒定时间内完成，但它是否弥补了 O(nlogn) 时间进行排序？

我该怎么办？或者有没有更好的方法来做到这一点，我什至没有看到？

4

3 回答 3

3

方式3怎么样：

  1. 使用诸如 QuickSelect 之类的 O(n) 算法来确保位置 length/2 处的元素是正确的元素，之前的所有元素都小于它，之后的所有元素都大于它（没有对它们进行完全排序！） - 这可能是无论如何，您在第 1 步第 1 步中使用的算法......

  2. 递归到每一半（中间元素除外）并重复下一个轴。

请注意，您实际上不需要制作“节点”对象。您实际上可以将树保存在一个大数组中。搜索时，从第一个轴的长度/2 开始。

我已经看到 ELKI 使用了这个技巧。它使用很少的内存和代码，这使得树非常快。

于 2013-06-10T13:40:54.647 回答
0

其他方式：

对每个维度进行排序：O(KN log N)。这将只执行一次，我们将使用维度上的排序列表。

对于当前维度，在 O(1) 时间内找到中位数，在 O(N) 时间内拆分中位数，在 O(KN) 时间内拆分每个维度的排序数组，然后递归下一个维度。

这样，您将在开始时执行排序。并对每个子树执行 (K+1) 次拆分/过滤，以获得已知值。对于小 K，这种方法应该比其他方法更快。

注意：算法所需的额外空间可以通过 Anony-Mousse 指出的技巧来减少。

于 2013-06-23T20:29:34.910 回答
0

请注意，如果查询超矩形包含许多点（例如所有点），则树是否平衡并不重要。如果查询超矩形很小，则平衡树很有用。

于 2013-10-24T20:56:35.343 回答