kdtree最简单易懂的介绍

路奇

2023-12-01

1. K-D TREE

1.1. kd-tree定义

基于分区idea的二叉树型数据结构，树中每个节点都是k-dimensional数据。能够用于搜索查询（邻居）和构建点云。

1.2. kd-tree如何分区

树中除了叶子节点以外，其他的节点都通过找到一个超平面将其切割为左子树和右子树。如何找到超平面进行划分，对于k维数据，我们只选择其中的一个维度，然后设定一个值，大于这个值的是一半，小于这个值的也是一半。超平面根据这个值确定，超平面的法线就是这个由这个维度这个值构成的one hot向量。

1.3. kd-tree的两个约束

从哪个维度开始来构建超平面是个问题，所以kd-tree的第一个约束就是从头开始，循环的选择维度来划分数据，构建二叉树。

另外就是用什么值来分割也是个问题，kd-tree的第二个约束就是用当前选择划分维度的中位数来进行划分。

1.3.1对两个约束的思考

引入两个约束能够帮助我们构建平衡树，也就是叶节点距离根节点的距离差不多远，毕竟选择的中位数来进行划分，而且每个维度都“平等的”遍历过。但是问题就是这两个约束并不是必须要遵守的，我们可以灵活一点，因为找到中位数需要使用O(n)算法复杂度，排序之后直接选择中位数即便是使用堆排或快排复杂度也在O(nlog(n))左右。所以说，我们为了构建近似的平衡树，可以通过选择对一部分数据进行中位数的选择。

跑题一下，平衡树的优点就是他的空间复杂度比较低（时间复杂度都一样），遍历平衡树的空间复杂度是O(log(n))，最坏情况是O（n），最好情况是O（1），原因和树的左偏右偏和尾递归有优化（不压栈）有关，不在这里详细讨论。

1.4. 伪代码

伪代码言简意赅，不进行解读了。

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtree
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

不过上面的代码不够细节，因为有些点具有相同的median，到底是分到左边还是右边呢？其中一个选项就是随机分，另外一个选项就是通过引入更多维度来进行站边。

这个算法的时间复杂度，是O(nlog(n))（排序n平衡树的遍历log(n)），最坏情况下是O(knlog(n)) (每次划分所有节点都落在median上，所以要引入其他k-1个维度才能确定分到最左边还是右边)，空间复杂度比较复杂，不在这里讨论。

1.5. 实现代码

简单解读：
Node数据解构初始化
然后进入函数，找到中位数
返回对象，在对象中递归调用函数（在对象里调用函数这个写的让人眼前一亮）

from collections import namedtuple
from operator import itemgetter
from pprint import pformat

class Node(namedtuple("Node", "location left_child right_child")):
    def __repr__(self):
        return pformat(tuple(self))

def kdtree(point_list, depth: int = 0):
    if not point_list:
        return None

    k = len(point_list[0])  # assumes all points have the same dimension
    # Select axis based on depth so that axis cycles through all valid values
    axis = depth % k

    # Sort point list by axis and choose median as pivot element
    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2

    # Create node and construct subtrees
    return Node(
        location=point_list[median],
        left_child=kdtree(point_list[:median], depth + 1),
        right_child=kdtree(point_list[median + 1 :], depth + 1),
    )

def main():
    """Example usage"""
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = kdtree(point_list)
    print(tree)

if __name__ == "__main__":
    main()

2. K-D TREE最近邻居搜索的思路

这是一个比较大的课题，有很多算法比这个算法要好，我们在这里只讨论k-d tree的。

首先先第一次遍历整个k-d tree，看看median决定走左边还是右边直到根节点（这么走可能走错，导致根节点并不是离我们要节点最近的，但是先别管），先把根节点假设成离我们要的节点最进的，这一步骤需要时间复杂度O(n*log(n))
然后按照当前的最近距离我们对树进行递归遍历
- 如果遍历的当前节点比当前最近距离近，那我们替换掉当前最近距离
- 然后在选择左边和右边子树的时候，不同于第一次遍历，我们这次需要搜索是否另外一边有更近的点
  - 方法是对我们要搜索的节点构建超球面，说人话就是以半径为当前最近距离的球，如果和当前中位数节点所构成的超平面相交，那么就证明另外一边有可能有更近的节点（路可能走错了，那边也要走一下），反之则没有（这个很好解释，我们假设路没有走错，那就默认了所有的邻居在当前维度上统一都超过或小于中位数，但是我们要验证这是不是对的，我们构建超平面就相当于穷举范围内的所有点，如果发现不成立，就意味着可能存在更近的邻居不能单独根据当前维度来判断，我们需要上另外一边看一看）。

3. K-D TREE构建最小生成树

最小生成树prims算法是根据贪心算法不断的访问当前集体的周边邻居，然后拉最近的入伙。而KD tree能快速帮我们为每一个节点找到周边邻居。

我的思路是：那么我们先利用KDtree为每一个节点找到其邻居们。然后将第一个点纳入集合，并且把第一个邻居节点纳入集合。然后我们遍历当前集合的点对应的所有邻居节点，不包括已经加入集合的点，找到新的需要加入到集合的节点，并且重复这个步骤。

别人是怎么写的：代码解读
反正不是太难，写个循环每次找一个新的点，然后使用UNIONFind完成xxx 未完成。。。。