平衡KD树：哪种方法更高效？

Question

我正在尝试使用KD树平衡一组（百万级别的）3D点，我有两种方法可以实现。

方法1：

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

2. 遍历向量中的所有元素，并将它们与刚刚找到的元素进行比较，并将那些较小的放入newArray1中，而将那些较大的放入newArray2中

3. 递归

方法2：

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)排序的时间呢？

我该怎么做？还是有一种更好的方法可以做到我甚至没有看到吗？

- user1782677

---

数组大小除以2的第二大元素被称为中位数（如果你不知道的话）。 - mrk

基于哪个轴排序数组元素？每次在树中插入节点时我们需要进行排序吗？这些树是否平衡？ - Logicbomb

如果我有这些点(12,21),(13,27),(19,5),(39,5),(49,63),(43,45),(41,22),(27,7),(20,12),(32,11),(24.56)，那么我该如何按照你的算法步骤构建树形结构？ - Logicbomb

Answer 1

如何使用第三种方法：

1. 使用O(n)算法，如QuickSelect，确保在位置length/2的元素是正确的元素，所有在它之前的元素都比它小，所有在它之后的元素都比它大（不需要完全排序！） - 这可能就是您在第一种方法的第一步中使用的算法...

2. 递归进入每半（除了中间元素），并重复下一个轴。

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

我见过ELKI使用这个技巧。它使用的内存和代码都非常少，使树变得非常快。

- Has QUIT--Anony-Mousse

---

你能详细说明你的意思吗？你是说我应该有一个循环，并重复调用QuickSelect在0、1、2、3等上吗？那不会比for循环慢吗？ - user1782677

不。如果您运行QuickSelect，它实际上会将您的数组进行枢轴化，使得中位数位于中间，其他元素在中位数之前和之后按照期望排列。 - Has QUIT--Anony-Mousse

但是快速选择算法会把数组分成越来越小的子数组，然后返回第k大的元素。我不知道它如何在生成数十个子数组时只给我想要的两个数组。 - user1782677

一个干净的QuickSelect应该部分排序数组，而不是复制/破坏它。你可能自己实现了一个天真的QuickSelect？ - Has QUIT--Anony-Mousse

是的，我实现了自己的版本，其中我将数组分成两个子数组，并在每个子数组上递归调用quickselect - 但我现在明白你的意思了，我不应该对数组进行分区，而是在整个过程中使用同一个数组。 - user1782677

这与快速排序完全相同，只是您只需迭代进入其中一半，而不是递归进入两个部分。顺便说一下。 - Has QUIT--Anony-Mousse

Answer 2

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

- mrk

Answer 3

另一种方法：

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

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

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

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

- Kartal Tabak