CentralNotice k From Wikipedia, the free encyclopedia Jump to: navigation , search k -d tree Type Multidimensional BST Invented 1975 Invented by Jon Louis Bentley Time complexity in big O notation Average Worst case Space O( n ) O( n ) Search O(log n ) O( n ) Insert O(log n ) O( n ) Delete O(log n ) O( n ) A 3-dimensional k -d tree. The first split (red) cuts the root cell (white) into two subcells, each of which is then split (green) into two subcells. Finally, each of those four is split (blue) into two subcells. Since there is no more splitting, the final eight are called leaf cells. 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 -d trees are a useful data structure for several applications, such as searches ...