Multidimensional search tree

Multidimensional search tree --- многомерное дерево сортировки.

Multidimensional search trees (or [math]\displaystyle{ K-d }[/math] trees) are a generalization of the well known binary search trees, that handles records with keys of [math]\displaystyle{ K }[/math] attributes. In what follows and without loss of generality, we identify a record with its corresponding key as [math]\displaystyle{ x = (x^{(1)}, x^{(2)}, \ldots, x^{(K)}) }[/math], where each [math]\displaystyle{ x^{(i)} }[/math], [math]\displaystyle{ 1 \leq i \leq K }[/math], refers to the value of the [math]\displaystyle{ i }[/math]-th attribute of the key [math]\displaystyle{ x }[/math].

A multidimensional search tree for a set of keys is a binary tree in which:

1. Each node contains a [math]\displaystyle{ K }[/math]-dimensional key and has an associated discriminant [math]\displaystyle{ j \in \{1, 2, \ldots, K\} }[/math].

2. For every node with a key [math]\displaystyle{ x }[/math] and discriminant [math]\displaystyle{ j }[/math], any key [math]\displaystyle{ y }[/math] in the left subtree satisfies [math]\displaystyle{ y^{(j)} \lt x^{(j)} }[/math] and any key [math]\displaystyle{ y }[/math] in the right subtree satisfies [math]\displaystyle{ y^{(j)} \gt x^{(j)} }[/math].

3. The root node has depth 0 and discriminant 1. All nodes at the depth [math]\displaystyle{ d }[/math] have the discriminant [math]\displaystyle{ (d\pmod{K}) + 1 }[/math].

Note that, if [math]\displaystyle{ K = 1 }[/math], then multidimensional search tree is a binary search tree.