Arbre de segments

En informatique, un arbre segment (en anglais segment tree), est un arbre enraciné pour stocker des intervalles ou des segments. Il permet des requêtes afin de savoir quels segments contiennent un certain point. C'est, en principe, une structure statique ; c'est une structure qui ne peut plus être modifiée une fois qu'elle est créée. Une structure de données similaire est l'arbre intervalle. Un arbre segment pour un ensemble I de n intervalles utilise un stockage de O(n log n) et peut être construit en un temps de O(n log n). Dans un arbre segment on peut rechercher tous les intervalles qui contiennent un certain point (la requête) en O(log n + k), où k est le nombre d'intervalles ou segments extraits. Les applications de l'arbre segment sont dans les domaines de la géométrie algorithmique et du système d'information géographique. L'arbre segment peut aussi être généralisé à des espaces avec des plus grandes dimensions. Cette section décrit la structure d'un arbre segment à 1 dimension. Soit S l'ensemble d'intervalles, ou segments. Soit p1, p2, ..., pm la liste des points d'extrémités d'intervalle distincts, trié de gauche à droite. On considère le partitionnement de la réelle ligne induite par ces points. Les régions de ce partitionnement sont nommés intervalles élémentaires. Ainsi, les intervalles élémentaires, sont de gauche à droite. Comme cela, la liste des intervalles élémentaires consistent à des intervalles ouverts entre deux points d'extrémités consécutifs pi et pi+1, alternés avec des intervalles fermés qui consistent en un seul point d'extrémité. Les points isolés sont traités comme des intervalles car la réponse à une requête n'est pas nécessairement la même à l'intérieur d'un intervalle élémentaire et ses points d'extrémités. vignette|upright=1.9|Exemple graphique de la structure d'un arbre segment. Cette instance est construite pour les segments montrés en bas.