kd树knn算法
给定kd树,求距离p点最近的k个样本。
零、L为有k个空位的列表
(一)、根据p的坐标值和每个节点的切分向下搜索。
(二)、到达一个底部节点时,标记。如果L不足k,当前节点加入L;如果L有值,且当前节点与p的距离小于L里最长的距离,用点前点替换L中离p最远的点。
(三)、如果当前节点不是最顶点,执行(a);否则,输出L,完成。
(a)向上爬一个节点。如果爬过的节点未被标记,则标记,然后执行(1)和(2);如果已被标记,再执行(a)。
(1)如果L不足k,将此节点加入L;如果L已满,且当前节点与p的距离小于L里最长距离,则替换之。
(2)计算p与当前节点切分线距离。如果该距离大于等于L中距离p最远的距离且L中已满,执行(三);如果该距离小于L中最远距离或L未满,从当前节点另一枝从(一)开始。