k-D Tree(KDT , k-Dimension Tree) 是一种可以 高效处理 $k$ 维空间信息 的数据结构。
基本思想
K-D树具有二叉搜索树的形态。因此可看做是替罪羊树扩展到 $k$ 维后的形态。
与一维的信息不同，K-D树的第 $i$ 层需要用第 $i%k$ 维的信息进行比较。为了保证复杂度，建树时选取第 $i%k$ 维中 $[l,r]$ 的中位数作为当前的根。修改的时候通过暴力重构保证树的深度在可以接受的范围内。
下面详细阐述几个操作。
基本操作
重构树
如果当前节点的左或右子树的大小比上当前子树的大小已经超过了某个阙值（可设为 $0.75$），那么我们需要重构树。
首先我们 DFS 一遍整棵子树，把所有的节点信息存入一个数组。然后进行重构。每次利用 nth_element 函数找到当前维信息的中位数并将其作为根，小于当前信息的放入左子树，否则放入右子树。递归下去即可。
代码如下（两个函数）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void clear(int id){
nd[++cqt]=tr[id].p;
lint[++cnt]=id;
if(lid)clear(lid);
if(rid)clear(rid);
}
int rebuild(int id,int l,int r,int d){
if(l>r)return 0;
int mid=(l+r)>>1;id=newnode();
nth_element(nd+l,nd+mid,nd+r+1,d?cmp1:cmp0);
tr[id].p=nd[mid];
lid=rebuild(lid,l,mid-1,d^1);
rid=rebuild(rid,mid+1,r,d^1);
push_up(id);
return id;
}
|
插入节点
插入的方式与普通二叉搜索树相同，只不过每层比较的信息不同。插入完成后需要判断是否需要重构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int push_down(int id,int d){
if(tr[lid].sz>tr[id].sz*rate||tr[rid].sz>tr[id].sz*rate){
cqt=0;
clear(id);
id=rebuild(id,1,tr[id].sz,d);
}
return id;
}
int insert(int id,int d,node u){
if(!id){
id=newnode();
lid=rid=0,tr[id].p=u;
push_up(id);
return id;
}
if(u.loc[d]<=tr[id].p.loc[d])lid=insert(lid,d^1,u);
else rid=insert(rid,d^1,u);
push_up(id);
id=push_down(id,d);
return id;
}
|
查询操作
不同的 K-D 树需要在树上存储不同的信息。这里只是提供一种思想。
我们可以在树上存子树内各维的范围，如果查询的东西完全包含该子树（在所有维度上），则返回该当前子树的答案。否则递归处理。注意需要判断每次的根节点是否要纳入答案中。个人感觉这挺像线段树的。
放一个 2-D 树内存储矩阵信息的代码：
1
2
3
4
5
6
7
8
| int query(int id,int x1,int y1,int x2,int y2){
if(!id)return 0;
if(in(tr[id].minm[0],tr[id].minm[1],tr[id].maxm[0],tr[id].maxm[1],x1,y1,x2,y2))return tr[id].sum;
if(out(tr[id].minm[0],tr[id].minm[1],tr[id].maxm[0],tr[id].maxm[1],x1,y1,x2,y2))return 0;
int ret=query(lid,x1,y1,x2,y2)+query(rid,x1,y1,x2,y2);
if(in(tr[id].p.loc[0],tr[id].p.loc[1],tr[id].p.loc[0],tr[id].p.loc[1],x1,y1,x2,y2))ret+=tr[id].p.val;
return ret;
}
|
时空复杂度
空间复杂度显然是 $O(n)$ 的，不过需要注意利用好已经被删除的点！可以拿一个数组存下被删除的点，每次加新节点的时候从数组里面拿就行了。
时间复杂度较为复杂。
- 对于建树、插入、删除操作，单次操作复杂度为均摊 $O(\log n)$，因为树高是这么高的。
- 对于查询操作，最坏情况是 $O(n^{1-\frac{1}{k}})$ 的。特别地，2-D 树的最坏复杂度是 $O(\sqrt n)$。
总结
在处理高维问题上，K-D 树不失为一种强有力的工具；但由于其复杂度的局限性，在处理二维问题时，K-D树往往只是在想不出正解的时候的一种巧妙的暴力。综上，掌握好 K-D 树对我们来说是十分必要的。