数据结构中的点四叉树

点四叉树是二叉树的一种变体，用于表示二维点数据。所有四叉树的特征都为点四叉树所共享。

它在比较二维有序数据点方面通常非常高效，通常在 O(log n) 时间内执行。出于完整性考虑，点四叉树值得一提，但 k-d 树作为广义二分搜索的工具胜过它们。

点四叉树的构建方式如下。

给定要插入的下一个点，我们计算它所在的单元格并将其添加到树中。

新点被添加，使得包含它的单元格被穿过该点的垂直线和水平线分成四个象限。因此，单元格是矩形的，但不一定是正方形的。

在这些树中，每个节点都包含一个输入点。

由于平面的划分是由点插入的顺序决定的，因此树的高度对插入顺序敏感并依赖于插入顺序。以不正确的顺序插入会导致树的高度与输入点的数量呈线性关系（此时它变成了链表）。

如果点集是静态的，则可以执行预处理以构建高度平衡的树。

点四叉树的节点结构

点四叉树的节点与二叉树的节点相同，主要区别在于它与四个指针相关联（每个指针用于每个象限），而不是像普通二叉树那样只有两个（“左”和“右”）。此外，键通常被分成两部分，分别指代 x 和 y 坐标。

因此，一个节点包含以下信息

  • 四个指针：分别是 quad[‘NW’]、quad[‘NE’]、quad[‘SW’] 和 quad[‘SE’]
  • NW-西北，NE-东北，SW-西南，SE-东南
  • 点；依次包含
  • 键；通常表示为 x、y 坐标
  • 值；例如名称

更新于: 2020年1月8日

1K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告