# K-d tree

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about K-d tree?

SHOW ALL QUESTIONS

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.[1] k-d trees are a useful data structure for several applications, such as:

Quick facts: k-d tree, Type, Invented, Invented by, Time c...
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.
TypeMultidimensional BST
Invented1975
Invented byJon 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)}$
Close

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

Oops something went wrong: