Arbre de portée
# 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. Des structures de données similaires ont été indépendamment découvertes par Lueker, Lee and Wong, et Willard. 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 $O(\log ^{d}n+k)$ mais un stockage pire en $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 $O(\log ^{d-1}n+k)$ et la complexité spatiale en $O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)$$^,.$

## Description

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 grande sont construites récursivement en construisant un arbre binaire de recherche équilibré sur la première coordonné 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). 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 dimensions sur la coordonnée y' des points dans S. Soit $x_m$ la médiane des 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−1}n).$

### Requête de distance

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_1,$ $x_2],$ on commence par chercher $x_1$ et $x_2.$ À certains sommets dans l'arbre, le chemin de recherche pour $x_1$ et $x_2$ va diverger. Soit $v_{split}$ le dernier sommet que ces deux chemins de recherche ont en commun. On continue à chercher pour $x_1$ dans l'arbre de portée. Pour chaque sommet v dans le chemin de recherche depuis $v_{split}$ à $x_1,$ si la valeur stockée à v est plus grande que $x_1,$ 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_2$ tout au long du chemin de recherche de $v_{split}$ à $x_2,$ 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_1$ et $x_2$ 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^2n)$ 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^2n).$

É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−1}n$ + k) en utilisant la technique de cascade $fractionnée^,^,.$

