Arbre de portée

En informatique, un arbre de portée, en anglais range tree, est un arbre enraciné qui sert de structure de données pour stocker une liste de points. Il permet de trouver efficacement tous les points à une certaine distance d'un autre point, et typiquement utilisé pour deux dimensions ou plus. Les arbres de portée ont été introduits par Jon Louis Bentley en 1979^[1]. Des structures de données similaires ont été indépendamment découvertes par Lueker^[2], Lee and Wong^[3], et Willard^[4]. L'arbre de portée est une alternative à l'arbre kd. Par rapport aux arbres kd, l'arbre de portée offre des requêtes plus rapides en ${\displaystyle O(\log ^{d}n+k)}$ mais un stockage pire en ${\displaystyle O(n\log ^{d-1}n)}$, où n est le nombre de points stockés dans l'arbre, d la dimension de chaque point et k le nombre de points signalé par une certaine requête.

Bernard Chazelle a amélioré ce temps de requête en ${\displaystyle O(\log ^{d-1}n+k)}$ et la complexité spatiale en ${\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}$^[5],[6].

Description

Exemple d'un arbre de portée à 1 dimension.

Un arbre de portée avec un ensemble de points à 1 dimension est un arbre binaire de recherche équilibré en ces points. Les points stockés dans l'arbre sont stockés dans les feuilles de l'arbre ; chaque nœud interne stocke la plus grande valeur contenue dans son sous-arbre gauche. Un arbre de portée sur un ensemble de points en d dimensions est un arbre binaire de recherche à plusieurs niveaux récursivement défini. Chaque niveau de la structure de données est un arbre binaire de recherche sur l'une des d dimensions. Le premier niveau est un arbre binaire de recherche sur la première des d coordonnées. Chaque sommet v de cet arbre contient une structure associée qui est un arbre de portée (d-1) dimensionnel sur la dernière (d-1) coordonnée des points stockés dans le sous-arbre de v.

Opérations

Construction

Un arbre de portée à 1 dimension d'un ensemble de n points est un arbre binaire de recherche, qui peut être construit en une complexité en temps de O(n log n)). Les arbres de portée de dimensions plus grandes sont construits récursivement en construisant un arbre binaire de recherche équilibré sur la première coordonnée des points, et ensuite, pour chaque sommet v dans cet arbre, en construisant un arbre de portée à (d-1) dimensions sur les points contenus dans le sous-arbre de v. Construire un arbre de portée de cette façon requiert un temps en O(nlog^dn)).

Cela peut être amélioré en remarquant qu'un arbre de portée sur un ensemble de points à 2 dimensions peut être construit en temps O(n log n)^[7]. Soit S l'ensemble de n points à 2 dimensions. Si S contient seulement un point, retourner une feuille contenant ce point. Sinon, construire la structure associée de S, un arbre de portée de 1 dimension sur la coordonnée y' des points dans S. Soit x_m la médiane de la coordonnée x des points. Soit 'S_L l'ensemble des points avec la coordonnée x inférieure ou égale à x_m et soit S_R l'ensemble des points avec la coordonnée x supérieure à x_m. Construire récursivement v_L, un arbre de portée à 2 dimensions sur S_L, et v_R, un arbre de portée à 2 dimensions sur S_R. Créer un sommet v avec pour enfant à gauche v_L et à droite v_R. Si on trie les points par leurs coordonnées y au début de l'algorithme, et en maintenant cet ordre quand on coupe les points par leurs coordonnées x, on peut construire la structure associée à chaque sous-arbre en temps linéaire. Cela réduit le temps pour construire un arbre de portée à 2 dimensions à O(n log n), ce qui réduit aussi le temps pour construire un arbre de portée à d dimensions à O(n log^d−1n).

Requête de distance

Une requête de distance à 1 dimension [x₁, x₂]. Les points stockés dans les sous-arbres gris seront signalés. Trouver (x₁) et trouver (x₂) sera signalé s'ils sont à l'intérieur des bornes de la requête.

Les arbres de portée peuvent être utilisés pour trouver un ensemble de points qui se situent à un intervalle donné. Pour signaler les points dans l'intervalle [x₁, x₂], on commence par chercher x₁ et x₂. À certains sommets dans l'arbre, le chemin de recherche pour x₁ et x₂ va diverger. Soit v_split le dernier sommet que ces deux chemins de recherche ont en commun. On continue à chercher pour x₁ dans l'arbre de portée. Pour chaque sommet v dans le chemin de recherche depuis v_split à x₁, si la valeur stockée à v est plus grande que x₁, on signale chaque point dans le sous-arbre droit de v. Si v est une feuille, on signale la valeur stockée sur v si c'est à l'intérieur de l'intervalle de la requête. Similairement, on signale tous les points stockés dans le sous-arbre gauches avec les sommets qui ont une valeur inférieure à x₂ tout au long du chemin de recherche de v_split à x₂, et on signale la feuille de ce chemin si elle est à l'intérieur de l'intervalle de la requête.

Étant donné que l'arbre de portée est un arbre binaire équilibré, le chemin de recherche de x₁ et x₂ a une longueur de O(log n). Signaler tous les points stockés dans le sous-arbre d'un sommet peut être effectué en temps linéaire en utilisant un algorithme de parcours d'arbre. Ainsi le temps pour effectuer une requête de distance est O(log n + k), où k est le nombre de points dans l'intervalle de la requête.

Les requêtes de distance sont similaires dans d dimensions. Au lieu de signaler tous les points stockés dans les sous-arbres des chemins de recherche, on effectue une requête de distance à (d-1) dimensions sur la structure associée à chaque sous-arbre. Finalement, une requête de distance à 1 dimension va être effectuée et les points corrects vont être signalés.

De même, les requêtes de distance à 2 dimensions peuvent être effectuées. Un arbre binaire dans la coordonnée est nécessaire, où chaque nœud est augmenté avec un sous-arbre dans la coordonnée y qui contient tous les points descendants. Trivialement, cette structure de données peut être calculée en un temps de O(nlog²n) qui peut être optimisé en O(nlogn). Étant donné qu'on augmente chaque nœud avec un sous-arbre, la complexité de l'espace requis de cette structure de données est O(nlogn). La complexité en temps de chaque requête sera O(log²n).

Étant donné qu'une requête à d dimensions consiste en des requêtes de distance à O(log n) (d−1)dimensions , il survient que le temps pour effectuer une requête de distance à d dimensions est O(log^dn + k), où k est le nombre de points dans l'intervalle de la requête. Cela peut être réduit à O(log^d−1n + k) en utilisant la technique de cascade fractionnée^[2],[4],[7].

Voir aussi

• Arbre kd
• Segment tree

Références

1. (en) J. L. Bentley, « Decomposable searching problems », Information Processing Letters, vol. 8, n^o 5,‎ 1979, p. 244–251 (DOI 10.1016/0020-0190(79)90117-0)
2. (en) G. S. Lueker, 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), 1978, 28–21 p. (DOI 10.1109/SFCS.1978.1), « A data structure for orthogonal range queries »
3. (en) D. T. Lee et C. K. Wong, « Quintary trees: A file structure for multidimensional database systems », ACM Transactions on Database Systems, vol. 5, n^o 3,‎ 1980, p. 339 (DOI 10.1145/320613.320618)
4. Dan E. Willard, « The super-b-tree algorithm », Tech report TR-03-79, Cambridge, MA, Aiken Computer Lab, Harvard University,‎ 1979
5. (en) Bernard Chazelle, « Lower Bounds for Orthogonal Range Searching: I. The Reporting Case », ACM, vol. 37,‎ 1990, p. 200-212 (lire en ligne)
6. (en) Bernard Chazelle, « Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model », ACM, vol. 37,‎ 1990, p. 439-463 (lire en ligne)
7. (en) Mark de Berg, Otfried Cheong, Marc van Kreveld et Mark Overmars, Computational Geometry : algorithms and applications, Berlin, Springer, 2008, 386 p. (ISBN 978-3-540-77973-5, BNF 41264669, DOI 10.1007/978-3-540-77974-2)

Liens extérieurs

• Range and Segment Trees in CGAL, the Computational Geometry Algorithms Library.
• Lecture 8: Range Trees, Marc van Kreveld.
• Erik Demaine, « Lecture 9: Augmentation: Range Trees », sur MIT : vidéo d'un cours sur les arbres de portée.

• Portail de l'informatique théorique