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.