| Property |
Value |
| dbo:abstract
|
- 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[citation nécessaire] 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[réf. nécessaire]. (fr)
- 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[citation nécessaire] 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[réf. nécessaire]. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 23038 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:date
|
- octobre 2017 (fr)
- octobre 2017 (fr)
|
| prop-fr:thème
|
- informatique (fr)
- informatique (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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[citation nécessaire] 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. (fr)
- 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[citation nécessaire] 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. (fr)
|
| rdfs:label
|
- Arbre d'intervalles (fr)
- Interval tree (en)
- 区間木 (ja)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
