Kd-Tree Applet Demo Page

Two figures showing a kd-tree. The left one
shows the split lines around medians,
and the right  figure  show the  actual  kd-tree.

More info about kd-trees can be found in book :

M. de Berg, M.van Kreveld, M. Overmars, O.Schwarzkopf, "Computational Geometry (Algorithms and Applications) ", Springer, 1998.

kdtree image
The algorithm used to build the kd-tree in this

The bound for building a kd-tree
is O(nlogn).

kdtree build algorithm
The algorithm used in searching in this

The bound for searching a kd-tree is
kstree search algorithm