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=(x0,... ,xK−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 yj < xj et n'importe quelle donnée dans le sous-arbre gauche avec l'étiquette y satisfait yj ≥ xj.
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,yi] × ... × [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(n1−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)
Références
Catégorie:Arbre (structure de données)