【算法笔记】KD_Tree

  • 本文为博主原创，未经许可不得转载

算法原理

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

$KD-Tree$的构建：第$i$层以数据的第$i%n$项为键值划分，满足平衡二叉树的性质，即左子树键值小于根，根小于右子树，以此递归建树

这里说一下$nth$_$element()$函数的用法，这个函数可以实现局部排序

如$nth$_$element(tr+l,tr+mid,tr+r+1,cmp)$可以实现把区间$[l,r]$排序，并把$mid$的位置置为第$mid$大的元素

为什么不用$sort$？据柳神所说，$sort$太慢了。。。。。。

查找时采用的是$A-Star$搜索的思想，调整搜索顺序以优化时间复杂度

时间复杂度$O(\sqrt n)$

　　

　　

例题一

放板子

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
#define FILE "read"
#define INF 1e9
#define MAXN 500010
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
struct node{int d[2],son[2],mx[2],mn[2];}tr[MAXN];
int n,Key,root,ans,maxx,minn,D[2],a[MAXN][2];
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
bool cmp(node a,node b){return a.d[Key]<b.d[Key];}
void updata(int p){
    for(int i=0;i<=1;++i){
        if(tr[p].son[0]){
            cmax(tr[p].mx[i],tr[tr[p].son[0]].mx[i]);
            cmin(tr[p].mn[i],tr[tr[p].son[0]].mn[i]);
        }
        if(tr[p].son[1]){
            cmax(tr[p].mx[i],tr[tr[p].son[1]].mx[i]);
            cmin(tr[p].mn[i],tr[tr[p].son[1]].mn[i]);
        }
    }
}
void build(int &p,int l,int r,int k){
    int mid=(l+r)>>1; p=mid; Key=k;
    nth_element(tr+l,tr+mid,tr+r+1,cmp);
    for(int i=0;i<=1;++i) tr[p].mx[i]=tr[p].mn[i]=tr[p].d[i];
    if(l<=mid-1)  build(tr[p].son[0],l,mid-1,k^1);
    if(mid+1<=r)  build(tr[p].son[1],mid+1,r,k^1);
    updata(p);  
}
int getmax(int p){
    int ret=0;
    for(int i=0;i<=1;++i) ret+=max(abs(tr[p].mx[i]-D[i]),abs(tr[p].mn[i]-D[i]));
    return ret;
}
int getmin(int p){
    int ret=0;
    for(int i=0;i<=1;++i) ret+=max(D[i]-tr[p].mx[i],0)+max(tr[p].mn[i]-D[i],0);
    return ret;
}
void query_max(int p){
    cmax(maxx,abs(tr[p].d[0]-D[0])+abs(tr[p].d[1]-D[1]));
    int dl=-INF,dr=-INF;
    if(tr[p].son[0])  dl=getmax(tr[p].son[0]);
    if(tr[p].son[1])  dr=getmax(tr[p].son[1]);
    if(dl>dr){
        if(dl>maxx)  query_max(tr[p].son[0]);
        if(dr>maxx)  query_max(tr[p].son[1]);
    }
    else{
        if(dr>maxx)  query_max(tr[p].son[1]);
        if(dl>maxx)  query_max(tr[p].son[0]);
    }
}
void query_min(int p){
    if(abs(tr[p].d[0]-D[0])+abs(tr[p].d[1]-D[1])) cmin(minn,abs(tr[p].d[0]-D[0])+abs(tr[p].d[1]-D[1]));
    int dl=INF,dr=INF;
    if(tr[p].son[0])  dl=getmin(tr[p].son[0]);
    if(tr[p].son[1])  dr=getmin(tr[p].son[1]);
    if(dl<dr){
        if(dl<minn)  query_min(tr[p].son[0]);
        if(dr<minn)  query_min(tr[p].son[1]);
    }
    else{
        if(dr<minn)  query_min(tr[p].son[1]);
        if(dl<minn)  query_min(tr[p].son[0]);
    }
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    int n=read(); ans=INF;
    for(int i=1;i<=n;++i){
        a[i][0]=read(); a[i][1]=read();
        tr[i].d[0]=a[i][0]; tr[i].d[1]=a[i][1];
    }
    build(root,1,n,0);
    for(int i=1;i<=n;++i){
        D[0]=a[i][0];  D[1]=a[i][1];
        maxx=-INF;  minn=INF;
        query_max(root);
        query_min(root);
        cmin(ans,maxx-minn);
    }
    printf("%d\n",ans);
    return 0;
}

　　

　　

　　

例题二

多了一个插入操作

还记得$Treap$的插入是怎么实现的吗？

