KD-Tree和R-Tree有什么区别？

Question

我查看了KD-Tree和R-Tree的定义。在我看来，他们几乎是一样的。

KD-Tree和R-Tree有什么区别？

Answer 1

R-Trees 和 kD-Trees 基于类似的想法（基于轴对准区域的空间分配），但主要区别是：

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

（有很多类似的树结构用于分区空间：四分之一，BSP-Trees，r*-trees等）

Answer 2

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

• R-Trees是 均衡, ，KD树不是（除非散装加载）。这就是为什么R-Trees首选用于更改数据的原因，因为可能需要重建KD树以重新启动。
• R-Trees是 面向磁盘. 。他们实际上在直接映射到盘盘表示的区域中组织了数据。这使它们在实际数据库和存储外操作中更有用。 KD树是 面向内存 并且不太平底放入磁盘页面
• R-树不涵盖整个数据空间。空地可能会被发现。 KD树总是覆盖整个空间。
• KD-Trees 二进制拆分 数据空间，R-Trees将数据划分为 矩形. 。二进制拆分显然是不相交的。虽然R-Tree的矩形可能重叠（实际上有时是好的，尽管人们试图最大程度地减少重叠）
• KD树在内存中更容易实现，这实际上是他们的关键好处
• R-Trees可以存储 矩形和多边形, ，KD树仅存储点向量（多边形需要重叠）
• R-Trees具有各种优化策略，不同的拆分，散装器，插入和再插入策略等。
• KD-Trees支持平方的欧几里得距离和Minkowski规范，而RTREES也已证明也支持大地距离（用于查找地理上的点附近）。

Answer 3

两者之间未提及的两个主要区别 这个答案 是KD-Trees仅在批量加载情况下有效。建造后，修改或重新平衡KD-Tree是不平凡的。 R-Trees不会遭受这一困扰。