Two figures showing a kdtree.
The left one shows the split lines around medians, and the right figure show the actual kdtree. More info about kdtrees can be found in book : M. de Berg, M.van Kreveld, M. Overmars, O.Schwarzkopf, "Computational Geometry (Algorithms and Applications) ", Springer, 1998. 

The algorithm used to build the
kdtree in this demonstration. The bound for building a kdtree is O(nlogn). 

The algorithm used in searching
in this demonstration. The bound for searching a kdtree is O(sqrt(n)). 