Kd Tree

Published: April 19, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

KDTree意思是K Dimension Tree，即K维树，其可以用于存储K维空间中的点。

实现非常简单，每个结点有左右子结点，如果结点处于第$i$层，那么其左子树存储的是第$i%k$维值小于该结点的结点，因此每一层的比较规则都不同，k层一循环。

KDTree支持插入和删除，与其它二分搜索平衡树区别不大。如果用已知结$n$个结点建树，可以利用第$k$大元素算法在$O(n\log_2n)$的时间复杂度内建立完成。但是这样没法保证修改后依旧平衡，可以利用替罪羊树的思路，提供一个平衡因子，在失去平衡后暴力重建子树。这样插入和删除的时间复杂度摊还为$O(n(\log_2n)^2)$。

KDTree支持很多操作，比较典型的就是区间查询和最近点查询。

区间查询很简单，和线段树差不多，记住要在区间无相加时剪枝。一次查询时间复杂度为$O(2kn^{1-\frac{1}{k}})$。

最近点查询的时间复杂度与距离计算的算法有关，但是无论哪种时间复杂度都很不好算（捂脸）。有两种可行的优化，一种是每次进入左右子结点之前，先预估哪边可能最近的顶点，并选择拥有最近顶点的那个分支，这样一般效果不错。（说白了就是剪枝呗）

下面提供几道题目：

最近K点查询