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.