K-D Tree

$K-D$ $Tree$是一种分割$k$维数据空间的数据结构,主要应用于多维空间关键数据的搜索

基本用法


节点

$K-D$ $Tree$中的一个节点储存了一个$K$维空间域和一个$K$维的点坐标

1
d:点各维坐标 mi:空间各维坐标的min mx:空间各维坐标的max c:左右儿子

以下以$2-D$ $Tree$为例

构树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)

struct abc{
int ww[2];
int& operator[](int x){return ww[x];}
}a[N];

bool operator <(abc x,abc y){return x[D]<y[D];}

void update(int x){
for(int i=0;i<2;i++){
if(c[x][0]) cmin(mi[x][i],mi[c[x][0]][i]),cmax(mx[x][i],mx[c[x][0]][i]);
if(c[x][1]) cmin(mi[x][i],mi[c[x][1]][i]),cmax(mx[x][i],mx[c[x][1]][i]);
}
}

int build(int l,int r,int x)//循环选取维度
{
D=x;int m=l+r>>1;
nth_element(a+l,a+m,a+r+1);//使用某一维坐标的中位数作为切分点
for(int i=0;i<2;i++) d[m][i]=mi[m][i]=mx[m][i]=a[m][i];
if(l<m) c[m][0]=build(l,m-1,x^1);
if(r>m) c[m][1]=build(m+1,r,x^1);
update(m);return m;
}

估价

算出目标点到当前查询区域距离的下界或上界

1
2
3
4
5
6
7
8
9
10
11
//now:需估价的矩形区域 P:目标点
//曼哈顿最小
for(int i=0;i<2;i++){
ret+=max(mi[now][i]-P[i],0);
ret+=max(P[i]-mx[now][i],0);
}
//曼哈顿最大

//欧几里得最小

//欧几里得最大

插入

1
2
3
4
5
6
void insert(int &now,int x){//同平衡树
if(!now){now=++n;for(int i=0;i<2;i++) d[now][i]=mi[now][i]=mx[now][i]=P[i];return ;}
int tmp=P[x]>=d[now][x];
insert(c[now][tmp],x^1);
update(now);
}

查询

1
2
3
4
5
6
7
8
9
10
int Dis(int now){return abs(d[now][0]-P[0])+abs(d[now][1]-P[1]);}

void query(int x)
{
int tmp=Dis(x),dl[2];
for(int i=0;i<2;i++) dl[i]=c[x][i]?getdis(c[x][i]):INF;//估价函数,走较优的子树
cmin(ans,tmp);tmp=dl[0]>=dl[1];
if(dl[tmp]<ans) query(c[x][tmp]),tmp^=1;//不能更新答案直接跳过
if(dl[tmp]<ans) query(c[x][tmp]);
}
分享到: