Arbre d'intervalles
En informatique, un arbre intervalle (en anglais interval tree), est un arbre enracinĂ© pour stocker des intervalles. ParticuliĂšrement, il permet de retrouver efficacement tous les intervalles qui chevauchent un certain intervalle ou point. Cette structure de donnĂ©es est souvent utilisĂ©e pour les requĂȘtes dites de fenĂȘtres, par exemple, pour trouver toutes les routes dans un espace rectangulaire sur une carte numĂ©rique, ou pour trouver tous les Ă©lĂ©ments visibles dans un espace Ă 3 dimensions. Une structure de donnĂ©es similaire est l'arbre segment.
Une solution triviale est de visiter chaque intervalle et de tester s'il intersecte le point ou intervalle donnĂ©, cela requiert un temps O(n), oĂč n est le nombre d'intervalles dans l'ensemble. Etant donnĂ© qu'une requĂȘte doit retourner tous les intervalles, par exemple si la requĂȘte est un large intervalle intersectant tous les intervalles de l'ensemble, cela est asymptotiquement optimal. Cependant on peut faire mieux en considĂ©rant les algorithmes qui dĂ©pendent de la taille de l'entrĂ©e, oĂč le temps dâexĂ©cution est exprimĂ© en fonction de m, le nombre d'intervalles produits par la requĂȘte. Les arbres intervalle ont un temps de requĂȘte en O(log n + m) et un temps initial de crĂ©ation en O(n log n), en limitant la consommation de la mĂ©moire Ă O(n). AprĂšs la crĂ©ation, les arbres intervalle peuvent ĂȘtre dynamiques, permettant une efficace insertion et suppression d'un intervalle en O(log n). Si les points d'extrĂ©mitĂ©s sont dans une petite plage d'entiers (e.g., dans la plage [1,...,O(n)]), des structures de donnĂ©es plus rapides existent avec un temps de prĂ©traitement de O(n) et un temps de requĂȘte de O(1+m) pour signaler m intervalles contenant a un certain point d'une requĂȘte.
Approche naĂŻve
Dans un cas simple, les intervalles ne se chevauchent pas et peuvent ĂȘtre insĂ©rĂ©s dans un simple arbre binaire de recherche et effectuer les requĂȘtes en un temps de O(log n). Cependant, avec certains intervalles qui se chevauchent, il n'y a aucune maniĂšre de comparer deux intervalles pour l'insertion dans l'arbre puisque les tris en fonction des points de dĂ©buts ou de fins peuvent ĂȘtre diffĂ©rents. Une approche naĂŻve serait de construire deux arbres parallĂšles, un triĂ© en fonction des points de dĂ©but, et l'autre par les points de fin de chaque intervalle. Cela permet de se dĂ©barrasser de la moitiĂ© de chaque arbre en un temps de O(log n), mais les rĂ©sultats doivent ĂȘtre mĂ©langĂ©s, ce qui requiert un temps O(n). Cela nous donne des requĂȘtes en O(n + log n) = O(n), ce qui n'est pas meilleur que la recherche par force brute.
Les arbres intervalle résolvent ce problÚme. Cet article décrit deux concepts différents pour un arbre intervalle, appelés arbre intervalle centré et arbre augmenté.
Arbre intervalle centré
Les requĂȘtes requiĂšrent un temps O(log n + m), oĂč n est le nombre total d'intervalles et m est le nombre de rĂ©sultats signalĂ©s. La construction nĂ©cessite un temps O(n log n) et un espace O(n).
Construction
Ătant donnĂ© un ensemble n d'intervalles sur une suite de nombres, on veut construire une structure de donnĂ©es de telle maniĂšre qu'on puisse retrouver efficacement tous les intervalles qui chevauchent un autre intervalle ou point.
On commence par prendre la plage entiÚre de tous les intervalles et en la divisant en deux moitiés au centre_x (en pratique, centre_x devrait choisi de maniÚre à garder l'arbre relativement équilibré). Cela donne trois ensemble d'intervalles, ceux complÚtement à gauche du centre_x qu'on appellera S_gauche, ceux complÚtement à droite du centre_x qu'on appellera S_droite, and ceux qui chevauchent le centre_x qu'on appellera S_centre.
Les intervalles dans S_gauche et S_droite sont rĂ©cursivement divisĂ©s de la mĂȘme maniĂšre jusqu'Ă ce qu'il n'y ait plus d'intervalles.
Les intervalles dans S_centre qui chevauchent le point central sont stockĂ©s dans une structure de donnĂ©es sĂ©parĂ© qui est liĂ©e au nĆud dans l'arbre intervalle. Cette structure de donnĂ©es consiste en deux listes, une contenant l'ensemble des intervalles triĂ©s par leurs points de dĂ©but, et l'autre contenant l'ensemble des intervalles triĂ©s par leurs points de fin.
Le rĂ©sultat est un arbre ternaire avec chaque nĆud qui stocke :
- Un point central
- Un pointeur vers un autre nĆud qui contient tous les intervalles de l'extrĂ©mitĂ© gauche jusqu'au point central
- Un pointeur vers un autre nĆud qui contient tous les intervalles de l'extrĂ©mitĂ© droite jusqu'au point central
- Tous les intervalles qui chevauchent le point central, triés par leurs points de début
- Tous les intervalles qui chevauchent le point central, triés par leurs points de fin
Intersection
Ătant donnĂ© la structure de donnĂ©es ci-dessus, on a des requĂȘtes qui consistant Ă des zones ou des points, et on retourne toutes les zones dans l'ensemble original qui chevauchent cette entrĂ©e.
Avec un point
Le but est de trouver tous les intervalles dans l'arbre qui chevauchent un certain point x. L'arbre est parcouru avec un algorithme rĂ©cursif similaire Ă ce qu'on pourrait utiliser dans un arbre binaire traditionnel, mais avec une affordance supplĂ©mentaire pour les intervalles qui chevauchent le point "central" de chaque nĆud.
Pour chaque nĆud de l'arbre, x est comparĂ© Ă centre_x, le point central utilisĂ© dans la construction des nĆuds ci-dessus. Si x est infĂ©rieur que centre_x, l'ensemble des intervalles le plus Ă gauche, S_gauche, est considĂ©rĂ©. Si x est plus grand que x_centre, l'ensemble d'intervalles le plus Ă droite, S_droite, est considĂ©rĂ©.
Comme chaque nĆud est traitĂ© quand on traverse l'arbre depuis la racine vers une feuille, la portĂ©e dans S_centre est traitĂ©e. Si x est infĂ©rieur que centre_x, on sait que tous les intervalles dans S_centre se terminent aprĂšs x, ou il ne pourraient pas aussi chevaucher x_centre. Par consĂ©quent, on a seulement besoin de trouver les intervalles dans S_centre qui dĂ©butent avant x. On peut consulter les listes de S_centre qui ont dĂ©jĂ construites. Etant donnĂ© que l'on s'intĂ©resse uniquement aux dĂ©buts des intervalles dans ce scĂ©nario, on peut consulter la liste qui est triĂ©e par les dĂ©buts. Supposons qu'on trouve le nombre le plus grand et le plus proche de x sans le dĂ©passer dans cette liste. Toutes les plages depuis le dĂ©but de la liste par rapport au point trouvĂ© chevauche x car elles dĂ©butent avant x et finissent aprĂšs x (car nous savons qu'elles chevauchent centre_x qui est plus grand que x). Ainsi, on va simplement commencer par Ă©numĂ©rer les intervalles dans la liste jusqu'Ă ce que le point de dĂ©part dĂ©passe x.
De mĂȘme, si x est plus grand que centre_x, on sait que tous les intervalles dans S_centre doivent dĂ©marre avant x, donc on trouve ces intervalles qui finissent aprĂšs x en utilisant la liste triĂ©e par la fin des intervalles.
Si x correspond exactement Ă centre_x, tous les intervalles dans S_centre peuvent ĂȘtre ajoutĂ©s aux rĂ©sultats sans autres traitements et le parcours de l'arbre peut ĂȘtre arrĂȘtĂ©.
Avec un intervalle
Pour avoir comme rĂ©sultat un intervalle r qui intersecte notre intervalle de requĂȘte q un des points suivants doit s'avĂ©rer :
- le point de début et/ou de fin de r est dans q ; ou
- r renferme complĂštement q.
En premier on trouve tous les intervalles avec les points de dĂ©but et/ou de fin dans q en utilisant un arbre construit sĂ©parĂ©ment. Dans le cas unidimensionnel, on peut utiliser un arbre de recherche contenant tous les points de dĂ©but et de fin de l'ensemble des intervalles, chacun avec un pointeur vers son intervalle correspondant. Une recherche binaire en un temps O(log n) pour le dĂ©but et la fin de q rĂ©vĂšle les points minimum et maximum Ă considĂ©rer. Chaque point avec ses plages de rĂ©fĂ©rences (un intervalle qui chevauche q) est ajoutĂ© Ă la liste des rĂ©sultats. Une attention doit ĂȘtre apportĂ©e afin d'Ă©viter les doublons, Ă©tant donnĂ© qu'un intervalle peut Ă la fois ĂȘtre au dĂ©but et Ă la fin de q. Cela peut ĂȘtre effectuĂ© un utilisant un marqueur binaire sur chaque intervalle afin de signaler s'il a dĂ©jĂ Ă©tĂ© ajoutĂ© Ă l'ensemble des rĂ©sultats.
Enfin, on doit trouver les intervalles qui renferment q. Afin de les trouver, on choisit n'importe quel point à l'intérieur de q et on utilise l'algorithme ci-dessus afin de trouver tous les intervalles qui l'intersectent (de nouveau, faire attention à enlever les doublons).
Dimensions plus grande
La structure de donnĂ©es arbre intervalle peut ĂȘtre gĂ©nĂ©ralisĂ©e pour une dimension plus grande N avec des requĂȘtes similaires; un mĂȘme temps de construction et un stockage en O(n log n).
PremiĂšrement, un arbre de portĂ©e en N dimensions est construit, ce qui permet de retrouver efficacement tous les Ă©lĂ©ments dont les points de dĂ©but et de fin sont Ă l'intĂ©rieur de la rĂ©gion R de la requĂȘte. Une fois que les zones correspondantes sont trouvĂ©es, la derniĂšre chose qui reste est les zones qui recouvrent la rĂ©gion dans certains dimensions. Afin de trouver ces recouvrements, n arbres intervalle sont crĂ©Ă©s, et un axe intersectant R est interrogĂ© pour chaque. Par exemple, en deux dimensions, le bas du carrĂ© R (ou toute autre ligne horizontale intersectant R) sera interrogĂ© contre l'arbre d'intervalle construit sur l'axe horizontal. De mĂȘme, la gauche (ou tout autre ligne verticale intersectant R) sera interrogĂ© contre l'arbre d'intervalle construit sur l'axe vertical.
Chaque arbre intervalle a aussi besoin d'une addition pour les dimensions plus grandes. Pour chaque nĆud que l'on traverse dans l'arbre, x est comparĂ© avec S_centre pour trouver les chevauchements. Au lieu de deux listes de points triĂ©s que nous avons utilisĂ© dans le cas unidimensionnel, a arbre de portĂ©e est construit. Cela permet de retrouver efficacement tous les points dans S_centre qui chevauchent la rĂ©gion R.
Suppression
Si aprĂšs avoir supprimĂ© un intervalle de l'arbre, le nĆud contenant cet intervalle n'en contient plus, ce nĆud pourrait ĂȘtre supprimĂ© de l'arbre. Ceci est plus compliquĂ© qu'une simple opĂ©ration de suppression dans un arbre binaire.
Un intervalle peut chevaucher le point central de plusieurs nĆuds dans l'arbre. Ătant donnĂ© que chaque nĆud stocke les intervalles qui le chevauchent, tous les intervalles complĂštement Ă gauche de son point central dans le sous-arbre gauche, similaire pour le sous-arbre droit, il survient que chaque intervalle est stockĂ© dans le nĆud le plus proche de la racine Ă partir de l'ensemble de nĆuds qui ont un point central qui est chevauchĂ©.
La suppression normale dans un arbre binaire (dans le cas oĂč le nĆud supprimĂ© a deux fils) implique de promouvoir un nĆud qui Ă©tait une feuille Ă venir Ă la place du nĆud qui est supprimĂ© (usuellement le fils le plus Ă gauche du sous-arbre droit, ou le fils le plus Ă droite du sous-arbre gauche).
![](https://img.franco.wiki/i/Binary_search_tree_delete.svg.png.webp)
Comme rĂ©sultat de cette promotion, certains nĆuds qui Ă©taient au-dessus du nĆud promu vont devenir ses descendants. Il est nĂ©cessaire de chercher ces nĆuds pour les intervalles qui chevauchent aussi le nĆud promu, et dĂ©placer ces intervalles dans le nĆud promu. Comme consĂ©quence, cela peut amener Ă de nouveaux nĆuds vides, qui devront ĂȘtre supprimĂ©s, en suivant Ă nouveau le mĂȘme algorithme.
Ăquilibrage
Le mĂȘme problĂšme qui affecte la suppression affecte aussi les opĂ©rations de rotations. La rotation doit prĂ©server l'invariant qui dit que chaque nĆud doit ĂȘtre aussi proche que possible de la racine.
Arbre augmenté
A la fois l'insertion et la suppression requiert un temps O(log n), avec n étant le nombre total d'intervalles dans l'arbre avant l'opération d'insertion ou de suppression.
Un arbre augmentĂ© peut ĂȘtre construit Ă partir d'un simple arbre triĂ©, par exemple un arbre binaire de recherche ou un arbre Ă©quilibrĂ©, triĂ© par les valeurs basses des intervalles. Une extra annotation est ajoutĂ©e Ă chaque nĆud, mĂ©morisant la plus haute valeur de tous les intervalles Ă partir de ce nĆud? Maintenir cet attribut implique de mettre Ă jour tous les ancĂȘtres de ce nĆud de bas en haut Ă chaque fois qu'un nĆud est ajoutĂ© ou supprimĂ©. Cela prend seulement O(h) Ă©tape par nĆud, addition ou suppression, oĂč h est la hauteur du nĆud ajoutĂ© ou supprimĂ© dans l'arbre. S'il y a des rotations de l'arbre pendant l'insertion ou la suppression, les nĆuds affectĂ©s doivent aussi ĂȘtre mis Ă jour.
Maintenant, i est connu que deux intervalles A et B se chevauchent uniquement quand Ă la fois A.min †B.max et A.max â„ B.min. En cherchant dans les arbres les nĆuds qui chevauchent un certain intervalle, vous pouvez immĂ©diatement sauter :
- tous les nĆuds Ă la droite des nĆuds dont la valeur minimale dĂ©passe la fin de l'intervalle donnĂ©.
- tous les nĆuds qui ont leur valeur maximale en dessous du dĂ©but de l'intervalle donnĂ©.
RequĂȘtes d'appartenance
Des performances peuvent ĂȘtre gagnĂ©es si l'arbre Ă©vite des traversĂ©es inutiles. Cela peut se produire en ajoutant des intervalles qui existent dĂ©jĂ ou en supprimant des intervalles qui n'existent pas.
Un ordre total peut ĂȘtre dĂ©fini sur les intervalles en les ordonnant en premier sur leurs bornes minimales et ensuite sur leurs bornes maximales. Ensuite, une vĂ©rification d'appartenant peut ĂȘtre effectuĂ©e en un temps O(log n), contre O(k + log n) pour trouver les doublons si k intervalles chevauchent l'intervalle qui doit ĂȘtre insĂ©rĂ© ou supprimĂ©. Cette solution a l'avantage de ne pas nĂ©cessitĂ© de structures additionnelles. Le changement est simplement algorithmique. Le dĂ©savantage est que la requĂȘte d'appartenant prend un temps O(log n).
Alternativement, au taux de O(n) mĂ©moire, les requĂȘtes d'appartenance peuvent ĂȘtre implĂ©mentĂ©es avec une table de hachage, mis Ă jour en mĂȘme temps que l'arbre intervalle. Cela ne nĂ©cessite pas forcĂ©ment le double de la mĂ©moire requise, si les intervalles sont stockĂ©s par rĂ©fĂ©rence et non pas par valeur.
Exemple en Java : Ajout d'un nouvel intervalle dans l'arbre
L'Ă©tiquette de chaque nĆud est l'intervalle lui-mĂȘme, par consĂ©quent les nĆuds sont triĂ©s d'abord par valeur minimale puis par valeur maximale, et la valeur de chaque nĆud est l'extrĂ©mitĂ© de l'intervalle :
public void add(Interval i) {
put(i, i.getEnd());
}
Exemple en Java : Recherche d'un point ou d'un intervalle dans l'arbre
Pour la recherche d'un intervalle, on parcourt l'arbre, en utilisant l'Ă©tiquette (n.getKey()
) et la valeur maximale (n.getValue()
) pour omettre les branches qui ne peuvent pas chevaucher la requĂȘte. Le cas le plus simple est la requĂȘte d'un point :
// Recherche de tous les intervalles contenant "p", démarrant avec le
// nĆud "n" et ajout des correspondances d'intervalles Ă la liste "result"
public void search(IntervalNode n, Point p, List<Interval> result) {
// Ne pas chercher des nĆuds qui n'existent pas
if (n == null)
return;
// Si p est Ă droite du point le plus Ă droite que n'importe quel intervalle
// dans ce nĆud et tous les fils, il n'y aura pas de correspondance
if (p.compareTo(n.getValue()) > 0)
return;
// Recherche du fils gauche
if (n.getLeft() != null)
search(IntervalNode (n.getLeft()), p, result);
// VĂ©rifier ce nĆud
if (n.getKey().contains(p))
result.add(n.getKey());
// Si p est à gauche du début de cet intervalle,
// alors il ne peut pas ĂȘtre dans n'importe quel fils Ă droite
if (p.compareTo(n.getKey().getStart()) < 0)
return;
// Sinon, rechercher dans le fils droit
if (n.getRight() != null)
search(IntervalNode (n.getRight()), p, result);
}
oĂč
a.compareTo(b)
retourne une valeur négative si a < ba.compareTo(b)
retourne zéro si a = ba.compareTo(b)
retourne une valeur positive si a > b
Le code pour chercher un intervalle est similaire, excepté pour la vérification au milieu :
// VĂ©rifier ce nĆud
if (n.getKey().overlapsWith(i))
result.add (n.getKey());
overlapsWith() est défini comme ceci :
public boolean overlapsWith(Interval other) {
return start.compareTo(other.getEnd()) <= 0 &&
end.compareTo(other.getStart()) >= 0;
}
Dimensions plus grande
Les arbres augmentĂ©es peuvent ĂȘtre Ă©tendus Ă de plus grandes dimensions en parcourant les dimensions Ă chaque niveau de l'arbre . Par exemple, pour deux dimensions, les niveaux impairs de l'arbre peuvent contenir les zones pour la coordonnĂ©e-x, pendant que les niveaux pairs contiennent les zones pour la coordonnĂ©e-y. Cette convertit effectivement la structure de donnĂ©es d'un arbre binaire augmentĂ© Ă un arbre kd augmentĂ©, ce qui, par consĂ©quent, complique significativement les algorithmes d'Ă©quilibrage pour les insertions et les suppressions.
Une solution plus simple est d'utiliser des arbres intervalle imbriquĂ©s. PremiĂšrement, crĂ©er un arbre en utilisant les zones pour la coordonnĂ©e-y. Maintenant, pour chaque nĆud dans l'arbre, ajouter un autre arbre intervalle sur les zones-x, pour tous les Ă©lĂ©ments qui ont la mĂȘme zone-y que celle du nĆud.
L'avantage de cette solution est qu'elle peut ĂȘtre Ă©tendu Ă un nombre de dimension arbitraire en utilisant le mĂȘme code de base.
Au dĂ©but, le coĂ»t additionnel des arbres intervalle imbriquĂ©s peut sembler prohibitif, mais ce n'est gĂ©nĂ©ralement pas le cas. Comme pour la solution prĂ©cĂ©dente pour les non-imbriquĂ©s, un nĆud est nĂ©cessaire par coordonnĂ©e-x, amenant le mĂȘme nombre de nĆuds pour les deux solutions. Le seul surcoĂ»t additionnel est les structures de l'arbre imbriquĂ©, une par intervalle vertical. Cette structure est usuellement de taille nĂ©gligeable, consistant uniquement en un pointeur vers la racine du nĆud, et possiblement le nombre de nĆuds et la profondeur de l'arbre.
Arbre axé sur le médian ou la longueur
Un arbre axĂ© sur le mĂ©dian ou la longueur est similaire Ă un arbre augmentĂ©, mais symĂ©trique, avec l'arbre binaire de recherche triĂ© par le mĂ©dian des points des intervalles. Il y a tas binaire orientĂ© vers le maximum dans chaque nĆud, triĂ© par la longueur de l'intervalle (ou la moitiĂ© de la longueur). Aussi on stocke la possible minimum et le maximum valeur du sous-arbre dans chaque nĆud (ainsi la symĂ©trie).
Test de chevauchement
En utilisant seulement les valeurs de dĂ©but et de fin de deux intervalles , pour , le test de chevauchement peut ĂȘtre effectuĂ© comme ceci :
et
Cela peut ĂȘtre simplifiĂ© en utilisant la somme et la diffĂ©rence :
Ce qui réduit le test de chevauchement à :
Ajout d'intervalle
Ajouter de nouveaux intervalles dans l'arbre est pareil que pour un arbre binaire de recherche en utilisant la valeur mĂ©diane comme Ă©tiquette. On pousse dans le tas binaire associĂ© avec le , et on met Ă jour la valeur minimum et maximum possible associĂ©e avec tous les nĆuds au-dessus.
Recherche pour tous les intervalles qui se chevauchent
Utilisons pour la requĂȘte d'intervalle, et pour l'Ă©tiquette d'un nĆud (comparĂ© Ă d'intervalles).
On commence avec le nĆud racine, dans chaque nĆud, on vĂ©rifie en premier s'il est possible que notre requĂȘte d'intervalle se chevauche avec le nĆud du sous-arbre en utilisant les valeurs minimales et maximales du nĆud (si cela ne l'est pas, on ne continue pas pour ce nĆud).
Ensuite on calcule pour les intervalles dans ce nĆud (pas ses fils) qui chevauchent avec l'intervalle de la requĂȘte (en sachant ) :
et on effectue une requĂȘte sur son tas binaire pour le plus grand que .
Ensuite on passe Ă travers les files gauche et droite du nĆud, en faisant la mĂȘme chose. Dans le pire des cas, nous devons scanner tous les nĆuds de l'arbre binaire de recherche, mais Ă©tant donnĂ© que la requĂȘte sur un tas binaire est optimale, ceci est acceptable (un problĂšme Ă 2 dimensions ne peut pas ĂȘtre optimal dans les deux dimensions).
Cet algorithme est attendu pour ĂȘtre plus rapide qu'un traditionnel arbre intervalle (arbre augmentĂ©) pour les opĂ©rations de recherche. Ajouter un Ă©lĂ©ment est un peu plus lent en pratique, car l'ordre de croissance est le mĂȘme.
Bibliographie
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Computational Geometry, Second Revised Edition. Springer-Verlag 2000. Section 10.1: Interval Trees, p. 212â217.
- Franco P. Preparata, Michael Ian Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985
- Jens M. Schmidt, Interval Stabbing Problems in Small Integer Ranges, DOI. ISAAC'09, 2009
Références
Liens externes
- CGAL : Computational Geometry Algorithms Library in C++ contains a robust implementation of Range Trees
- IntervalTree (Python) - a centered interval tree with AVL balancing, compatible with tagged intervals
- Interval Tree (C#) - an augmented interval tree, with AVL balancing
- Interval Tree (Ruby) - an immutable, augmented interval tree, compatible with tagged intervals
- IntervalTree (Java) - an augmented interval tree, with AVL balancing, supporting overlap, find, Collection interface, id-associated intervals