ζ

k-Dimensional Tree

    杂记

照理来说，这篇文章的tag应该是“算法”，但笔者深知自己对k-D树的理解还远远不够，说这篇文章是算法笔记实在是太牵强了。

之前笔者写了有关线段树的博客。众所周知，线段树本是起源于计算几何中的的一种数据结构，不同于一般意义上的线段树，计算几何中的线段树的叶结点维护的并不是一个单点的值，而是跟非叶结点一样维护一个区间，或者说一个“线段”的值，照这个逻辑，我们常用的线段树其实更应该被称作“点树”。

看一看本篇博客的标题，所谓“k-Dimensional Tree”，翻译过来应该是“k维树”，意思是每个结点都维护了一个k维空间中的点集的一棵树。而一维的空间其实就是一条线段，所以（计算几何中的）线段树，其实就是一维的k-D树，或者说“1-D树”。

类比线段树（然而线段树其实是1-D树，我类比我自己了属于是），可以大概知道k-D树是怎样的一棵树了：树的根节点维护问题整个（k维的）空间的信息，每个节点node的左右子节点分别维护node结点的一半空间的信息。这里的“信息”因题而异，但总是解题需要的，当前空间中的点的信息。

由于线段只有一个维度，将一根长线段划分为两根线段只有一种方法，而如果要将一个k维空间划分的方法就比较多了。比如：对一个二维平面（可以想像成一张纸），一刀可以将它切成上下两半或者是左右两半；一个三位平面（比如一个蛋糕），一刀可以把它切成上下两块，左右两块，或者是拦腰切成两层。应该如何划分空间呢？对于一个（树的）结点的划分，实际上就是对它所维护的（空间中的）点集的划分。如何，或者说“应当基于什么样的原则”来划分点集？这个问题在后面会提到。

k-D树的基础性的共通内容其实就这么多，看了上面一大串逼逼叨叨还一头雾水的同志可以看这个视频。

这里插播一句不算题外话的题外话。在线段树中，必须保证一个结点的两个子结点所维护的信息可以可以在合并时直接更新到父节点，比如：一个区间的最大值必然是左半区间的最大值和右半区间最大值中较大的那个，一个区间所有数的最大公因数必然是左半区间中所有数的最大公因数与右半区间的最大公因数这两个数的最大公因数…云云。这（貌似）是被称为“区间加性”。作为高维度的线段树的k-D树所维护的信息当然也是要满足“空间加性”的。虽然这是题外话，但它之所以又不算题外话，是因为接下来的博文默认读者已经知道了k-D树所维护的信息需要满足k维空间加性这一不算常识的常识。

如何使用k-D树进行解题？自然需要让它存储有用的信息。虽然使用同一数据结构存储不同信息来解决不同问题的方法总是大同小异的，但数据结构的核心并不是“结构”，而是“数据”。不论是什么数据结构，光搭起一个架子，里面不装对解题有版主的数据，就没有任何用处。将数据存储在特定的数据结构中是为了更高效地访问这些数据，“高效访问”的含义不止是快速得到想要的数据，更是通过特定的访问顺序来在一次访问中得到更多的信息，从而减少访问的次数。数据结构没有模板题，就像所有满足区间加性的的信息都能用线段树维护一样，所有满足k维空间加性的信息都能用k-D树来维护。随着维度的增加，信息的混沌程度总是会发生不可思议的增加，不同题目间需要使用k-D树维护的信息总是大相径庭。这里以比较经典的问题平面最近点对为例，探讨k-D树在实际解题中的应用。

使用k-D树将整个点集划分为多个子空间的点集后需要探讨的问题就是：树的每个结点应该存储的是其中的点集的什么信息？

答案是：点集的横纵坐标的最大值和最小值（一共四个值）。由于2-D树的各节点维护的信息实际上是一个矩形区域中的点集的信息，点集横纵坐标的最大值和最小值实际上就是这个矩形四角上的顶点的坐标，也就是这个举行所占的区域。

建好2-D树后，每次将点集中的一个点作为丢进去搜索，查找与它距离最近的点。查找的方式如下：对于每个结点，都假设它所维护的矩形区域中所有位置都有点，以估算其中的点到目标点的最短距离。如果这个点集的估算最短距离比已经得到的最短距离答案还长，那就没有遍历这个点集的必要了。

