K-D Tree 学习笔记

Dementor · 2022-01-26 10:25:49 · 题解

K-D Tree

K-D Tree 是一种具备 BST 形态的维护 k 维空间上点的信息的一种数据结构

其名称 “K-D” 也是取 k 维空间这个意义

在节点数 n >> 2^k 时， K-D Tree 的运行效率优秀

单次操作，最坏时间复杂度是 O(n^{1-\frac{1}{k}}) 的

思维清晰、代码清新的 K-D Tree 在这样的自身情况下不失为一个良好的解决问题的工具，有的题目甚至需要依赖 K-D Tree 才能解决，而有的题目则可以利用其取得一定部分分

建树

K-D Tree 维护的节点的位置、权值信息在绝大多数情况下都由题目给出，所以在下面的实现中，我们节点的编号和读入顺序一致，需要额外将读入的数据存储下来

下面所说 “编号” 统一先行指明是读入顺序编号

K-D Tree 的空间复杂度是 O(n) 的

int build (int l, int r)

我们在这个函数里，需要实现：

• 构建一颗由编号 l..r 节点 K-D Tree

• 构建好节点之间的父子关系

声明：

• “当前节点”指 build 函数的返回值

核心思想：根据某一维度进行划分

我们考虑 d 表示当前节点 按照 d 这一维度进行划分 ，具体地， d 这一维度上，小于等于当前节点的节点作为其左子树，大于当前节点的节点作为其右子树，再分别递归左右两边进行构建

方差优化

可以看出，以上构建方法保证了 K-D Tree 具有 BST 的性质，但是并没有保证时间复杂度

我们接下来提出两个优化方案，以保证 K-D Tree 具有正确的复杂度

首先是 方差优化

我们计算当前 l..r 的节点分别在 k 个维度上坐标的方差，取方差最大的一维作为当前节点的 d

中位数优化

取得 d 后，我们不任意取当前节点，而是将 d 维上坐标的中位数节点作为当前节点

由以上两个优化，我们就可以保证 K-D Tree 的高度最高是 O(n^{1-\frac{1}{k}}) 的，由此做到单次操作复杂度正确

建树部分到此实现

插入

void ins (int & x, int v)

插入编号为 v 的节点，当前在 K-D Tree 的 x 号节点

我们查看 d[x] ，按照 d[x] 这一维比较，如果小于等于 t[x][d[x]] 就递归左子树，否则递归右子树