K-DTree

• 什么是 K-D Tree ?
  1.对多维平面的一个划分。
  2.询问就是进行启发式搜索。
  3.也可以进行插入操作，所以也算是在线?

• K-D Tree 是用来做什么的?
  1.求n个点中离询问的点最近 ( 最远 ) 的点、第K远 ( 近 ) 的点。
  2.这里的距离可是曼哈顿距离、欧拉距离还有各种奇奇怪怪的距离。

• K-D Tree 复杂度？
  1.传说中有两种算法，然而我只看了一种。
  2.建树的复杂度：$T(n) = 2T(n/2) + O(n) => T(n) = O(nlogn)$
  3.查询复杂度，启发式搜索复杂度本来就是玄学，主要取决于你的评估函数。有人证明最坏是$O(N^{(1-1/k)})$,其中k是维度。实际上很难到这么大的，不过确实比 $logN$ 要大。

• 常用的几种评估函数写法(还挺快的)。