四叉树
四元树(英语:Quadtree)是一种树状资料结构,在每一个节点上会有四个子区块。四元树常应用于二维空间资料的分析与分类。 它将资料区分成为四个象限。资料范围可以是方形或矩形或其他任意形状。这种资料结构是由 拉斐尔·芬克尔与乔恩·本特利在1974年发展出来。类似的资料分割方法也称为 Q-tree。所有的四元树法有共同之特点:
- 可分解成为各自的区块
- 每个区块都有节点容量。当节点达到最大容量时,节点分裂
- 树状资料结构依造四元树法加以区分
四叉树 | |||||
---|---|---|---|---|---|
类型 | 树 | ||||
发明时间 | 1974年 | ||||
发明者 | 拉斐尔·芬克尔、乔恩·本特利 | ||||
用大O符号表示的时间复杂度 | |||||
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/300px-Point_quadtree.svg.png)
形态
编辑四元树可以用他们资料形态的表示法来作分类,资料形态的项目有:区域、点、直线及曲线。四元树也可以进行分类,不管树的形态是否独立于已处理过的排秩资料。一些四元树的形态如下所示:
四元树区块
编辑四元树区块表示为空间的分割,即在二维上分割区块为四组相同的象限、次象限等,且每个叶节点包含有关特殊次区块的资料。树里的每个节点不是正好有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)值来表示。
- 值;比如是"名字"。
边四元树
编辑边四元树是专门用来储存直线而不是点。曲线能分割每格到很接近精细的解析度。如此能产生极度的不平衡树,而此不平衡树可能推翻索引的使用目的。
一些四元树的常用法
编辑- 图像表示法
- 空间索引(Spatial index)。
- 在二维的有效率之碰撞侦测(collision detection)。
- 地形资料的隐藏面决定(Hidden surface determination)。
- 储存分散资料,诸如试算表(spreadsheet)、或著一些矩阵计算的格式化资讯。
- 多维场的解法。(计算流体力学, 电磁学)
- 生命游戏模拟程式。[1]
- 毒瘤资料结构
四元树为八叉树的二维类比。
区辨说明
编辑假如几何次分割不能减缩每个四元树的项目数时,(例如,在资料重叠时)则四元树的次分割失败,为了使演算法能够继续进行其容量必须突破限制。比如,一个四元树最大的容量为8,而且有9个点在(0, 0),次分割将会造成3个空的四元树,且每个空四元树会包含最初的9个点,再次分割依此类推。因为树必须允许在这样的象限内超过8点,如此四元树对带有任意几何(比如:地图或图形)的资料集才能够达到O(N)的时间复杂度。
注释
编辑- ^ Tomas G. Rokicki. An Algorithm for Compressing Space and Time. 2006-04-01 [2009-05-20]. (原始内容存档于2012-10-02).
参考资料
编辑- 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.
- 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.