Skip to main content

KD树

第03部分红黑树

一、范围查找问题

给定直线L上的点集 $P={p_0, ..., p_{n-1}}$ ，对于任一区间 $R = [x1, x2]$ ，P中的哪些点落在其中？
这种问题的解决方案两种
蛮力算法：只需遍历点集P，并逐个地花费O(1)时间判断各点是否落在区间R内，缺点是数据集爆炸的时候，效率直接降低
正确方法：先进行预处理，比如我进行快速排序，消耗的时间是 $O(nlogn)$
之后我再查找的时候，定位最小的元素，只需要 $O(logn)$ 的时间，然后遍历找出 $r$ 个点，则总体的查询时间成本为 $O(r + logn)$ 。

二、二维范围查找问题

方法一：

如果点在二维的查询空间呢！我们再考虑容斥原理
根据容斥原理 $|R \cap P| = n(X1,Y1) + n(X2, Y2) - n(X1,Y2) - n(X2, Y1)$
$n(X1,Y1)$ 的含义是在平面的 $(x1,y1)$ 左下方的点的数量
利用这种方法，需要空间复杂度是 $O(n^2)$ ，但是查询很快，只需要 $O(logn)$
但是这种方法需要预处理，耗费的时间 $O(n^2)$
预处理的时候需要记下来 $n(x,y) = |(0,x] \times (0,y] \cap P|$

方法二：

如果点在二维的查询空间呢！我们再考虑构造平衡二叉树
设查询区间为[1, 23]。首先，在树中分别查找这一区间的左、右端点1和23，并分别终止于叶节点3和24。接下来，考查这两个叶节点共同祖先中的最低者，即所谓的最低共同祖先，也就是15
然后从祖先出发，分别重走一遍通往节点3和24的路径（分别记作path(3) 和path(24)）。在沿着path(3)/path(24)下行的过程中，忽略所有的右转/左转；而对于每一次左转/右转，都需要遍历对应的右子树/左子树（图中以阴影示意）
最终查找得到结果，消耗的时间复杂度是 $O(logn)$ ，用这种思路可以很快的拓展到更高纬度的数据

截屏2023-04-01 19.23.37

三、KD-Tree

1）概念

2d-树中的每个节点，都对应于二维平面上的某一矩形区域，且其边界都与坐标轴平行。当然，有些矩形的面积可能无限

截屏2023-04-01 19.27.09

2）构造实例

首先创建树根节点，并指派以整个平面以及全部7个输入点

截屏2023-04-01 19.28.01

3）查询实例

初始化递归查询的区域为v，也就是树的根节点
此时，视矩形区域v与查询区域R的相对位置，无非三种情况：
- 若矩形区域v完全包含于R内，则其中所有的输入点亦均落在R内，于是只需遍历一趟子树v，即可报告这部分输入点。
- 若二者相交，分别深入到v的左、右子树中，递归地查询
- 若二者彼此分离，不需要查了结束

4）复杂度

平面范围查询与一维情况不同，在同一深度上可能递归两次以上，并报告出多于两棵子树。但更精细的分析（习题[8-16]）表明，被报告的子树总共不超过 $O(\sqrt{n})$ 棵，累计耗时 $O(\sqrt{n})$
空间复杂度 $O(n)$ ，预处理的时间复杂度 $O(nlogn)$ ，查询的时间复杂度是 $O(\sqrt{n} + r)$ ，排除掉 $r$ 的部分，其余的查找时间决定与递归发生的次数，还有待查找区域边界和子区域的相交的数目 $Q(n)$
递推关系 $Q(1) = O(1)$ ， $Q(n) =2 + 2Q(n/4)$
如下图所示，深色的区域代表查找区域，浅色的就是数据范围区域
每次递归到节点 $t$ 的时候，儿子节点两个(大约n/2个数据点在里面)，孙子节点四个(大约n/4个数据点在里面)
我们可以发现，最多还需要递归两个孙子节点，那就是下图的左上方的区域、右下方的区域。至于左下方的区域不需要递归了！因为左下方区域的所有点都在查找范围里面！右上角没有数据在目标里面，也不需要递归！

截屏2023-04-01 19.52.42

四、高维度推广

kd树本质是高维度K的情况，我们二维的时候考虑的是2d树
假设有d维的情况下，空间复杂度是 $O(n)$ ，预处理 $O(nlogn)$ ，查询 $O(n^{1-1/d} + r)$
仿照上面证明，假如是三维的时候，儿子节点两个(大约n/2个数据点在里面)，孙子节点四个(大约n/4个数据点在里面)第三代节点8个(大约n/8个数据点在里面)
$Q(n) =4 + 4Q(n/8)$

第03部分红黑树