k-d tree

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. K-dimensional is that which concerns exactly k orthogonal axes or a space of any number of dimensions. k-d trees are a useful data structure for several applications, such as:

• Searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) &
• Creating point clouds.

k-d tree
A 3-dimensional k-d tree. The first split (the red vertical plane) cuts the root cell (white) into two subcells, each of which is then split (by the green horizontal planes) into two subcells. Finally, four cells are split (by the four blue vertical planes) into two subcells. Since there is no more splitting, the final eight are called leaf cells.
Type	Multidimensional BST
Invented	1975
Invented by	Jon Louis Bentley
Time complexity in big O notation Operation Average Worst case Search ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ Insert ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ Delete ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ Space complexity Space ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

k-d trees are a special case of binary space partitioning trees.