Arbre kd

Un arbre kd (ou kd-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 kd sont des cas particuliers d'arbres BSP (Binary Space Partition Trees).

Description

Les arbres kd sont des 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 (Ox), 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 kd. 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 kd-tree 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 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 sélectionner aléatoirement 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 kd équilibré:

function kdtree (liste de points pointList, int depth)
{
    if pointList is empty
        return nil;
    else
    {
        // Sélectionne l'axe de comparaison en fonction de la profondeur du nœud
        var int axis := depth mod k;

        // trie la liste de points et sélectionne le point médian
        select median by axis from pointList;

        // Crée le noeud courant, et construit récursivement les deux fils
        var tree_node node;
        node.location := median;
        node.leftChild := kdtree(points in pointList before median, depth+1);
        node.rightChild := kdtree(points in pointList after median, depth+1);
        return node;
    }
}

La complexité algorithmique de construction d'un arbre kd est de O(n log^2 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).

Voir aussi

• Octree
• Quadtree
• Binary space partitioning
• Recherche des plus proches voisins

• Portail de l’algorithmique