要求： 对平面内每一个点都找到离它最近的点。通常想法是knn，那么由于是对n个点求，直接算的话就是n平方。
我们利用kd树来搜索，那么复杂度就变为了nlogn,甚至说由于a与b距离最小等价于b与a最小，我们可以减少到(nlogn)/2;
建树： 对于一个二维空间的一堆点，首先对第一维考虑，找到第一维的中位数，按照中位数划分为两部分。小的放在左子树，大的放在右子树。然后按照第二维来划分，再建树，再按照第一维来划分，以此类推，直到所有点都成为节点。
搜索： 杜对于一个query，首先先按照第一维来分为左右两边分别搜索，假如小，那么继续搜索左边。然后按照第二维继续搜，再按照第一维，以此类推。搜索到query的点后，回溯，往其父节点走，再根据父节点往另一节点走，假如往另一个节点发现距离大了，那么就停止往另一个节点的下面走，而是继续往父节点走，依次类推。
参考《统计学习方法》 P41
转载请注明原文地址: https://ju.6miu.com/read-668635.html
