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. |
|
The algorithm used to build the
kd-tree in this demonstration. The bound for building a kd-tree is O(nlogn). |
|
The algorithm used in searching
in this demonstration. The bound for searching a kd-tree is O(sqrt(n)). |