This HTML5 document contains 72 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n14http://dbpedia.org/resource/File:
dbpedia-eshttp://es.dbpedia.org/resource/
n16http://www.cgal.org/
n10https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n22https://github.com/Breinify/brein-time-utilities/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
n13http://commons.wikimedia.org/wiki/Special:FilePath/
n19http://code.google.com/p/intervaltree/
n25https://github.com/chaimleib/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n15https://github.com/misshie/interval-tree/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n30https://www.boost.org/doc/libs/1_64_0/libs/icl/doc/html/
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:Interval_tree
rdf:type
dbo:Building
rdfs:label
区間木 Interval tree Drzewo przedziałowe Árbol de intervalo Arbre d'intervalles
rdfs:comment
Drzewo przedziałowe (ang. interval tree, range tree, drzewo zakresowe) – struktura danych przechowująca punkty, oraz związane z tymi punktami wszystkie możliwe przedziały. Drzewo przedziałowe, jeśli jest skonstruowane tak, aby było zrównoważone, pozwala odpowiadać na zapytania o dowolny przedział w czasie logarytmicznym. Przykładami zapytań dla drzew przedziałowych może być: Drzewo przedziałowe w celu odpowiedzi na takie pytania w czasie logarytmicznym, poza tym że musi być zrównoważone, przechowuje dodatkowe informacje (tzw. informacje agregujące) w każdym węźle, opisujące całe poddrzewo. En ciencia de la computación, un árbol de intervalo es una para mantener intervalos. En concreto, permite encontrar de manera eficiente todos los intervalos que se solapan con cualquier otro intervalo o punto dado. A menudo se utiliza para las consultas de ventanas, por ejemplo, para encontrar todos los caminos en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el árbol de segmento. In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree. 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. 区間木またはインターバル木（英: Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（英: Segment tree, segtree）があるが別物である。
foaf:depiction
n13:Example_of_augmented_tree_with_low_value_as_the_key_and_maximum_high_as_extra_annotation.png n13:Check_if_a_point_overlaps_the_intervals_in_S_center_of_a_centered_interval_tree.svg n13:Binary_search_tree_delete.svg
dcterms:subject
dbc:Search_trees
dbo:wikiPageID
1533767
dbo:wikiPageRevisionID
1122891003
dbo:wikiPageWikiLink
dbr:Self-balancing_binary_search_tree dbr:Marc_van_Kreveld dbr:Franco_P._Preparata dbr:Binary_search_tree dbr:Tree_rotation dbr:Binary_tree dbr:Kd-tree dbc:Search_trees dbr:Michael_Ian_Shamos n14:Binary_search_tree_delete.svg dbr:Range_tree dbr:Computer_science dbr:Asymptotically_optimal dbr:Output-sensitive_algorithm dbr:Otfried_Schwarzkopf dbr:Binary_heap n14:Check_if_a_point_overlaps_the_intervals_in_S_center_of_a_centered_interval_tree.svg dbr:Mark_de_Berg dbr:Interval_(mathematics) dbr:Tree_(data_structure) n14:Example_of_augmented_tree_with_low_value_as_the_key_and_maximum_high_as_extra_annotation.png dbr:Segment_tree dbr:Mark_Overmars
dbo:wikiPageExternalLink
n15: n16: n19: n22:%23intervaltree n25:intervaltree n30:index.html
owl:sameAs
dbpedia-fa:درخت_بازه dbpedia-sr:Интервал_стабла n10:4nokD yago-res:Interval_tree dbpedia-ja:区間木 freebase:m.058qc6 dbpedia-fr:Arbre_d'intervalles wikidata:Q6057306 dbpedia-es:Árbol_de_intervalo dbpedia-pl:Drzewo_przedziałowe
dbp:wikiPageUsesTemplate
dbt:Confusing dbt:CS-Trees dbt:Citation dbt:Harvtxt dbt:Unreferenced_section dbt:Paragraph_break
dbo:thumbnail
n13:Check_if_a_point_overlaps_the_intervals_in_S_center_of_a_centered_interval_tree.svg?width=300
dbo:abstract
En ciencia de la computación, un árbol de intervalo es una para mantener intervalos. En concreto, permite encontrar de manera eficiente todos los intervalos que se solapan con cualquier otro intervalo o punto dado. A menudo se utiliza para las consultas de ventanas, por ejemplo, para encontrar todos los caminos en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el árbol de segmento. La solución trivial es visitar cada intervalo y probar si se cruza el punto o intervalo dado, que requiere Θ(n) tiempo, donde n es el número de intervalos en la colección. Dado que una consulta puede devolver todos los intervalos, por ejemplo, si la consulta es un gran intervalo de intersección de todos los intervalos de la colección, esto es ; Sin embargo, podemos mejorarlo al considerar , donde el tiempo de ejecución se expresa en términos de m, el número de intervalos producidos por la consulta. Los Árboles de intervalo son dinámicos, es decir, que permiten la inserción y la supresión de intervalos. Obtienen un tiempo de consulta de O(log n), mientras que el tiempo de preprocesamiento para construir la estructura de datos es O(n log n) (pero el consumo de espacio es O(n)). Si los puntos extremos de los intervalos están dentro de un rango entero pequeño (por ejemplo, en el intervalo [1, ..., O (n)]), las estructuras de datos más rápidas existen con el tiempo de preprocesamiento O (n) y el tiempo de consulta O(1+m) para informar m intervalos que contienen un punto de consulta dada. 区間木またはインターバル木（英: Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（英: Segment tree, segtree）があるが別物である。 In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree. The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires time, where is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of , the number of intervals produced by the query. Interval trees have a query time of and an initial creation time of , while limiting memory consumption to . After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in time. If the endpoints of intervals are within a small integer range (e.g., in the range ), faster and in fact optimal data structures exist with preprocessing time and query time for reporting intervals containing a given query point (see for a very simple one). 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]. Drzewo przedziałowe (ang. interval tree, range tree, drzewo zakresowe) – struktura danych przechowująca punkty, oraz związane z tymi punktami wszystkie możliwe przedziały. Drzewo przedziałowe, jeśli jest skonstruowane tak, aby było zrównoważone, pozwala odpowiadać na zapytania o dowolny przedział w czasie logarytmicznym. Przykładami zapytań dla drzew przedziałowych może być: * ile jest kluczy w zbiorze większych niż "Cava" i przy tym mniejszych niż "Kofa"? * jaka jest największa wartość pomiędzy 400 a 500 pozycją? * jakie jest odchylenie standardowe wartości które odpowiadają kluczom z zakresu od "F2a" do "I3"? * czy różnica liczby elementów parzystych i nieparzystych pomiędzy pozycją 214314 a 219131 jest parzysta? Drzewo przedziałowe w celu odpowiedzi na takie pytania w czasie logarytmicznym, poza tym że musi być zrównoważone, przechowuje dodatkowe informacje (tzw. informacje agregujące) w każdym węźle, opisujące całe poddrzewo. * W pierwszym przypadku jest to liczba kluczy w poddrzewie, * w drugim jest to wartość maksymalna w poddrzewie, * w trzecim mogą to być 3 pierwsze momenty (na podstawie których da się wyliczyć odchylenie standardowe) lub ilość, średnia oraz odchylenie standardowe w danym poddrzewie, * w czwartym przypadku odpowiedź na pytanie dla każdego poddrzewa. W najczęstszym przypadku binarnych drzew przedziałowych, dane przechowywane w każdym węźle powinny być możliwe do obliczenia tylko na podstawie analogicznych danych dla lewego i prawego poddrzewa, poprzez redukcję, bez potrzeby rekursji w głąb drzewa. * W pierwszym przypadku liczba kluczy w poddrzewie, to liczba kluczy w lewym poddrzewie + liczba kluczy w prawym poddrzewie, * w drugim przypadku maksimum w poddrzewie to maksimum z maksimum w lewym i prawym poddrzewie, * w trzecim przypadku momenty to sumy momentów z lewego i prawego poddrzewa, * w czwartym przypadku, wystarczy dokonać operacji alternatywy wykluczającej. Drzewa przedziałowe mogą zostać uogólnione na przestrzenie wielowymiarowe, i np. odpowiadać szybko na pytania typu "Ile jest domów w prostokącie o wierzchołkach odpowiednio w Gdańsku i Krakowie?" Drzewa przedziałowe mogą również być oparte na strukturach innych niż drzewa binarne. W systemach bazodanowych stosuje zwykle się B-drzewa. W przypadku usunięcia, dodania, lub zmiany węzła w drzewie przedziałowym, należy przeprowadzić aktualizacje danych dodatkowych na ścieżce do tego węzła. Analogiczną procedurę trzeba zastosować w przypadku wyważania, ponieważ struktura drzewa, jak i to na co wskazują dane dodatkowe może się zmienić (np. w przypadku rotacji). Binarne drzewa przedziałowe, są binarnym drzewami poszukiwań rozszerzonymi o dodatkową funkcjonalność. W wielu zastosowaniach, w drzewach przedziałowych wartości przechowuje się tylko w liściach, natomiast w węzłach wewnętrznych (nie liściach), przechowuje się tylko informacje agregujące.
gold:hypernym
dbr:Structure
prov:wasDerivedFrom
wikipedia-en:Interval_tree?oldid=1122891003&ns=0
dbo:wikiPageLength
23942
foaf:isPrimaryTopicOf
wikipedia-en:Interval_tree