Kd-Tree問題

Question

我試圖執行並瞭解KdTree，以下是我找到的鏈接。 http://ldots.org/kdtree/#buildingAkDTree 但我不明白下面的算法

tuple function build_kd_tree(int depth, set points): 
    if points contains only one point: 
     return that point as a leaf. 

    if depth is even: 
     Calculate the median x-value. 
     Create a set of points (pointsLeft) that have x-values less than 
      the median. 
     Create a set of points (pointsRight) that have x-values greater 
      than or equal to the median. 
    else: 
     Calculate the median y-value. 
     Create a set of points (pointsLeft) that have y-values less than 
      the median. 
     Create a set of points (pointsRight) that have y-values greater 
      than or equal to the median. 

    treeLeft = build_kd_tree(depth + 1, pointsLeft) 
    treeRight = build_kd_tree(depth + 1, pointsRight) 

    return(median, treeLeft, treeRight) 

我不明白什麼是 Calculate the median x-value.

Answer 1

你points有x和y值的含義。所述x的median值可以通過由x排序，然後取來獲得中間元件的x（爲奇數的points）或是兩者中間points'x的平均值（對於偶數的points）。

或者，使用快速selection algorithm，如中位數的中位數。