数据结构中的点四叉树
点四叉树是为表示二维点数据而实现的二叉树的改编。所有四叉树的特征由点四叉树共享。
在比较通常在O（logn）时间执行的二维有序数据点时，它通常非常有效。点四叉树的完整性值得一提，但kd树已超越它们成为广义二分搜索的工具。
点四叉树的构建如下。
给定下一个要插入的点，我们计算它所在的单元格并将其添加到树中。
添加新点，以便包含该点的单元格通过穿过该点的垂直线和水平线划分为四个象限。因此，单元是矩形的，但不一定是正方形。
在这些树中，每个节点都由一个输入点组成。
由于平面的划分是由点插入的顺序确定的，所以树的高度对插入顺序敏感并取决于插入顺序。以错误的顺序插入会导致一棵树的高度与输入点数成线性关系（在此点上，它成为一个链表）。
如果点集是静态的，则可以执行预处理以构建平衡高度的树。
点四叉树的节点结构
点四叉树的节点与二叉树的节点相同，主要区别在于它与四个指针（每个指针用于每个象限）相关联，而不是两个（“左”和“右”）在普通的二叉树中。同样，键通常分为两部分，分别指x和y坐标。
因此，一个节点包含以下信息
四个指针：它们是quad['NW']，quad['NE']，quad['SW']和quad['SE']
西北西北，东北东北，西南西南，东南东南
点;依次由
键;通常表示为x，y坐标
值;如一个名字