In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard.The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of (in Big O notation) but worse storage of , where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Bereichsbaum (de)
- Arbre de portée (fr)
- Range tree (en)
|
| rdfs:comment
| - Ein Bereichsbaum (englisch range tree) ist eine Datenstruktur für das Speichern einer Menge von Punkten im k-dimensionalen reellen Raum .Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient orthogonale Bereichsanfragen. (de)
- 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 mais un stockage pire en , 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. (fr)
- In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard.The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of (in Big O notation) but worse storage of , where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query. (en)
|
| name
| |
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| type
| |
| has abstract
| - Ein Bereichsbaum (englisch range tree) ist eine Datenstruktur für das Speichern einer Menge von Punkten im k-dimensionalen reellen Raum .Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient orthogonale Bereichsanfragen. (de)
- 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 mais un stockage pire en , 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 et la complexité spatiale en . (fr)
- In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard.The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of (in Big O notation) but worse storage of , where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query. Bernard Chazelle improved this to query time and space complexity . (en)
|
| invented by
| |
| invented year
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
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)
