跳转到内容

四叉树

本页使用了标题或全文手工转换
维基百科,自由的百科全书
四叉树
类型
发明时间1974年
发明者拉斐尔·芬克尔乔恩·本特利
大O符号表示的时间复杂度
算法 平均 最差
四叉树区块的点资料分布图

四叉树(英语:Quadtree)是一种树状数据结构,在每一个节点上会有四个子区块。四叉树常应用于二维空间资料的分析与分类。 它将资料区分成为四个象限。资料范围可以是方形或矩形或其他任意形状。这种数据结构是由 拉斐尔·芬克尔乔恩·本特利在1974年发展出来。类似的资料分割方法也称为 Q-tree。所有的四叉树法有共同之特点:

  • 可分解成为各自的区块
  • 每个区块都有节点容量。当节点达到最大容量时,节点分裂
  • 树状数据结构依造四叉树法加以区分

形态

[编辑]

四叉树可以用他们资料形态的表示法来作分类,资料形态的项目有:区域、点、直线及曲线。四叉树也可以进行分类,不管树的形态是否独立于已处理过的排秩资料。一些四叉树的形态如下所示:

四叉树区块

[编辑]

四叉树区块表示为空间的分割,即在二维上分区块为四组相同的象限、次象限等,且每个叶节点包含有关特殊次区块的资料。树里的每个节点不是正好有4个子节点,就是没有子节点(为一个树叶节点)。四叉树区块不是严格的一颗'树' - 且位置的次分割与资料无关。他们是比较精确一些称为'单词查找树'.

在一个深度为n的四叉树区块中可以用来表示一个影像包含有2n × 2n的像素,每个像素的值为0或1。根节点表示全部影像区块。假如像素在任何区块不是全部为0或1,那就可以进行画分。在这个应用中,每个叶节点代表一个段落的像素、段落像素里面包含全部为零或全部为一的组合。

四叉树区块也可以用为一种资料区块上不同变化解析的表达法。比如,温度在一个区块中可以存储为一个四叉树,而树叶节点存储著平均温度涵盖到它所拥有的次区块。

假如四叉树区块被用来表达一组点资料(诸如一组城市的经纬度),区块就进行次分割直到每个叶节点包含最多一个单点。

点四叉树

[编辑]

点四叉树修改自二叉树用来表示二维的点资料。点四叉树与四叉树都有共同的特点,不过于次分割的中心总是在一点时、点四叉树视为一真树(true tree)。树的形态根据编过序的资料而定。在比较二维规律资料点上是相当有效率的,经常运作在O(log n)时间复杂度内。

点四叉树的节点结构

[编辑]

点四叉树的节点类似于二叉树的节点,它们之间的主要差别在于点四叉树有4个指针(每一个象限一个指针)、而一般二叉树只有2个指针(左指针及右指针)。点四叉树的键值也是经常被分解为两部分,如在直角坐标上的 x 及 y 值。因此,一个节点包含下列信息:

  • 4个指针(Pointer):quad[‘NW’](西北)、quad[‘NE’](东北)、quad[‘SW’](西南)、及quad[‘SE’](东南)。
  • 点;含有如下项目:
    • 键值;通常以直角座标(x, y)值来表示。
    • 值;比如是"名字"。

边四叉树

[编辑]

边四叉树是专门用来存储直线而不是点。曲线能分割每格到很接近精细的分辨率。如此能产生极度的不平衡树,而此不平衡树可能推翻索引的使用目的。

一些四叉树的常用法

[编辑]

四叉树为八叉树的二维模拟。

区辨说明

[编辑]

假如几何次分割不能减缩每个四叉树的项目数时,(例如,在资料重叠时)则四叉树的次分割失败,为了使算法能够继续进行其容量必须突破限制。比如,一个四叉树最大的容量为8,而且有9个点在(0, 0),次分割将会造成3个空的四叉树,且每个空四叉树会包含最初的9个点,再次分割依此类推。因为树必须允许在这样的象限内超过8点,如此四叉树对带有任意几何(比如:地图或图形)的资料集才能够达到O(N)的时间复杂度。

注释

[编辑]
  1. ^ Tomas G. Rokicki. An Algorithm for Compressing Space and Time. 2006-04-01 [2009-05-20]. (原始内容存档于2012-10-02). 

参考资料

[编辑]
  1. Raphael Finkel and J.L. Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica. 1974, 4 (1): 1–9. doi:10.1007/BF00288933. 
  2. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry 2nd revised edition. Springer-Verlag. 2000. ISBN 3-540-65620-0.  Chapter 14: Quadtrees: pp.291–306.

参看

[编辑]

外部链接

[编辑]