Arbre kd relaxé

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

1. Chaque nœud contient une donnée à K-dimensions et a, associé, un discriminant arbitraire j ∈ {0,1,...,K − 1}.
2. 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.[2]

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.

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)[3]