谁能告诉我KD-tree和R-tree有什么区别
我看看KD-tree和R-tree的定义，看起来它们差不多。
谁能告诉我KD-tree和R-tree有什么区别？ 谢谢
R树和K树是基于相似的思想（基于轴alignment区域的空间分割），但是关键的区别是：
- k棵树中的节点表示分离平面，而R树中的节点表示边界框。
- k d-trees将整个空间分割成区域，而R-树仅分割包含兴趣点的空间的子集。
- k d-trees表示不相交的分区（点只属于一个区域），而R-树中的区域可能重叠。
（有很多类似的树结构用于划分空间：四叉树，BSP树，R *树等等）
他们实际上是完全不同的。 它们的用途相似（对空间数据进行区域查询），它们都是树木，但这些都是他们所有的共同点。
- R树是平衡的 ，kd树不是（除非批量加载）。 这就是为什么R树更适合改变数据的原因，因为kd树可能需要重build以重新优化。
- R-Trees是面向磁盘的 。 他们实际上将数据组织在直接映射到磁盘表示的区域中。 这使得它们在真实数据库和内存不足操作中更有用。 kd-trees是以内存为导向的，并且可以放入磁盘页面
- R-树不覆盖整个数据空间。 空的地方可能被发现。 kd-trees总是覆盖整个空间。
- kd-trees 二进制分割数据空间，r-trees将数据分割成矩形 。 二元分裂显然是不相交的; 而r-树的矩形可能会重叠（实际上有时是好的，虽然人们试图最小化重叠）
- kd-trees在内存中实现起来要容易得多，这实际上是他们的主要好处
- R树可以存储矩形和多边形 ，kd树只存储点向量（因为多边形需要重叠）
- R树带有各种优化策略，不同的分割，批量加载器，插入和重新插入策略等。
Gareth Rees没有提到的两个主要区别在于，Kd树只能在批量加载情况下有效。 一旦build成，修改或重新平衡Kd树是不平凡的。 R树不会受到这个。
