谁能告诉我KD-tree和R-tree有什么区别

Question

我看KD-tree和R-tree的定义，看起来它们差不多。

谁能告诉我KD-tree和R-tree有什么区别？感谢

Answer 1

R-trees和kd-trees基于类似想法（基于轴对齐区域空间分割），但是关键的差异是：

• 节点在ķ d树表示分离平面，而节点在R树中表示边界框。
• k d-trees将整个空间划分为区域，而R-树只划分包含感兴趣点的空间子集。
• k d-trees表示不相交的分区（点只属于一个区域），而R树中的区域可能重叠。

（有很多相似种的树结构的用于划分空间：四叉树，BSP树，R * - 树，等等，等等）

Answer 2

两者之间的主要区别不被提及加雷里斯是Kd树只在批量加载情况下才有效。一旦构建，修改或重新平衡Kd树是非平凡的。 R树不会因此受到影响。

Answer 3

它们实际上完全不同。它们的用途相似（对空间数据的区域查询），它们都是树木，但这是关于它们所有的共同点。

• R-树木是均衡，KD-树不是（除非批量加载）。这就是为什么R树可以用来改变数据的原因，因为kd树可能需要重建以重新优化。
• R-Trees是面向磁盘。他们实际上将数据组织在直接映射到磁盘表示的区域中。这使它们在真实数据库和内存不足操作中更有用。 kd-trees是面向内存的并且是不平凡的放入磁盘页面
• R树不覆盖整个数据空间。空的区域可能被揭露。 kd-trees总是覆盖整个空间。
• kd-trees 二进制拆分数据空间，r-trees将数据分区为矩形。二元分裂显然是不相交的;虽然r-tree的矩形可能会重叠（实际上有时很好，尽管试图使重叠最小化）
• kd-trees在内存中实现起来要容易得多，这实际上是它们的关键优点
• R-树可以存储矩形和多边形，kd-trees只存储点向量（因为多边形需要重叠）
• R树带有各种优化策略，不同的分割，批量加载器，插入和重新插入策略等。