A relaxed K-d tree or relaxed K-dimensional tree is a data structure which is a variant of K-d trees. Like K-dimensional trees, a relaxed K-dimensional tree stores a set of n-multidimensional records, each one having a unique K-dimensional key x=(x0,... ,xK−1). Unlike K-d trees, in a relaxed K-d tree, the discriminants in each node are arbitrary. Relaxed K-d trees were introduced in 1998.[1]
Relaxed k-d tree | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | Multidimensional BST | |||||||||||||||||||||||
Invented | 1998 | |||||||||||||||||||||||
Invented by | Amalia Duch, Vladimir Estivill-Castro and Conrado Martínez | |||||||||||||||||||||||
|
A relaxed K-d tree for a set of K-dimensional keys is a binary tree in which:
If K = 1, a relaxed K-d tree is a binary search tree.
As in a K-d tree, a relaxed K-d tree of size n induces a partition of the domain D into n+1 regions, each corresponding to a leaf in the K-d tree. The bounding box (or bounds array) of a node {x,j} is the region of the space delimited by the leaf in which x falls when it is inserted into the tree. Thus, the bounding box of the root {y,i} is [0,1]K, the bounding box of the left subtree's root is [0,1] × ... × [0,yi] × ... × [0,1], and so on.
The average time complexities in a relaxed K-d tree with n records are: