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

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.

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

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.