KD 树

KD 树

交替地按 x、y 坐标划分平面，直到叶子节点只有一个点。 每个节点对应一个平面矩形区域。

构造

找到中位数点（对应维度下），左右子树分别递归处理两侧节点

查询

递归地进行查询：

• 若为叶子节点，判断节点中的点是否在查询区域内并输出
• 若子节点代表区域包含于查询区域，则输出子树
• 若子节点代表区域与查询区域交不为空，则继续递归查询
• 若子节点代表区域与查询区域交为空，则返回

性质

• 树高为 $O(\log n)$
• 同层的节点对应的区间交为空，并为整个平面

性能

预处理 （构造）

$T(n)=2\cdot T(n/2)+O(n)=O(n\log n)$ 每层耗时来自找到中间值的 $O(n)$ 耗时 树高为 $O(\log n)$，因此空间复杂度为 $O(n)$

查询

查询的时间成本取决于递归调用的次数 $Q(n)$，观察发现当且仅当一个子区域的边界与查询区域边界相交时，会触发向下的递归。 $Q(n)$ 渐近等于一条查询区域的边触发的递归调用次数。 可以发现，祖孙节点间存在递推关系，如果一个子区域与查询边相交，则在其四个孙子中，至多会有两个区域与该边相交。 $Q(n)=2\cdot Q(n/4)+O(1)=O(\sqrt{n})$ 最坏情况构造：点均匀分布，查询形状为长条形，只有一个维度上可以剪枝。则每经过两层，需要访问的节点数会翻倍，总共会访问 $2^{\log n/2}=\sqrt{n}$ 个节点

更高维度

依次按第 1 至第 k 维进行划分，

• 在 $O(n\log n)$ 构造出
• 空间复杂度 $O(n)$
• 查询时间 $O(r+n^{1-1/d})$