k -d tree

A -dimensional tree or -d-tree is an unbalanced search tree for storing points from the . Similar to the area tree, it offers the possibility of performing orthogonal area inquiries. The query complexity is higher, but the memory overhead is instead . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle O(kn)}$ ${\displaystyle O(n(\log n)^{k-1})}$

kd trees are special cases of CLT trees whose dividing hyperplanes are aligned along the axes of the coordinate system.

It was introduced by Jon Bentley .

definition

There are homogeneous and inhomogeneous k -d-trees. In the case of homogeneous k -d trees, each node stores a data set. In the inhomogeneous variant, the inner nodes only contain keys, the leaves contain references to data records.

For an inhomogeneous k -d tree, let the axis-parallel -dimensional hyperplane be at that point . For the root, the points are divided by the hyperplane into two point sets of as much as possible the same size and this is entered in the root; to the left of this all points that are smaller than , to the right of the root all larger ones are stored . For the left child node, the points are again divided by a new split level and this is saved in the inner node. To the left of this all points are saved whose is smaller than . This is now continued recursively across all dimensions. Then we start again with the first dimension until each point can be clearly identified by hyperplanes. ${\displaystyle H_{i}(t)=(x_{1},x_{2},\ldots ,x_{i-1},t,x_{i+1},\ldots ,x_{k})}$ ${\displaystyle 1\leq i\leq k}$ ${\displaystyle (k-1)}$ ${\displaystyle t}$ ${\displaystyle H_{1}(t)}$ ${\displaystyle t}$ ${\displaystyle x_{1}}$ ${\displaystyle t}$ ${\displaystyle H_{2}(t)}$ ${\displaystyle t}$ ${\displaystyle x_{2}}$ ${\displaystyle t}$

A k -d tree can be constructed in. Orthogonal range inquiries can be answered in, where denotes the size of the answer. The storage space requirement for the tree itself is in . ${\displaystyle O(n(k+\log n))}$ ${\displaystyle O(n^{1-{\frac {1}{k}}}+a)}$ ${\displaystyle a}$ ${\displaystyle O(k\cdot n)}$

Example 2-D tree

See also

• Quadtree
• Octree
• UB tree
• R tree
• Area tree
• Gridfile

literature

• JL Bentley: Multidimensional binary search trees used for associative searching . In: Communications of the ACM , 18, 9, September 1975, pp. 509-517.
• JL Bentley: Kd Trees for Semidynamic Point Sets. In: SCG '90: Proceedings of the 6th Annual Symposium on Computational Geometry , 1990, pp. 187-197, doi: 10.1145 / 98524.98564 .
• Rolf Klein: Algorithmic Geometry , 2nd edition. Springer-Verlag, Berlin / Heidelberg 2005, ISBN 3-540-20956-5 .

Web links

• kd tree . University of Osnabrück