kd树可以用来解决多维空间查找给定点最近邻的k个点的问题。 ### 基本思想 将给定的所有点组成一棵具有**某种特点**的树。那么可以通过遍历树求解原问题的解，这对应于在数据集中使用线性扫描的方式求解。kd树的作用在于可以使用树的特点进行剪枝从而加快搜索速度。 ### 基础知识 高维空间中点到超平面的距离公式可以表示为