构造平衡kd树

算法：构造平衡kd树

输入：数据集T，T包含m个n维的数据 输出：kd树

第一步：构造根结点 第二步：重复划分 令当前结点的深度为depth，计算： feature = depth % n value = T[:, feature]的下中位数。 选择在第feature个特征上基于value将数据划分成2份。 第三步：结束 区域中没有实例时停止。

# 计算下中位数
def getDownMedian(data):
    if data.shape[0] % 2 == 0:
        data = np.hstack([data, np.inf])
    return np.median(data)

def seperateNode(node, depth):
    dataSet = node['data']
    if dataSet.shape[0] == 0:
        return None
    feature = depth % dataSet.shape[1]
    value = getDownMedian(dataSet[:, feature])
    node['left'] = {'data':dataSet[dataSet[:,feature] < value, :], 'left':None, 'right':None}
    node['right'] = {'data':dataSet[dataSet[:,feature] > value, :], 'left':None, 'right':None}
    node['data'] = dataSet[dataSet[:,feature] == value, :]
    seperateNode(node['left'], depth+1)
    seperateNode(node['right'], depth+1)
    return node   

def createTree(dataSet):
    root = {'data':dataSet, 'left':None, 'right':None}
    seperateNode(root, 0)
    return root 
`