[科普中国]-四叉树

概述

四叉树（quad-tree）是一种数据结构，是一种每个节点最多有四个子树的数据结构。

四叉树是在二维图片中定位像素的唯一适合的算法。因为二维空间（图经常被描述的方式）中，平面像素可以重复的被分为四部分，树的深度由图片、计算机内存和图形的复杂度决定。

四叉树可以用来在数据库中放置和定位文件（称作记录或键）。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。

特点可分解成为各自的区块

每个区块都有节点容量。当节点达到最大容量时，节点分裂

树状数据结构依造四元树法加以区分

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

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

在一个深度为n的四元树区块中可以用来表示一个视频包含有2× 2的像素，每个像素的值为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)值来表示。

值；比如是"名字"。

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

种类1.点四叉树（Point Quadtree）

点四叉树与KD树相似，两者的差别是在点四叉树中，空间被分割成四个矩形。四个不同的多边形分别是：SW、NW、SE、NE。其搜索过程和KD树相似，当一个点包含在搜索范围内时被记录下来，当一个子树和搜索范围有交叠时它将被穿过。

2.PR四叉树(Point Region Quadtree)

PR四叉树是点四叉树的一个变种，它不使用数据集中的点来分割空间。在PR四叉树中，每次分割空间时，都是将一个正方形分成四个相等的子正方形，依次进行，直到每个正方形的内容不超过所给定的桶量（比如一个对象）为止。

3.MX四叉树

空间被分割成四个矩形。四个不同的多边形分别是：SW、NW、SE、NE。每次分割空间时，都是将一个正方形分成四个相等的子正方形，依次进行，直到每个正方形的内容不超过所给定的桶量（比如一个对象）为止。

所有的数据都处在四叉树的同一个深度，多个点可以由一个指针联接。

4.基于固定网格划分的四叉树索引

在四叉树中，空间要素标识记录在其外包络矩形所覆盖的每一个叶结点中，但是，当同一父亲的四个兄弟结点都要记录该空间要素标识时，则只将该空间要素标识记录在该父亲结点上，并按这一规则向上层推进。

5.线性可排序四叉树索引

首先将四叉树分解为二叉树，即在父结点层与子结点层之间插入一层虚结点，虚结点不用来记录空间要素，然后按照中序遍历树的顺序对结点进行编码，包括加入的虚结点2。

应用图像表示法

空间索引(Spatial index)。

在二维的有效率之碰撞侦测(collision detection)。

地形数据的隐藏面决定(Hidden surface determination)。

存储分散数据，诸如电子表格(spreadsheet)、或著一些矩阵计算的格式化信息。

多维场的解法。(计算流体力学,电磁学)

生命游戏模拟程序3。