K-D Tree

KDT 维护了一个 $k$ 维点集，是一颗特殊意义的 BST。具体地，对于每一层节点，有相同的划分维度 $d$ ，它的左子树的第 $d$ 维坐标都比它小，右子树的第 $d$ 维坐标都比它大。

可以维护多维键值检索。

操作

建树

对于当前点集、划分维度，先按划分维度对点集升序排序，然后取一个中值作为 KDT 上当前的结点。对于这个中值，它左边的点是它左子树集，右边是它右子树集。往下递归，划分维度依次交替。

插入

可以先像 BST 那样插入。然后发现可能退化成链，那就再像替罪羊树一样设一个平衡因子 $\alpha$ ，当一个子树的左右子树超过总大小 $\alpha$ 时，就将子树暴力重构。均摊 $\mathcal{O}(\log^2n)$ 。

找最近点

每个节点的点分割了自己的矩形范围成了两个子节点的矩形范围。

往子树找距离近的，如果都大于等于已有的答案，就不找了。单次一般 $\mathcal{O}(\log n)$ ，可达到 $\mathcal{O}(n^{\frac{k-1}{k}})$ 。

找 k 远点

开个长度为 $k$ 的小根堆，每次递归大的。最后堆顶就是第 $k$ 小。

例题

P4357