| rdfs:comment
| - 区間木またはインターバル木（英: Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（英: Segment tree, segtree）があるが別物である。 (ja)
- 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. (es)
- 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)
- 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)
- 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. (pl)
|
| has abstract
| - 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)
- 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. (es)
- 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)
- 区間木またはインターバル木（英: Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（英: Segment tree, segtree）があるが別物である。 (ja)
- 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. (pl)
|
![[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)