$KD-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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
#define FILE "read"
#define INF 1e9
#define MAXN 1000010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
struct node{int d[2],son[2],mx[2],mn[2];}tr[MAXN];
int n,m,minn,cnt,Key,root,D[2];
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
bool cmp(node a,node b){return a.d[Key]<b.d[Key];}
void updata(int p){
    for(int i=0;i<=1;++i){
        if(tr[p].son[0]){
            cmax(tr[p].mx[i],tr[tr[p].son[0]].mx[i]);
            cmin(tr[p].mn[i],tr[tr[p].son[0]].mn[i]);
        }
        if(tr[p].son[1]){
            cmax(tr[p].mx[i],tr[tr[p].son[1]].mx[i]);
            cmin(tr[p].mn[i],tr[tr[p].son[1]].mn[i]);
        }
    }
}
void build(int &p,int l,int r,int k){
    int mid=(l+r)>>1; p=mid; Key=k;
    nth_element(tr+l,tr+mid,tr+r+1,cmp);
    for(int i=0;i<=1;++i) tr[p].mx[i]=tr[p].mn[i]=tr[p].d[i];
    if(l<=mid-1)  build(tr[p].son[0],l,mid-1,k^1);
    if(mid+1<=r)  build(tr[p].son[1],mid+1,r,k^1);
    updata(p);
}
void insert(int &p,int k){
    if(!p){p=++cnt; for(int i=0;i<=1;++i) tr[p].d[i]=tr[p].mx[i]=tr[p].mn[i]=D[i];return;}
    if(D[k]<tr[p].d[k])  insert(tr[p].son[0],k^1);
    else insert(tr[p].son[1],k^1);
    updata(p);
}
int getmin(int p){
    int ret=0;
    for(int i=0;i<=1;++i) ret+=max(tr[p].mn[i]-D[i],0)+max(D[i]-tr[p].mx[i],0);
    return ret;
}
void query_min(int p){
    cmin(minn,abs(tr[p].d[0]-D[0])+abs(tr[p].d[1]-D[1]));
    int dl=INF,dr=INF;
    if(tr[p].son[0])  dl=getmin(tr[p].son[0]);
    if(tr[p].son[1])  dr=getmin(tr[p].son[1]);
    if(dl<dr){
        if(dl<minn)  query_min(tr[p].son[0]);
        if(dr<minn)  query_min(tr[p].son[1]);
    }
    else{
        if(dr<minn)  query_min(tr[p].son[1]);
        if(dl<minn)  query_min(tr[p].son[0]);
    }
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    n=read();  m=read();
    for(int i=1;i<=n;++i) tr[i].d[0]=read(),tr[i].d[1]=read();
    build(root,1,n,0);  cnt=n;
    for(int i=1;i<=m;++i){
        int opt=read(); D[0]=read(); D[1]=read();
        if(opt==1) insert(root,0);
        else{
            minn=INF;
            query_min(root);
            printf("%d\n",minn);
        }
    }
    return 0;
}

　　

　　

　　

例题三

我们用堆来维护第$K$大，具体方法：

先往堆中装入$K$个$0$，然后如果元素大于堆顶，则用该元素代替堆顶，操作完后堆顶元素即为第$K$大元素

至于这么做为什么是对的，留给读者推敲

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
typedef long long ll;
struct node{ll d[2],mx[2],mn[2],son[2];}tr[MAXN];
ll n,K,root,Key,D[2],a[MAXN][2];
priority_queue<ll,vector<ll>,greater<ll> >q;
inline ll read(){
    ll x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
bool cmp(node a,node b){return a.d[Key]<b.d[Key];}
ll sqr(ll x){return x*x;}
void updata(ll p){
    for(ll i=0;i<=1;++i){
        if(tr[p].son[0]){
            cmax(tr[p].mx[i],tr[tr[p].son[0]].mx[i]);
            cmin(tr[p].mn[i],tr[tr[p].son[0]].mn[i]);
        }
        if(tr[p].son[1]){
            cmax(tr[p].mx[i],tr[tr[p].son[1]].mx[i]);
            cmin(tr[p].mn[i],tr[tr[p].son[1]].mn[i]);
        }
    }
}
void build(ll &p,ll l,ll r,ll k){
    ll mid=(l+r)>>1; p=mid; Key=k;
    nth_element(tr+l,tr+mid,tr+r+1,cmp);
    for(ll i=0;i<=1;++i)  tr[p].mx[i]=tr[p].mn[i]=tr[p].d[i];
    if(l<=mid-1)  build(tr[p].son[0],l,mid-1,k^1);
    if(mid+1<=r)  build(tr[p].son[1],mid+1,r,k^1);
    updata(p);
}
ll getmax(ll p){
    ll ret=0;
    for(ll i=0;i<=1;++i) ret+=max(sqr(D[i]-tr[p].mx[i]),sqr(D[i]-tr[p].mn[i]));
    return ret;
}
void query_max(ll p){
    ll dis=sqr(D[0]-tr[p].d[0])+sqr(D[1]-tr[p].d[1]);
    if(dis>q.top())  q.pop(),q.push(dis);
    ll dl=0,dr=0;
    if(tr[p].son[0])  dl=getmax(tr[p].son[0]);
    if(tr[p].son[1])  dr=getmax(tr[p].son[1]);
    if(dl>dr){
        if(dl>q.top())  query_max(tr[p].son[0]);
        if(dr>q.top())  query_max(tr[p].son[1]);
    }
    else{
        if(dr>q.top())  query_max(tr[p].son[1]);
        if(dl>q.top())  query_max(tr[p].son[0]);
    }
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    n=read();  K=read();
    for(ll i=1;i<=n;++i){
        a[i][0]=read();  a[i][1]=read();
        tr[i].d[0]=a[i][0],tr[i].d[1]=a[i][1];
    }
    build(root,1,n,0);
    for(ll i=1;i<=(K<<1);++i) q.push(0);
    for(ll i=1;i<=n;++i){
        D[0]=a[i][0];  D[1]=a[i][1];
        query_max(root);
    }
    printf("%lld\n",q.top());
    return 0;
}

本文标题:【算法笔记】KD_Tree

文章作者:chty

发布时间:2017年04月29日 - 16时24分

最后更新:2018年07月09日 - 20时19分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. 算法原理
  2. 2. 例题一
  3. 3. 例题二
  4. 4. 例题三
,