构造平衡kd树

• 算法：

算法：

$\qquad$ 输入：$k$ 维空间数据集 $T=\{x_1,x_2,\ldots ,x_N\}$, 其中 $x_i=(x_i^{(1)},x_i^{(2)},\ldots,x_i^{(k)})^T,\quad i=1,2,\ldots,N$；

$\qquad$ 输出：$kd$ 树

$\qquad$ (1) 开始：构造根节点，根节点对应于包含 $T$ 的 $k$ 维空间的超矩形区域。

$\qquad$ 选择 $x^{(1)}$ 为坐标轴，以 $T$ 中所有实例 $x^{(1)}$ 坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。

$\qquad$ 由根节点生成深度为 $1$ 的左、右子节点：左子结点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子节点对应于坐标 $x^{(1)}$ 大于切分点的子区域。

$\qquad$ 将落在切分超平面上的实例点保存在根节点。

$\qquad$ (2) 重复：对深度为 $j$ 的节点，选择 $x^{(l)}$ 为切分的坐标轴，$l=j(\mod k)+1$,以该节点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该节点对应的超矩形区域划分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。

$\qquad$ 由该节点生成深度为 $j+1$ 的左、右子节点：左子节点对应坐标 $x^{(l)}$小于切分点的子区域，右子节点对应坐标 $x^{(l)}$ 大于切分点的子区域。

$\qquad$ 将落在切分超平面上的实例点保存在该节点。

$\qquad$ (3) 直到两个子区域没有实例存在时停止。从而形成 $kd$ 树的区域划分。