Arbre kd relaxé
# Arbre kd relaxé

Un arbre kd relaxé ou arbre à k-dimension relaxé est une structure de données qui est une variante de l'arbre kd. Comment les arbres kd, un arbre kd relaxé stocke un ensemble de données à n-dimensions, chacune ayant une unique étiquette à K-dimensions $x=(x_0,...$ $,x_{K−1}).$ Contrairement aux arbres kd, dans un arbre kd relaxé, le discriminant dans chaque nœud est arbitraire. Les arbres kd relaxés ont été introduits en 1998.

## Définitions

Un arbre kd relaxé pour un ensemble d'étiquettes à K-dimensions est un arbre binaire dans lequel :

* Chaque nœud contient une donnée à K-dimensions et a, associé, un discriminant arbitraire j ∈ {0,1,...,K − 1}.
* Pour chaque nœud avec l'étiquette x et le discriminant j, l'invariant suivant est vrai : n'importe quelle donnée dans le sous-arbre droit avec l'étiquette y satisfait $y_j$ < $x_j$ et n'importe quelle donnée dans le sous-arbre gauche avec l'étiquette y satisfait $y_j$ ≥ $x_j.$

Si K=1, un arbre kd relaxé est un arbre binaire de recherche.

Comme dans un arbre kd, un arbre kd relaxé de taille n induit une partition du domaine D en n+1 régions, chacune correspondant à une feuille dans l'arbre kd. La zone de délimitation (ou délimitation du tableau) d'un nœud {x,j} est la région de l'espace délimitée par la feuille dans laquelle x tombe quand il est inséré dans l'arbre. Ainsi, la zone de délimitation de la racine {y,i} est $[0,1]^K,$ la zone de délimitation de la racine du sous-arbre-gauche est [0,1] × ... × $[0,y_i]$ × ... × [0,1], et ainsi de suite.

## Requêtes supportées

Le temps moyen des complexités dans un arbre kd relaxé avec n données sont :

* Requête de correspondance parfaite : O(log n)
* Requête de correspondance partielle : $O(n^{1−f(s/K)}),$ où :
   * s parmi K attributs sont spécifiés
   * avec 0 < f(s/K) < 1, une fonction à réelle valeur de s/K
* Requête de plus proches voisins : O(log n)
