四叉树和kd树的区别

Question

四叉树和kd-tree之间的主要区别是什么？我知道它们都可以在多个维度中分割点，但我不明白为什么会选择其中之一。

我需要一种结构，可以让我计算在给定区域内有多少个点（2D点）。基本上，我正在尝试检测点的聚集。

- Mauricio Galindo

---

请参见http://cstheory.stackexchange.com/questions/8470/why-would-one-ever-use-an-octree-over-a-kd-tree - naught101

Answer 1

算法上的不同之处在于：在四叉树中，到达一个节点的数据被分成固定（2 ^ d）大小的等分单元格，而在kd树中，数据是基于某些数据分析（例如某些坐标的中位数）分为两个区域。由于在维度上呈指数依赖关系，四叉树在高维情况下无法很好地扩展。这两种数据结构的查询时间复杂度也有所不同。

由于您对2D点感兴趣，任何一种数据结构都可以使用。KD树非常容易查询范围，通常优先于四叉树。我建议您使用它们。

- killogre

---

注意：kd树在维度数量上也呈指数级增长。主要区别在于，kd树最终会变得更深但更窄。 - Apollys supports Monica

深度与维度数量有什么关系？深度不是$\log(N)$吗？ - Eduardo Reis

在四叉树的 d 维版本中，宽度随深度呈指数级增长。只有在数据平衡时，深度才为 log(N)，但这种情况不太可能发生。@EduardoReis - killogre