高级数据结构之R树（R-tree）

作者：Gausst松鼠会 | 2024-04-23 21:01:27

踩

r-tree

R树（R-tree）是一种将Ｂ树扩展到多维情况下得到的数据结构，它最初由Antonin Guttman于1984年提出。Ｂ树的结点中会存储一个键的集合，这些键把线分成片段，沿着那条线的点仅属于一个片段。因此，Ｂ树使得我们可以很容易地找到点。如果把沿线各处的点表示成Ｂ树结点，我们就能够确定点所属唯一子结点，在那里可以找到该点。

Ｒ树表示由二维或者更高维区域组成的数据，我们把它们称为数据区。一个Ｒ树的内结点对应于某个内部区域，或称“区域”，它不是普通的数据区。原则上，区域可以是任意形状，虽然实际中它经常为矩形或其他简单形状。例如上图中（a）是一棵Ｒ树，其中的一个内部结点R3R4R5就代表（b）中的一个区域，它被包含在R1之中。Ｒ树的结点用子区域替代键，子区域表示结点的子结点的内容，例如R3、R4、R5是结点R3R4R5中的键，它们中的

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/476004