# Building a Balanced k-d Tree in O(kn log n) Time

arXiv: https://arxiv.org/abs/1410.5420 · HTML: https://mlsanity.com/paper/1410.5420/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2014.

## Built on by (most cited first, 4 of 4)

- [Improve Sentence Alignment by Divide-and-conquer](https://mlsanity.com/paper/2201.06907/) (2022)
- [Detection of Small Holes by the Scale-Invariant Robust Density-Aware Distance (RDAD) Filtration](https://mlsanity.com/paper/2204.07821/) (2022)
- [Multicriteria Optimization Techniques for Understanding the Case Mix Landscape of a Hospital](https://mlsanity.com/paper/2308.07322/) (2023)
- [Dynamics Models for Offline Hyperparameter Selection in Real-World RL](https://mlsanity.com/paper/2608.11349/) (2026)

## Abstract (arXiv)

The original description of the k-d tree recognized that rebalancing techniques, such as are used to build an AVL tree or a red-black tree, are not applicable to a k-d tree. Hence, in order to build a balanced k-d tree, it is necessary to find the median of the data for each recursive subdivision of those data. The sort or selection that is used to find the median for each subdivision strongly influences the computational complexity of building a k-d tree. This paper discusses an alternative algorithm that builds a balanced k-d tree by presorting the data in each of k dimensions prior to building the tree. It then preserves the order of these k sorts during tree construction and thereby avoids the requirement for any further sorting. Moreover, this algorithm is amenable to parallel execution via multiple threads. Compared to an algorithm that finds the median for each recursive subdivision, this presorting algorithm has equivalent performance for four dimensions and better performance for three or fewer dimensions.