计算机科学

首页 > 计算机科学

四叉树

2018-08-27 10:40:18     所属分类:树结构
四元树区块的点数据分布图

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

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

目录

  • 1 形态
    • 1.1 四元树区块
    • 1.2 点四元树
      • 1.2.1 点四元树的节点结构
    • 1.3 边四元树
  • 2 一些四元树的常用法
  • 3 区辨说明
  • 4 注释
  • 5 参考资料
  • 6 参看
  • 7 外部链接

形态

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

四元树区块

四元树区块表示为空间的分区,即在二维上分区块为四组相同的象限、次象限等,且每个叶节点包含有关特殊次区块的数据。树里的每个节点不是正好有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)值来表示。
    • 值;比如是"名字"。

边四元树

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

一些四元树的常用法

  • 图像表示法
    Bitmap and its compressed quadtree representation
  • 空间索引(Spatial index)。
  • 在二维的有效率之碰撞侦测(collision detection)。
  • 地形数据的隐藏面决定(Hidden surface determination)。
  • 存储分散数据,诸如电子表格(spreadsheet)、或著一些矩阵计算的格式化信息。
  • 多维场的解法。(计算流体力学, 电磁学)
  • 生命游戏模拟程序。[1]

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

区辨说明

假如几何次分区不能减缩每个四元树的项目数时,(例如,在数据重叠时)则四元树的次分区失败,为了使算法能够继续进行其容量必须突破限制。比如,一个四元树最大的容量为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]. 

参考资料

  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.

参看

  • 八叉树
  • 二叉空间分区(Binary space partitioning)
  • k-d树(Kd-tree)
  • R树(R-tree)
  • UB树(UB-tree)
  • 空间索引(Spatial index)
  • 空间数据库(Spatial database)

外部链接

  • A discussion of the Quadtree and an application (英文)
  • Considerable discussion and demonstrations of Spatial Indexing (英文)
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339724.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:顺序统计树
下一篇:大纲
相关推荐