数据结构_kd-树

拼搏现实的明天。 2022-05-20 23:45 163阅读 0赞

## kd-树 ##

**一维范围查询**  
如下图所示，许多实际应用问题，都可归结为如下形式的查询：给定直线L上的点集P=\{P0,….,Pn-1\}，对于任一区间R=\[x1,x2\]，P中哪些点落在其中。  
![这里写图片描述][70]  
上述这种查找问题统称为一维范围查询，对于这种问题的解决方法，我们通常有以下几种方法解决：  
1、蛮力算法  
可以直接遍历点集P，并且逐个的花费O(1)时间判断各点是否落在区间R内，这样总体的运行时间为O(n)。然而，当我们处理更大规模的输入点集时，这种方法就会显得力不从心。首先，当输入点集的规模大到需要借助外部存储器时，遍历整个点集会引发大量的I/O操作；另外，当数据点的坐标分布范围比较大时，通常的查询所命中的点集，在整个输入点集中只占极低的比例。

2、计数法  
首先通过适当的预处理，将输入点集P提前整理和组织为某种适当的数据结构，就有可能进一步提高以后各次查询操作的效率。例如，可以花费O(nlogn)的时间，将P组织成一个有序向量，如下所示：  
![这里写图片描述][70 1]  
然后对于任何R=\[x1,x2\]，首先利用二分查找算法，在O(logn)时间内找到不大于x2的最大点Pt。然后从右向左的遍历向量中的各点，直至第一个离开区间R的点Ps，期间所有经过的节点都是查询结果。总体的查询时间成本为0(r+logn)。（**输出铭感的**：根据问题的输入规模和输出规模进行估计。）

**二维范围查询**  
在实际应用中，往往还需要同时对多个维度做范围查找，例如下图：  
![这里写图片描述][70 2]  
如上图，在矩形区域R=\[x1,x2\]x\[y1,y2\]内有多少个点。此时，上述计数方法中（基于二分查找）并不能直接推广至二维情况，这是借助平衡二叉搜索树。

--------------------

平衡二叉查找树：结构  
我们还是回到问题的一维版本，尝试其它可以推广至二维甚至更高维的办法。考虑以下例子：  
首先，在O(nlogn)时间内，将点集P组织成下图所示的一颗平衡二叉搜索树：  
![这里写图片描述][70 3]  
叶节点存放输入点，内部节点等于左子树中的最大者。满足：左子树 LTree(v) 中的叶子  x(v) < 右子树 RTree(v) 中的叶子，比如：x(v) = 12：max\{9, 12\} <=12 < min\{14, 15\}。  
借助这种形式的平衡二叉搜索树，我们可以高效的解决一维范围查询问题，假设查询区间为\[2，14\]。  
1、首先分别查找2和14，终止于3和14。记住其最低的共同祖先LCA(3,14)=7。  
2、从这一共同祖先节点出发，分别重走一遍通往节点3和14的路径（分别记作path(3)和path(14)）。在沿着path(3)/path(14)下行的过程中忽略掉所有的**右/左**拐；而对于每一次**左转/右转**，都需要遍历对应的**右子树/左子树**（如下图阴影部分所示）。  
![这里写图片描述][70 4]  
就本例而言，沿path(3)得到的叶子点集为：\{4，7\}；沿path(14)得到的叶子点集为：\{9，12\}。最后还要检查path(3)和path(14)的终点是否满足。  
效率分析：首先预处理花费的时间O(nlogn)，并且空间为O(n)；每次查询的时间都可以在O(r+logn)内完成，同样为输出敏感的算法。

--------------------

**kd-树**  
依着上面介绍采用平衡二叉搜索树实现一维查询的构思，可以将带查询的二维点集组织为kd-树结构。在任何维度下，kd-树都是一颗递归定义的平衡二叉搜索树。下面以2d-树的原理以及构造和查询算法做介绍。  
具体的，2d-树中的每一个节点，都对应于二维平面上的某一矩形区域，如下构思实例：  
![这里写图片描述][70 5]  
树根对应于整个平面。  
**构造算法：**  
若当前节点深度为偶(奇)树，则沿垂直(水平)方向切分，所得子区域随同包含的输入点分别构成左右孩子。如此不断，直至子区域仅含单个输入结点。每次切分都在中位点进行（按对应的坐标排序居中者，以保证全树的高度不超过O(logn)）。  
对于上面实例，划分过程如下：  
![这里写图片描述][70 6]  
最后一轮划分时，对树中人含有至少两个节点的三个深度为2的节点，分成左右两半。

具体可实现如下：

kdTree* buildkdTree(p,d){
       //在深度为d的层次，构造一颗对应于集合p的2d-树
        if (P == {p}) return(CreateLeaf(p));  //递归基
        root = CreateKdNode();    //创建子树根
        root->splitDirection = depth%2 ? HORIZONTAL ：VERTICAL;  //确定划分方向
        root->splitLine = FindMedian(root->splitDirection, P);   //确定中位点
        (P1,P2) = Divide(P, root->splitDirection, root->splitLine);    //子集划分
        root->lChild = BuildKdTree(P1, depth+1);    //深度d+1的层次，构造左子树
        root->rChild = BuildKdTree(P2, depth+1); 
        return (root);
    
    }

由上可以得到kd-树的几条性质：  
1、树节点~矩形区域。  
2、同一节点左、右孩子所对应区域的并，即该节点对应的子区域。  
3、同一层的所有节点对应的子区域互不相交，而且其并就为整个平面。

**查找算法**  
经过以上预处理，将待查询点集p转化为一颗2d-树之后，对于任一矩形区域R的查找，可以分为三种情况：  
1、若矩形区域V完全包含于R内，则其中所有的输入点亦均落在R内。  
2、若二者相交，则要分别深入到V的左、右子树中继续递归地查询。  
3、若二者彼此分离，则子集V中的点不可能落在R内。  
过程可以描述如下：

kdsearch(v,R)
    {
        if(v是叶子)
        {
            if(v在R中)
                report(v);
            return;
        }
    
        if(左子树完全包含R内)
            reportsutree(v->lc);//直接遍历
        esle if(左子树与R相交)
            kdsearch(v->lc,R);//递归查询
    
        if(右子树完全包含R内)
            reportsutree(v->rc);//直接遍历
        esle if(右子树与R相交)
            kdsearch(v->rc,R);//递归查询
    }

平面范围查询与一维情况不同，在同一深度上可能递归两次以上，并报告出多余两颗子树。给出结论，累计耗时O(sqrt(n))。

--------------------

对于更高维度空间中，kd-树依然适用。  
构造：  
深度 = 0 时，沿第 0 维划分  
深度 = 1 时，沿第 1 维划分  
…  
深度 = d‐1 时，沿第 d‐1 维划分  
深度 = d 时，沿第 0 维划分  
…  
深度 = k 时，沿第 k%d 维划分  
**空间：O(n)**  
**预处理：O(nlogn)**  
**查询：O(n^(1-1/d)+r)**

--------------------

[70]: /images/20220521/ffdf64eeee544cb58d4a70a02f1ab4a4.png
[70 1]: /images/20220521/6f8d9aa9b68f475e94095f21f5e8af5e.png
[70 2]: /images/20220521/a8ba8743982544d08571c15be5dbfa9b.png
[70 3]: /images/20220521/940cbfcd63574068a30db60f9ca697b5.png
[70 4]: /images/20220521/5e0f0b5a18a84880aa11477cb9a282f2.png
[70 5]: /images/20220521/8a71711f79db46c5be77ad56d6260f1d.png
[70 6]: /images/20220521/b5c32f00a21c40cc85472945f53321b2.png