Voir la source de Arbre kd

{{double image verticale|right|Arbre kd noeuds espace.svg|Arbre kd noeuds arborescence.svg|290|Arbre 2-d correspondant à la partition de l’espace (à dimension 2) au-dessus.}}

[[Fichier:3dtree.png|vignette|Partition d'un espace à trois dimensions pour la construction d'un arbre 3-d.]]

En [[informatique]], un '''arbre ''k''-d''' (ou '''''k''-d tree''', pour k''-dimensional tree'') est une [[structure de données]] de partition de l'espace permettant de stocker des [[Point (géométrie)|points]], et de faire des recherches ([[recherche par plage]], [[Recherche des plus proches voisins|plus proche voisin]], etc.) plus rapidement qu'en parcourant linéairement le tableau de points. Les arbres ''k''-d sont des cas particuliers d'[[Partition binaire de l'espace|arbres BSP]] ''(binary space partition trees)''.

Cette structure a été proposée par [[Jon Louis Bentley]] de l'[[Université Stanford]] en 1975<ref>{{article
 | prénom1 = J. L. | nom1 = Bentley
 | titre = Multidimensional binary search trees used for associative searching
 | langue = en
 | périodique = Communications of the ACM
 | volume = 18 | numéro = 9
 | année = 1975
 | pages = 509-517
 | doi = 10.1145/361002.361007
}}</ref>.

== Description ==

Les arbres ''k''-d sont des [[arbre binaire|arbres binaires]], dans lesquels chaque nœud contient un point en dimension ''k''. Chaque nœud non terminal divise l'espace en deux demi-espaces. Les points situés dans chacun des deux demi-espaces sont stockés dans les branches gauche et droite du nœud courant. Par exemple, si un nœud donné divise l'espace selon un plan normal à la direction (O''x''), tous les points de coordonnée ''x'' inférieure à la coordonnée du point associé au nœud seront stockés dans la branche gauche du nœud. De manière similaire, les points de coordonnée ''x'' supérieure à celle du point considéré seront stockés dans la branche droite du nœud.

== Construction ==

Il y a plusieurs possibilités de construction d'arbres ''k''-d. La construction standard se fait en suivant ces deux conditions :
* la direction de l'hyperplan est choisie en fonction de la hauteur du point dans l'arbre ; pour un arbre ''k''-d en dimension 3, le plan de la racine sera par exemple normal au vecteur (1,0,0), le plan des deux enfants sera normal au vecteur (0,1,0), celui des petits-enfants sera normal au vecteur (0,0,1), puis à nouveau normal au vecteur (1,0,0), et ainsi de suite… 
* afin d'avoir un [[arbre équilibré]], le point inséré dans l'arbre à chaque étape est celui qui a la coordonnée [[Médiane (statistiques)|médiane]] dans la direction considérée.

La contrainte sur la sélection du point médian n'est pas une obligation, mais permet de s'assurer que l'arbre sera équilibré. Le tri des points à chaque étape a un coût en temps, ce qui peut amener à un temps de création de l'arbre assez long. Il est possible de prendre la médiane d'un nombre fixé de points choisis aléatoirement pour le prochain point à insérer, ce qui donne en général un arbre globalement équilibré.

À partir d'une liste de ''n'' points, l'algorithme suivant construit un arbre ''k''-d équilibré :
 
 '''fonction''' kdtree(listePoints, profondeur)
     '''si''' la liste listePoints '''est vide'''
         '''retourner l'arbre vide'''
 
     ''// Sélectionne l'axe de comparaison en fonction de la profondeur du nœud''
     axe := profondeur '''mod''' k;
 
     ''// trie la liste de points et sélectionne le point médian''
     '''sélectionner''' pointMédian selon l'axe dans la liste listePoints
 
     ''// Crée le nœud courant, et construit récursivement les deux fils''
     nœud := nouveau nœud 
     nœud.point := pointMédian;
     node.filsGauche := kdtree(points '''dans''' listePoints '''avant''' pointMédian, profondeur+1);
     node.filsDroit := kdtree(points '''dans''' listePoints '''après''' pointMédian, profondeur+1);
     '''return''' node;

