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

Russell A. Brown

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,…