1. KD 树构建

KD 树的构建需要确定两个问题：

1. 选择使用那个维度作为分裂点：
   1. 随机选择
   2. 顺序选择
   3. 方差最大的维度
2. 确定以当前维度那个值作为分裂点：
   1. 中位数
   2. 注意：如果中位数对应的不是一个具体的样本点，可以任意选择前后两个点

分析案例：

T = { (2,3), (5,4), (9,6), (4,7), (8,1), (7,2) }

1. 使用最大方差方法选择分裂维度：
   1. x 轴的方差：
      1. 计算均值：( 2 + 5 + 9 + 4 + 8 + 7) / 6 = 5.83
      2. 计算方差：(2 – 5.83)² + (5 – 5.83)² + (9 – 5.83)² + (4 – 5.83)² + (8 – 5.83)² + (7 – 5.83)² = 34.83
   2. y 轴的方差：
      1. 计算均值：(3 + 4 + 6 + 7 + 1 + 2) / 6 = 3.83
      2. 计算方差：(3 – 3.83)² + (4 – 3.83)² + (6 – 3.83)² + (7 – 3.83)² + (1 – 3.83)² + (2 – 3.83)² = 26.83
   3. 最终：选择方差较大的 x 轴作为分裂维度。
2. 选择 x 轴的中位数作为分裂点：
   1. 对 x 轴数据进行排序： 2、4、5、7、8、9
   2. 取中位数：7，对应的样本点为：（7, 2）
3. 选择 y 轴作为分裂维度，并选取其中位数作为分裂点：
   1. 左子树：{ (2, 3), (5, 4), (4, 7) } 中位数：4
   2. 右子树： { (9, 6), (8, 1) } 中位数：6
4. 此时，KD 树构建完毕，如下图所示：

2. KD 树搜索

KD 搜索主要通过两步来完成：

1. 正向搜索：确定点所在区域，以及搜索路径
2. 反向回溯：在区间、临近区间搜索最近邻点

接下来，通过两个例子来理解搜索过程：

1. 查找点: (2.1, 3.1)
   1. 正向搜索: (7, 2)、(5, 4)、(2, 3)
   2. 反向回溯：
      1. 反向回溯取出样本点 (2, 3)，并计算该点和 (2.1, 3.1) 之间的距离：0.141
      2. 反向回溯取出样本点 (5, 4)，以 (2.1, 3.1) 为圆心，0.141 为半径，判断是否和 y=4 相交
         1. 如果不相交：则不用在 (5, 4) 的右子树去搜索
         2. 如果相交：则需要在 (5, 4) 的右子树可能存在更近临的点
         3. 此处不相交
      3. 反向回溯取出样本点 (7, 2), 以 (2.1, 3.1) 为圆心，0.141 为半径，判断是否和 x=7 相交
         1. 如果不想交：则不用在 (7, 2) 的右子树去搜索
         2. 如果相交：则需要在 (7, 2) 的右子树可能存在更近临的点
         3. 此处不相交

1. 查找点: (2, 4.5)
   1. 正向搜索: (7,2)、(5,4)、(4,7)
   2. 反向回溯：
      1. 反向回溯取出样本点 (4, 7)，并计算该点和 (2, 4.5) 之间的距离：3.202
      2. 反向回溯取出样本点 (5, 4)，以 (2, 4.5) 为圆心，3.202 为半径，判断是否和 y=4 相交
         1. 如果不相交：则不用在 (5, 4) 的左子树去搜索
         2. 如果相交：则需要在 (5, 4) 的左子树可能存在更近临的点
         3. 此处相交：
            1. 将左子树结点 (2, 3) 加入到回溯列表中，此时回溯列表为： (7,2)、(2,3)
            2. 计算 (5, 4) 与 (2, 4.5 ) 的距离为：3.04，小于 3.202，更新最近邻点为：(5, 4)
      3. 反向回溯取出样本点 (2, 3)，由于该点是叶子结点，直接计算 (2, 3) 和 (2, 4.5) 距离为：1.5，更新最近邻点为：(2, 3)
      4. 反向回溯取出样本点 (7, 2)，以 (2, 4.5) 为圆心，1.5 为半径的圆并不和 x=7 相交
      5. 至此，反向回溯路径为空，(2, 3) 作为 (2, 4.5) 的最近邻点，距离为：1.5