接下来讨论之前流的尾巴：如何划分点集？感性分析，点集中的点越分散，估计的结果也就越准确，越有效，因此应按照尽可能分散的原则划分点集，即每次划分都求一下待划分点集各维的方差，选取方差最大的一维划分。实际上，k-D树对于点集的划分总是基于方差来实现的。

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;
int tot, d;
struct ptt
{
    double a[2];
    bool operator<(const ptt &x) const
    {
        return a[d] < x.a[d];
    }
} pt[200005];
struct nd
{
    int lson, rson, di;
    double lt, rt, up, dn;
    ptt p;
    void gen();
    double cmp(int x)
    {
        double ret = 0;
        if (lt > pt[x].a[0])
            ret += (lt - pt[x].a[0]) * (lt - pt[x].a[0]);
        if (rt < pt[x].a[0])
            ret += (rt - pt[x].a[0]) * (rt - pt[x].a[0]);
        if (dn > pt[x].a[1])
            ret += (dn - pt[x].a[1]) * (dn - pt[x].a[1]);
        if (up < pt[x].a[1])
            ret += (up - pt[x].a[1]) * (up - pt[x].a[1]);
        return ret;
    }
} node[200005];
void nd::gen()
{
    lt = rt = p.a[0], up = dn = p.a[1];
    if (lson)
        lt = min(lt, node[lson].lt), rt = max(rt, node[lson].rt),
        dn = min(dn, node[lson].dn), up = max(up, node[lson].up);
    if (rson)
        lt = min(lt, node[rson].lt), rt = max(rt, node[rson].rt),
        dn = min(dn, node[rson].dn), up = max(up, node[rson].up);
}
long double fangcha(int l, int r, int it)
{
    long double avg = 0, ret = 0;
    int i;
    for (i = l; i <= r; i++)
        avg += pt[i].a[it];
    avg /= r - l + 1.0;
    for (i = l; i <= r; i++)
        ret += (avg - pt[i].a[it]) * (avg - pt[i].a[it]);
    return ret;
}
int build(int l, int r)
{
    if (l >= r)
        return 0;
    int root = l + (r - l >> 1);
    if (fangcha(l, r, 0) > fangcha(l, r, 1))
        node[root].di = d = 0;
    else
        node[root].di = d = 1;
    nth_element(pt + l, pt + root, pt + r + 1);
    node[root].lson = build(l, root - 1);
    node[root].rson = build(root + 1, r);
    node[root].p = pt[root];
    node[root].gen();
    return root;
}
double res;
double dis(int x, int y)
{
    return (pt[x].a[0] - pt[y].a[0]) * (pt[x].a[0] - pt[y].a[0]) +
           (pt[x].a[1] - pt[y].a[1]) * (pt[x].a[1] - pt[y].a[1]);
}
void query(int l, int r, int tar)
{
    if (l > r)
        return;
    int md = l + (r - l >> 1);
    if (md != tar)
        res = min(res, dis(md, tar));
    if (l == r)
        return;
    double disl = 2e20, disr = 2e20;
    if (node[md].lson)
        disl = node[node[md].lson].cmp(tar);
    if (node[md].rson)
        disr = node[node[md].rson].cmp(tar);
    if (disl < res && disr < res)
    {
        if (disl < disr)
        {
            query(l, md - 1, tar);
            if (disr < res)
                query(md + 1, r, tar);
        }
        else
        {
            query(md + 1, r, tar);
            if (disl < res)
                query(l, md - 1, tar);
        }
    }
    else
    {
        if (disl < res)
            query(l, md - 1, tar);
        if (disr < res)
            query(md + 1, r, tar);
    }
}
int main()
{
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%lf%lf", &pt[i].a[0], &pt[i].a[1]);
    build(1, n);
    res = 2e20;
    for (i = 1; i <= n; i++)
        query(1, n, i);
    printf("%.4f", sqrt(res));
    return 0;
}
页阅读量:  ・  站访问量:  ・  站访客数: