arrays - 1维排序数组: KD-Tree vs Binary Search

Question

只是为了验证，我是否正确，如果:

• 我有一个排序的一维数组。
• 使用 KD 树的最近邻搜索最多与对该数组使用二分搜索一样快？ (对于正常搜索当然是一样的)
• 范围搜索也是如此(获取 x..y 范围内的所有元素)。
• 我使用 KD 树的唯一优势是在频繁插入/删除数据时。

这已被要求用于一般的二叉树和 N 维，但我想知道关于 KD-Tree 和 1 特别是尺寸数据。

Answer 1

A nearest neighbor search using a KD-Tree will always be at best as fast as using a binary search on that array? (For normal search of course the same)

正确。如果 KD 树稍微退化(通过更新操作)，你的情况会更糟。

The same goes for range search (getting all elements in range x..y).

正确。使用二分查找找到大于 x 的最小值后，您可以扫描直到找到 y。在 KD 树中，您必须遍历范围内键所在的所有节点。

The only advantage that I may have with a KD-Tree is when there is frequent insertion / deletion of the data.

这取决于你所说的优势。

在 KD 树中插入和删除比在排序数组中更快。

但是，随着更多的插入/删除，对 KD 树的搜索会变得更慢，因为 KD 树会退化(如果您只使用基础 KD 树而没有适应更新)。二进制搜索将停留在 O(log n)。

这不是您的问题，但是，如果您在一维环境中操作，您很可能会使用两全其美的方法，这意味着 Red-Black Trees , B+-Trees或类似的东西。