Quelles sont les différences entre les arbres de segment, les arbres d'intervalle, les arbres indexés binaires et les arbres de plage?

200

Quelles sont les différences entre les arbres de segment, les arbres d'intervalle, les arbres indexés binaires et les arbres de plage en termes de:

  • Idée / définition clé
  • Applications
  • Performance / ordre dans des dimensions plus élevées / consommation d'espace

Veuillez ne pas donner seulement des définitions.

Aditya
la source
12
Ce n'est pas un doublon, cette question est de savoir si les arbres de fenwick sont une généralisation de l'intervalle, et ma question est plus spécifique et différente.
Aditya
7
Il n'a pas été répondu à stackoverflow.com/questions/2795989/… , la réponse donne juste la définition.
Aditya
12
En quoi est-il trop large? "Quelles sont les différences entre x et y?" est aussi clair et ciblé que possible. C'est une très bonne question.
IVlad
16
Et il n'y a pas de bonne réponse à cela disponible nulle part. Une bonne réponse sera excellente pour la communauté
Aditya
22
La plupart de ces structures de données (à l'exception des arbres de Fenwick) sont examinées dans ce pdf: "Interval, Segment, Range, and Priority Search Trees" (par DT Lee). Ou vous pouvez le lire comme un chapitre de ce livre: "Manuel des structures de données et des applications" .
Evgeny Kluev

Réponses:

319

Toutes ces structures de données sont utilisées pour résoudre différents problèmes:

  • L'arborescence des segments stocke les intervalles et est optimisée pour les requêtes " lequel de ces intervalles contient un point donné ".
  • L'arbre d' intervalles stocke également les intervalles, mais optimisés pour les requêtes " lesquels de ces intervalles se chevauchent avec un intervalle donné ". Il peut également être utilisé pour les requêtes ponctuelles - similaire à l'arborescence des segments.
  • L'arbre de plage stocke les points et optimisé pour les requêtes " quels points se situent dans un intervalle donné ".
  • L'arborescence indexée binaire stocke le nombre d'éléments par index et est optimisée pour le nombre d'éléments entre les requêtes d' index m et n .

Performance / consommation d'espace pour une dimension:

  • Arbre de segment - O (n logn) temps de prétraitement, O (k + logn) temps de requête, O (n logn) espace
  • Arbre d'intervalle - temps de prétraitement O (n logn), temps de requête O (k + logn), espace O (n)
  • Arbre de plage - O (n logn) temps de prétraitement, O (k + logn) temps de requête, O (n) espace
  • Arbre binaire indexé - temps de prétraitement O (n logn), temps de requête O (logn), espace O (n)

(k est le nombre de résultats rapportés).

Toutes les structures de données peuvent être dynamiques, dans le sens où le scénario d'utilisation inclut à la fois des modifications de données et des requêtes:

  • Arbre de segment - l'intervalle peut être ajouté / supprimé en temps O (logn) (voir ici )
  • Arbre d' intervalle - l'intervalle peut être ajouté / supprimé en temps O (logn)
  • Arbre de plage - de nouveaux points peuvent être ajoutés / supprimés en temps O (logn) (voir ici )
  • Arbre binaire indexé - le nombre d'éléments par index peut être augmenté en temps O (logn)

Dimensions supérieures (d> 1):

  • Arbre de segment - O (n (logn) ^ d) temps de prétraitement, O (k + (logn) ^ d) temps de requête, O (n (logn) ^ (d-1)) espace
  • Arbre d'intervalle - O (n logn) temps de prétraitement, O (k + (logn) ^ d) temps de requête, O (n logn) espace
  • Arbre de plage - O (n (logn) ^ d) temps de prétraitement, O (k + (logn) ^ d) temps de requête, O (n (logn) ^ (d-1))) espace
  • Arbre binaire indexé - O (n (logn) ^ d) temps de prétraitement, O ((logn) ^ d) temps de requête, O (n (logn) ^ d) espace
Lior Kogan
la source
12
J'ai vraiment l'impression que les arbres de segment <arbres d'intervalle de cela. Y a-t-il une raison de préférer un arbre de segment? Par exemple, simplicité de mise en œuvre?
j_random_hacker
7
@j_random_hacker: Les algorithmes basés sur des arbres de segments présentent des avantages dans certaines variantes plus complexes de haute dimension de la requête d'intervalles. Par exemple, trouver les segments de ligne non parallèles à l'axe qui se croisent avec une fenêtre 2D.
Lior Kogan
5
Merci, je serais intéressé par toute élaboration que vous pourriez donner à ce sujet.
j_random_hacker
3
@j_random_hacker, les arbres de segment ont une autre utilisation intéressante: les RMQ (plage de requêtes minimales) en temps O (log N) où N est la taille globale de l'intervalle.
ars-longa-vita-brevis
1
Pourquoi les arbres de segments sont-ils un espace O (n log n)? Ils stockent N feuilles + N / 2 + N / 4 + ... + N / 2 ^ (log N), et cette somme est O (N) si je ne me trompe pas. La réponse @ icc97 indique également un espace O (N).
Ant
24

Non pas que je puisse ajouter quoi que ce soit à la réponse de Lior , mais il semble que cela pourrait faire avec une bonne table.

Une dimension

k est le nombre de résultats rapportés

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |        n logn |     n logn |         n logn |    n logn |
|Query         |        k+logn |     k+logn |         k+logn |      logn |
|Space         |        n logn |          n |              n |         n |
|              |               |            |                |           |
|Insert/Delete |          logn |       logn |           logn |      logn |

Dimensions supérieures

d > 1

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |     n(logn)^d |     n logn |      n(logn)^d | n(logn)^d |
|Query         |    k+(logn)^d | k+(logn)^d |     k+(logn)^d |  (logn)^d |
|Space         | n(logn)^(d-1) |     n logn | n(logn)^(d-1)) | n(logn)^d |

Ces tableaux sont créés dans Github Formatted Markdown - voyez cet Gist si vous voulez que les tableaux soient bien formatés.

icc97
la source
2
Qu'entendez-vous par résultats rapportés?
Pratik Singhal
@ ps06756 les algorithmes de recherche ont souvent un runtime de log (n) où n est la taille d'entrée mais peuvent donner des résultats linéaires en n qui ne peuvent pas être faits en temps logarithmique (la sortie de n nombres en temps log (n) n'est pas possible) .
oerpli
1
L'arbre de segment ne devrait-il pas avoir O(n logn) spacedans le premier tableau?
Danny_ds