Kd树:仅存储在树叶中的数据与存储在树叶和节点中的数据

Question

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

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

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

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

到目前为止，我认为有两个原因：

1. 在节点中存储数据的树也较浅1层。
2. 只在树叶中存储数据的树更易于实现delete data函数。

，在决定制作哪一个之前，我还需要考虑其他一些原因吗？

Answer 1

您只需将节点标记为已删除的，并将任何结构更改推迟到下一次树重建。随着时间的推移，K-d树会退化，所以你需要频繁地重建树。K-d树对于低维数据集是很好的，这些数据集不会改变，或者你可以很容易地重建一棵(近似)最优的树。

至于实现树，我建议使用极简结构。我通常不使用节点。我使用一个数据对象引用数组。轴是由当前搜索深度定义的，不需要存储在任何地方。左右邻由数组的二进位搜索树给出。(否则，只需添加一个byte数组，其大小为数据集的一半，用于存储所使用的轴)。加载树是由一个专门的QuickSort完成的。从理论上讲，这是O(n^2)最坏的情况，但是如果有一个很好的启发，比如中位数为-5，您就可以相当可靠地得到O(n log n)，并且开销最小。

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

这就是它的全部意义:如果你的树真的很便宜重建(就像诉诸一个几乎预先排序的数组一样便宜！)因此，频繁地重建这棵树是无害的。线性扫描短的“插入列表”是非常友好的CPU缓存。跳过null也很便宜。

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