KDツリーアルゴリズム

KDツリーアルゴリズムを学習して、最近の隣マッチングを行うために使用しました.その疑似コードは以下の通りです.

# KD       

#     ：
# node{
#     node_data   #     
#     node_left   #    
#     node_right  #    
#     node_parrent#    
#     node_s      #     
# }

#   KD ：
#   ：  list
#   ：KD    
def build_tree(list):
    if list is None:
        return None
    #                ，        vi     
    #      vi     ，      tree_node
    for point in other_points:
        if point[vi] < tree_node[vi]:
            left_points.append(point)
        else:
            right_points.append(point)
    build_tree(left_points)
    #      left_points          tree_node
    build_tree(right_points)
    #      right_points          tree_node

#      ：
#   ：KD    kd,    target
#   ：  target     min_node,      min_dis
def find_nn(kd, target):
    if kd is None:
        return 'kdTree is None'
    while kd is not None:       #   1：     
        search_path.append(kd)  # search_path      ，         
        min_node = kd
        if target[s] < kd[s]:
            kd = kd.left
        else:
            kd = kd.right
    min_dis = distans(kd.data, target)

    while kd is not None:       #   2：  
        back_point = search_path.pop()
        if distans(back_point[s], target[s]) < min_dis: #          ，         
            if target[s] < back_point[s]:   #         ，      
                kd = back_point.right
            else:                   #         ，      
                kd = back_point.left
            search_path.push(kd)    #       

        if distans(kd.data, target) < min_dis:   #                  ，          
            min_dis = distans(kd.data, target)
            min_node = kd
    return min_node.data, min_dis

参考:
http://acm.hdu.edu.cn/showproblem.php?pid=2966
https://blog.csdn.net/v_jurlyuv/articale/detail/8203674
https://blog.csdn.net/acdreamers/article/details/44664645
https://www.cnblogs.com/eyeszjwang/articles/2429382.html
http://blog.51cto.com/underthehood/687160
https://blog.csdn.net/lhanchao/article/details/52535694