![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/3dtree.png/640px-3dtree.png&w=640&q=50)
k-d tree
Multidimensional search tree for points in k dimensional space / From Wikipedia, the free encyclopedia
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?
Summarize this article for a 10 year old
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:
- Searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) &
- Creating point clouds.
Quick Facts k-d tree, Type ...
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 | |||||||||||||||||||||||
|
Close
![](http://upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
Wikimedia Commons has media related to k-d trees.
k-d trees are a special case of binary space partitioning trees.