摘要: 四叉树(quad-tree)是一种数据结构,是一种每个节点最多有四个子树的数据结构。 四叉树可以用来在数据库中放置和定位文件(称作记录或键)。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。 在树中,记录被存储在叶子的位置上。这...
四叉树(quad-tree)是一种数据结构,是一种每个节点最多有四个子树的数据结构。
四叉树可以用来在数据库中放置和定位文件(称作记录或键)。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。
在树中,记录被存储在叶子的位置上。这一名字的由来是因为记录被存储在端点上,它们上面再没有节点了。分支被称作节点。数的顺序是每节点的分支(也称孩子)数。在四叉树中,每个节点通常有4个孩子,因此顺序是4。四叉树的叶子数也是4。为达到想要的记录所进行的查找操作次数成为树的深度。
在实际的树中,可能有成千、成万或数十亿条记录。不是所有的叶子必须有一条记录,但至少要有一半包含记录。不包含记录的叶子称为空。在上面例子中,第8、第12、第16个叶子是空的,用空白圆来指示。