drzewo przedziałowe

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.