Kd树：数据仅存储在叶子节点还是存储在叶子节点和中间节点？

Question

我正在尝试在C ++中实现Kd树来执行最近邻和近似最近邻搜索。到目前为止，我已经遇到了两个版本的最基本的Kd树。

1. 其中数据存储在节点和叶子中，例如这里
2. 只有叶子中存储数据，例如这里

它们似乎从根本上相同，具有相同的渐近特性。

我的问题是： 为什么要选择一个而不是另一个？

我找到了两个原因：

1. 在节点中存储数据的树比只在叶子中存储数据的树浅1级。
2. 只在叶子中存储数据的树更容易实现delete data函数

在决定制作哪个之前，还有其他理由需要考虑吗？

- Martin Drozdik

---

@Boris Strandjev，谢谢！ - Martin Drozdik

为什么是第二个原因呢？我想即使使用第二种方法，您也会在中间节点中存储一些距离数据吧？ - Boris Strandjev

@BorisStrandjev 在第一种方法中，如果您删除一个节点，则需要找到替换节点。这可以通过搜索以该节点为根的子树来实现。在第二种方法中，您只需删除叶子节点即可。 - Martin Drozdik

但是你仍然需要更新中间节点中的数据吗？ - Boris Strandjev

是的，那是更好、更勤奋的方法。但第二棵树让你选择使用懒惰的方法，而不修改中间节点。 - Martin Drozdik

Answer 1

您可以将节点标记为已删除，并将任何结构更改推迟到下一个树重建中。k-d树随着时间的推移而退化，因此您需要频繁地重建树。对于不经常更改或可以轻松重建（近似）最优树的低维数据集，k-d树非常适合使用。

关于实现树，我建议使用简洁的结构。我通常不使用节点，而是使用数据对象引用的数组。轴由当前搜索深度定义，无需在任何地方存储它。左右邻居由数组的二叉搜索树给出。（否则，只需添加一个字节数组，大小为数据集的一半，用于存储您使用的轴）。通过专门的快速排序完成加载树。理论上它是O(n^2)的最坏情况，但是通过使用良好的启发式算法（例如五个中值）可以可靠地获得O(n log n)，并且具有最小的常数开销。

虽然对于C/C++不是很适用，但在许多其他语言中，管理大量对象会付出相当大的代价。 type* []是您可以找到的最便宜的数据结构，特别是它不需要太多管理工作。要标记元素为已删除，可以将其 null ，并在遇到 null 时搜索两侧。对于插入，我建议首先将它们收集在缓冲区中。当修改计数器达到阈值时，进行重建。

这就是它的全部意义所在：如果您的树非常便宜可以重建（与几乎预先排序的数组重新排序一样便宜！），那么频繁重建树不会造成任何损害。线性扫描短的“插入列表”非常CPU高速缓存友好。跳过 null 也非常便宜。

如果您想要一个更动态的结构，我建议看一下R * -trees。它们实际上是为了在插入和删除时保持平衡，并将数据组织在面向磁盘的块结构中而设计的。但即使对于R-trees，也有报告称，保留插入缓冲区等来推迟结构更改可以提高性能。在许多情况下，批量加载也会有很大帮助！

- Erich Schubert

---

非常感谢您的详细解释。然而，有几个点我还不太清楚。1. 您说您不使用节点是什么意思？2. 关于我的问题，您能否更具体地说明一下？即这两棵树的比较。 - Martin Drozdik

实际上，您可以在不使用“节点”数据类型的情况下实现kd树。总内存成本：n个指针。而且，代码越简单，通常越快。我还想传达的是：您可以实现良好或缓慢的kd树。没有规则表明哪种更好，而是取决于您如何为特定需求实现它们。 - Erich Schubert