四叉树
四元树（英语：Quadtree）是一种树状资料结构，在每一个节点上会有四个子区块。四元树常应用于二维空间资料的分析与分类。 它将资料区分成为四个象限。资料范围可以是方形或矩形或其他任意形状。这种资料结构是由 拉斐尔·芬克尔与乔恩·本特利在1974年发展出来。类似的资料分割方法也称为 Q-tree。所有的四元树法有共同之特点:
- 可分解成为各自的区块
- 每个区块都有节点容量。当节点达到最大容量时，节点分裂
- 树状资料结构依造四元树法加以区分
| 四叉树 | |||||
|---|---|---|---|---|---|
| 类型 | 树 | ||||
| 发明时间 | 1974年 | ||||
| 发明者 | 拉斐尔·芬克尔、乔恩·本特利 | ||||
| 用大O符号表示的时间复杂度 | |||||
| |||||
形态
四元树可以用他们资料形态的表示法来作分类，资料形态的项目有：区域、点、直线及曲线。四元树也可以进行分类，不管树的形态是否独立于已处理过的排秩资料。一些四元树的形态如下所示：
四元树区块
四元树区块表示为空间的分割，即在二维上分割区块为四组相同的象限、次象限等，且每个叶节点包含有关特殊次区块的资料。树里的每个节点不是正好有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.