Kd Tree

Published: by Creative Commons Licence

  • 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(n^{1-\frac{1}{k}})$。

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

下面提供几道题目:

最近K点查询