Arbre kd

Carte Commune · n° 281043

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 points, et de faire des recherches (recherche par plage, plus proche voisin, etc.) plus rapidement qu'en parcourant linéairement le tableau de points. Les arbres k-d sont des cas particuliers d'arbres BSP (binary space partition trees). Cette structure a été proposée par Jon Louis Bentley de l'Université Stanford en 1975.

Lire sur Wikipédia · Image Christophe Dang Ngoc Chan (Cdang (d)), CC BY-SA 3.0