A median is a middle-ranked value that divides an ordered collection into lower and higher portions. In a balanced k-d tree, choose the median point along the current coordinate as the subtree pivot, placing roughly equal numbers of points on each side. section 9.3.3
The comparison coordinate changes with recursion depth: use coordinate level % k, then recursively partition the left and right sets using the next coordinate. A single initial sort cannot replace these changing criteria. section 9.3.3
Listing 9.6 Balanced construction
function constructKdTree(points, level=0) #1
if size(points) == 0 then #2
return null
elsif size(points) == 1 then #3
return new KdNode(points[0], null, null, level)
else
(median, left, right) ← partition(points, level) #4
leftTree ← constructKdTree(left, level + 1) #5
rightTree ← constructKdTree(right, level + 1) #5
return new KdNode(median, leftTree, rightTree, level) #6
Constructs a balanced k-d tree by partitioning points around a median and recursively building both subtrees. section 9.3.3
Two-dimensional partition
For a two-dimensional point set, the first partition selects (-0.5, 0) as the median; the next level selects (-1, 1) for the left subset. The resulting partitions contain three points on one side and four on the other, then one point on each side at the next level.
