更新时间：2022-08-25 12:56
四元树又称四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。
四叉树（quad-tree）是一种数据结构，是一种每个节点最多有四个子树的数据结构。
四叉树是在二维图片中定位像素的唯一适合的算法。因为二维空间（图经常被描述的方式）中，平面像素可以重复的被分为四部分，树的深度由图片、计算机内存和图形的复杂度决定。
四叉树可以用来在数据库中放置和定位文件（称作记录或键）。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。
四元树可以用他们数据形态的表示法来作分类，数据形态的项目有：区域、点、直线及曲线。四元树也可以进行分类，不管树的形态是否独立于已处理过的排秩数据。一些四元树的形态如下所示：
四元树区块表示为空间的分区，即在二维上分区块为四组相同的象限、次象限等，且每个叶节点包含有关特殊次区块的数据。树里的每个节点不是正好有4个子节点，就是没有子节点(为一个树叶节点)。四元树区块不是严格的一颗'树' - 且位置的次分区与数据无关。他们是比较精确一些称为'单词查找树'.
在一个深度为n的四元树区块中可以用来表示一个视频包含有2× 2的像素，每个像素的值为0或1。根节点表示全部视频区块。假如像素在任何区块不是全部为0或1，那就可以进行画分。在这个应用中，每个叶节点代表一个段落的像素、段落像素里面包含全部为零或全部为一的组合。
四元树区块也可以用为一种数据区块上不同变化解析的表达法。比如，温度在一个区块中可以存储为一个四元树，而树叶节点存储著平均温度涵盖到它所拥有的次区块。
假如四元树区块被用来表达一组点数据(诸如一组城市的经纬度)，区块就进行次分区直到每个叶节点包含最多一个单点。
点四元树修改自二叉树用来表示二维的点数据。点四元树与四元树都有共同的特点，不过于次分区的中心总是在一点时、点四元树视为一真树(true tree)。树的形态根据编过序的数据而定。在比较二维规律数据点上是相当有效率的，经常运作在O(log n)的时间复杂度内。
点四元树的节点类似于二叉树的节点，它们之间的主要差别在于点四元树有4个指针(每一个象限一个指针)、而一般二叉树只有2个指针(左指针及右指针)。点四元树的键值也是经常被分解为两部分，如在直角坐标上的 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.线性可排序四叉树索引
首先将四叉树分解为二叉树，即在父结点层与子结点层之间插入一层虚结点，虚结点不用来记录空间要素，然后按照中序遍历树的顺序对结点进行编码，包括加入的虚结点。