kd树（kd tree） -ag凯发k8国际

维基百科介绍：http://en.wikipedia.org/wiki/kdtree

　　kd树是一种能在 o(n)时间内把平面划分成若干个区域，然后在均摊 o(logn)的时间内找到某个区域内所有点的数据结构。

其思想是，每次把当前处理的区域按照点数分成两部分，然后对两部分进行递归处理。。。

分成两部分有两种策略:

　　一种是横着竖着横着竖着交替划分。。

　　一种是把坐标跨度大的那一维划分成两部分。

似乎没什么影响。

上图是一种可行的划分方式。每次找到当前处理点集中的中点，以这个中点为分界线把区间划分成两部分和。注意中点是作为分界线不参与下一轮处理。

查询一个点的最近点时，首先令最近距离为，然后在kd树中查找，首先和当前区间的中点求一次距离更新答案，然后再根据该点和中点的关系决定是去左区间还是右区间，如果正好在分界线上那么两边都过去吧。

这里还有个问题，可能点被分到了左区间，但是可能和右区间的某个点比较近。那么怎么办。？

假设这个点到分界线的距离已经是大于等于当前最优答案了，那么另一个区间的所有点到这个点的距离都比当前最优答案远，只有这时候不需要考虑另一个区间。

复杂度分析均摊下来的确是 o(n)，详情可以参观一下《计算几何：算法与应用》那本书。

stl中提供了一个叫做nth_element的函数，可以在o(n)的复杂度下找到序列的第k大数并且把序列以第k大为界分为两半，用这个就能写出很短的建树过程了。

bool div[maxn];\\记录这个区间是用什么体位划分的
void buildkd(int l, int r, point p[])\\记得备份一下p
{ 
       if (l > r) return; 
       int mid = l   r >> 1; 
       int minx, miny, maxx, maxy; 
       minx = min_element(p   l, p   r   1, cmpx)->x; 
       miny = min_element(p   l, p   r   1, cmpy)->y; 
       maxx = max_element(p   l, p   r   1, cmpx)->x; 
       maxy = max_element(p   l, p   r   1, cmpy)->y; 
       div[mid] = (maxx - minx >= maxy - miny); 
       nth_element(p   l, p   mid, p   r   1, div[mid] ? cmpx : cmpy);
       buildkd(l, mid - 1, p); 
       buildkd(mid   1, r, p);
}
查找的时候照着思路写就可以了。
void find(int l, int r, point a, point p[])
{ 
  　　if (l > r) return; 
 　　 int mid = l   r >> 1; 
　　  long long dist = dist2(a, p[mid]); 
　　  if (dist > 0)//如果有重点不能这样判断 
        res = min(res, dist); 
 　　 long long d = div[mid] ? (a.x - p[mid].x) : (a.y - p[mid].y); 
 　　 int l1, l2, r1, r2; l1 = l, l2 = mid   1; r1 = mid - 1, r2 = r; 
 　　 if (d > 0)     swap(l1, l2), swap(r1, r2); 
  　　find(l1, r1, a, p); 
  　　if (d * d < res)      find(l2, r2, a, p);
}

这份kd树是参照佐倉杏子的代码学习的。orz。
相关题目：incaseoffailure

#include
#include
using namespace std;
const int n = 100000;
 
struct point{
　　int x,y;
}p[n 10],tmp[n 10];
int div[n 10];
long long ret;
 
int cmpx(const point &a,const point &b){
　　return a.x < b.x;
}
int cmpy(const point &a,const point &b){
　　return a.y < b.y;
}
 
void build(int l,int r,point q[]){
　　if(l > r) return;
　　int m = (l r)>>1;
　　int minx = min_element(q l,q r 1,cmpx)->x;
　　int miny = min_element(q l,q r 1,cmpy)->y;
　　int maxx = max_element(q l,q r 1,cmpx)->x;
　　int maxy = max_element(q l,q r 1,cmpy)->y;
　　div[m] = (maxx-minx) >= (maxy-miny);
　　nth_element(q l,q m,q r 1,(div[m]?cmpx:cmpy));
　　build(l,m-1,q);
　　build(m 1,r,q);
}
long long dis(point a,point b){
　　return 1ll*abs(a.x-b.x)*abs(a.x-b.x) 1ll*abs(a.y-b.y)*abs(a.y-b.y);
}
void find(int l,int r,point q){
　　if(l > r) return;
　　int m = (l r)>>1;
　　long long dist = dis(q,tmp[m]);
　　if( dist > 0 ) ret = min(ret,dist);
　　
　　int d = div[m] ? (q.x-tmp[m].x) : (q.y-tmp[m].y);
　　int l1,l2,r1,r2;
　　l1 = l, r1 = m-1;
　　l2 = m 1,r2 = r;
　　if(d > 0) swap(l1,l2),swap(r1,r2);
　　find(l1,r1,q);
　　if( 1ll*d*d < ret ) 
　　find(l2,r2,q);
}
int main(){
　　int t,n; scanf("%d",&t);
　　while(t-- && scanf("%d",&n)){
　　　　for(int i = 0; i < n; i  )
　　　　　　scanf("%d%d",&p[i].x,&p[i].y);
　　　　memcpy(tmp,p, sizeof(p));
　　　　build(0,n-1,tmp);
　　　　for(int i = 0; i < n; i  ){
　　　　　　ret = (1ll<<60);
　　　　　　find(0,n-1,p[i]);
　　　　　　printf("%i64d\n",ret);
　　　　}
　　}
　　
　　return 0;
 
}

总结

以上是ag凯发k8国际为你收集整理的kd树（kd tree）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。