A balanced k-d tree organizes multidimensional points so recursive partitions keep the subtrees near equal size. When the points are known before construction, choosing coordinate-wise medians produces a tree with worst-case logarithmic search and insertion. This is most useful when the structure remains mostly static; frequent updates can destroy the balance guarantee. section 9.3.3
Construct the tree recursively:
- At recursion level d, compare points using coordinate d mod k. section 9.3.3
- Choose the median point as the current node, then partition the remaining points into left and right sets of roughly equal size. section 9.3.3
- Build both subtrees with the next level until the point set is empty or contains one point. section 9.3.3
- Building takes O(n log n) time and O(n) memory under the stated partitioning analysis; balanced search and insertion take O(log n). section 9.3.3 section 9.3.7
Two-dimensional construction
For a two-dimensional point set, select a median by the first coordinate at the root. At the next level, select medians by the second coordinate, then alternate coordinates as recursion continues. Each partition leaves smaller points on one side and larger points on the other with respect to the active coordinate. 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
The construction pseudocode makes the level-dependent partitioning, recursive subtrees, and median-node assembly explicit. section 9.3.3
