| Attributes | Values |
|---|
| rdfs:label
| - Arbre d'intervalles (fr)
- Interval tree (en)
- 区間木 (ja)
|
| 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)
|
| rdfs:seeAlso
| |
| sameAs
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| dbo:wikiPageWikiLink
| |
| Link from a Wikipage to an external page
| |
| page length (characters) of wiki page
| |
| dct:subject
| |
| prop-fr:wikiPageUsesTemplate
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| prop-fr:date
| |
| prop-fr:thème
| |
| thumbnail
| |
| foaf:isPrimaryTopicOf
| |
| has 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)
|
| is dbo:wikiPageWikiLink
of | |
| is Wikipage redirect
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
