title: Kd-Tree Question
body: <p>I am trying to implementation and understand <code>KdTree</code>, Following is the link I found.
  <a href="http://ldots.org/kdtree/#buildingAkDTree" rel="nofollow">http://ldots.org/kdtree/#buildingAkDTree</a>
  But I fail to understand following algorithm</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>I do not understand what is the meaning of 
  <code>Calculate the median x-value.</code></p>