La [[complexité en temps|complexité algorithmique]] de construction d'un arbre ''k''-d est de O(''n'' log<sup>2</sup> ''n'') si un algorithme médian de complexité O(''n'' log ''n'') est utilisé. Si on utilise un algorithme de calcul de la médiane de complexité linéaire (en O(''n'')), alors la construction de l'arbre a une complexité en O(''n'' log ''n'').

Le choix de la méthode de sélection de l'hyperplan de coupe a une grande influence sur l'efficacité de l'algorithme de recherche du plus proche voisin<ref name = "MM99">{{article
 | langue = en
 | titre = It's okay to be skinny, if your friends are fat
 | prénom1 = Songrit | nom1 = Maneewongvatana
 | prénom2 = David M. | nom2 = Mount
 | périodique = 4th Annual CGC Workshop on Computational Geometry
 | année = 1999
 | lire en ligne = http://www.cs.umd.edu/~mount/Papers/cgc99-smpack.pdf
 | format = pdf
}}</ref>. La méthode standard présentée ci-dessus (utilisation du point médian) peut donner des cellules très minces selon une dimension ; lors d'une recherche de plus proche voisin, on peut donc avoir de nombreuses cellules dans la boule de recherche<ref>Pour un point <math>C(c_1, c_2, ..., c_n)</math> et un rayon <math>R</math> donnés, et pour une [[Norme (mathématiques)|norme L<sub>''m''</sub>]] choisie, la boule de recherche est l'ensemble des points <math>X(x_1, x_2, ..., x_n)</math> vérifiant <math>\left ( \sum_{i = 1}^n (x_i - c_i)^m \right )^{1/m}\leq R</math>; si ''m'' = 2 (norme euclidienne), la boule de recherche est l'[[hypersphère]]</ref>, ce qui oblige à visiter de nombreuses branches de l'arbre. Si à l'inverse on utilise le point milieu (milieu géométrique, l'hyperplan coupant l'hypercube en deux parties égales), on obtient des cellules « épaisses », c'est-à-dire dont le rapport entre la dimension la plus grande et la plus petite est au pire de 2:1, la boule de recherche recouvre donc un nombre limité de cellules ; mais de nombreuses cellules peuvent être vides, ce qui amène à effectuer des recherches dans des zones vides.

Maneewongvatana et Mount<ref name = "MM99"/> proposent la méthode du point milieu glissant, qui peut générer des cellules minces, mais entourées de cellules grasses, et aucune cellule vide ; il garantit donc une bonne efficacité de l'algorithme de recherche. Cette méthode consiste à prendre en première intention le point milieu ; si tous les points se trouvent du même côté de l'hyperplan (donc si une cellule est vide), on fait glisser le point générant l'hyperplan jusqu'à rencontrer un point de l'ensemble. Une cellule contient alors au moins un point. L'arbre ainsi généré n'est pas nécessairement équilibré.

== Alternative ==

{{double image verticale|right|Arbre kd feuilles espace.svg|Arbre kd feuilles arborescence.svg|290|Arbre 2-d dans lequel les points sont aux feuilles.}}

On peut également construire un arbre ''k''-d dans lequel les points sont les feuilles de l'arbre<ref>{{article
 | langue = en
 | titre = Orthogonal Range Searching
 | périodique = Computational Geometry
 | année = 2008
 | éditeur = Springer
 | page = 95-120
 | doi = 10.1007/978-3-540-77974-2_5
 | isbn = 978-3-540-77973-5
 | isbn2 = 978-3-540-77974-2
}}</ref>.

== Notes et références ==

{{références}}

== Voir aussi ==
===Articles connexes===
* [[Arbre kd relaxé]]
* [[Octree]]
* [[Quadtree]]
* [[Partition binaire de l'espace]]
* [[Recherche des plus proches voisins]]

{{Palette|Arbres informatiques}}
{{Portail|informatique théorique}}

[[Catégorie:Arbre (structure de données)]]
[[Catégorie:Géométrie algorithmique]]