介绍一下Kd树？如何建树，以及如何搜索最近节点？

kd树是一种对k维空间中的实例点进行存储，以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个节点对应于一个k维超矩形区域。

构造平衡kd树过程：

输入：k维空间数据集

Missing or unrecognized delimiter for \left

$T=\left{x_{1}, x_{2}, \cdots, x_{N}\right}$

输出：kd树

（1）开始：构造根节点，根节点对应于包含T的k维空间的超矩形区域

​ 选择 为坐标轴，以T中所有实例的 坐标的中位数为切分点，将根节点对应的超矩形区域且分为两个子区域。切分由通过切分点并与坐标轴 垂直的超平面实现。

​ 由根节点生成深度为1的左、右子节点：左子节点对应坐标 小于切分点的子区域，右子节点对应于坐标 大于切分点的子区域。

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

（2）重复：对深度为 的节点，选择 为切分的坐标轴，，以该节点的区域中所有实例的 坐标的中位数为切分点，将该节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 垂直的超平面实现。

​ 由该节点生成深度为 的左、右子节点：左子节点对应坐标 小于切分点的子区域，右子节点对应坐标大于切分点的子区域。

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