# How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees:

Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. [..] This algorithm presorts n points in each of k dimensions

I fail to understand how that is actually done. Consider this example:

Lets say I have 5 points in an array.

0 = (4, 7)
1 = (2, 9)
2 = (5, 4)
3 = (3, 6)
4 = (2, 1)


I suppose we now want to create 2 sorted arrays, one by X and one by Y ?

Sort them by X     Sort them by Y
1 = (2, 9)         4 = (2, 1)
4 = (2, 1)         2 = (5, 4)
3 = (3, 6)         3 = (3, 6)
0 = (4, 7)         0 = (4, 7)
2 = (5, 4)         1 = (2, 9)


We start creating the KD-Tree. Lets split by X axis, at the first step. We select the median of the points, 3 = (3, 6), so the Left and right trees will like this:

Left  (first half)
1 = (2, 9)
4 = (2, 1)

Right  (second half)
0 = (4, 7)
2 = (5, 4)


Now we want to sort the Left and the Right trees by Y axis. How are we supposed to make use of the points that we sorted previously by Y axis ?

The only solution in my eyes is to re-sort the Left and Right trees respectively, by Y axis. What is Wikipedia talking about ?

• (I hope the sentences following in the wikipedia article sum it up usefully: presorts n points in each of k dimensions using an O(n log n) sort […] prior to building the tree[, maintain] the order of these k presorts during tree construction and thereby [avoid] finding the median at each level of subdivision.) (From skimming the references given, I can't tell the connection to Havran V., Bittner J. "On improving k-d trees for ray shooting" (2002).) – greybeard Apr 30 '16 at 19:37
• Maybe you could try a z-ordering instead of median? Z-ordering (en.wikipedia.org/wiki/Z-order_curve) can be achieved by interleaving the bits of the coordinates. – TilmannZ May 2 '16 at 9:29
• (There is jcgt.org.) – greybeard Apr 29 '20 at 5:23

## 1 Answer

At depth = 1, with your pre-sorted Y list, you'll still need to perform a comparison to the parent node (and compare by X value).

This ensures that items on the left branch will have X value less than parent node, and items on right branch will have X value greater than parent node.

Since at depth = 1, your list is already pre-sorted by Y value, you save time from sorting at each level.

In the case that your item is the same as the parent node, you don't insert, because that node is already the parent.