Jakie są różnice między drzewami segmentów, drzewami interwałowymi, drzewami indeksowanymi binarnie i drzewami zasięgu?

Jakie są różnice między drzewami segmentów, drzewami interwałowymi, drzewami indeksowanymi binarnie i drzewami zasięgu pod względem:

• Kluczowy pomysł / definicja
• Aplikacje
• Wydajność / zamówienie w większych wymiarach / zużycie miejsca

Proszę nie podawać tylko definicji.

Wszystkie te struktury danych służą do rozwiązywania różnych problemów:

• Drzewo segmentów przechowuje przedziały i jest zoptymalizowane pod kątem zapytań „ który z tych przedziałów zawiera dany punkt ”.
• Drzewo interwałów również przechowuje interwały, ale zoptymalizowane pod kątem zapytań „ które z tych interwałów pokrywają się z danym interwałem ”. Może być również używany do zapytań punktowych - podobnie jak drzewo segmentów.
• Drzewo zasięgu przechowuje punkty i jest zoptymalizowane pod kątem zapytań „ które punkty mieszczą się w danym przedziale ”.
• Binarne drzewo indeksowane przechowuje liczbę elementów według indeksu i jest zoptymalizowane pod kątem „ liczby elementów między zapytaniami o indeksie n ”.

Wydajność / zużycie miejsca dla jednego wymiaru:

• Drzewo segmentów - czas wstępnego przetwarzania O (n logn), czas zapytania O (k + logn), przestrzeń O (n logn)
• Drzewo interwałów - czas wstępnego przetwarzania O (n logn), czas zapytania O (k + logn), przestrzeń O (n)
• Drzewo zakresu - czas wstępnego przetwarzania O (n logn), czas zapytania O (k + logn), spacja O (n)
• Drzewo indeksowane binarnie - czas wstępnego przetwarzania O (n logn), czas zapytania O (logn), przestrzeń O (n)

(k to liczba zgłoszonych wyników).

Wszystkie struktury danych mogą być dynamiczne w tym sensie, że scenariusz użycia obejmuje zarówno zmiany danych, jak i zapytania:

• Drzewo segmentów - interwał można dodawać / usuwać w czasie O (logn) (patrz tutaj )
• Drzewo interwałów - interwał można dodawać / usuwać w czasie O (logn)
• Drzewo zasięgu - nowe punkty można dodawać / usuwać w czasie O (logn) (patrz tutaj )
• Drzewo indeksowane binarnie - liczbę elementów na indeks można zwiększyć w czasie O (logn)

Wyższe wymiary (d> 1):

• Drzewo segmentów - O (n (logn) ^ d) czas wstępnego przetwarzania, O (k + (logn) ^ d) czas zapytania, O (n (logn) ^ (d-1)) przestrzeń
• Drzewo interwałów - czas wstępnego przetwarzania O (n logn), O (k + (logn) ^ d) czas zapytania, przestrzeń O (n logn)
• Drzewo zakresu - O (n (logn) ^ d) czas wstępnego przetwarzania, O (k + (logn) ^ d) czas zapytania, O (n (logn) ^ (d-1))) spacja
• Drzewo indeksowane binarnie - O (n (logn) ^ d) czas wstępnego przetwarzania, O ((logn) ^ d) czas zapytania, O (n (logn) ^ d) przestrzeń

Nie to, że mogę dodać coś do odpowiedzi Liora , ale wygląda na to, że przydałoby się to przy dobrym stole.

Jeden wymiar

k to liczba zgłoszonych wyników

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |        n logn |     n logn |         n logn |    n logn |
|Query         |        k+logn |     k+logn |         k+logn |      logn |
|Space         |        n logn |          n |              n |         n |
|              |               |            |                |           |
|Insert/Delete |          logn |       logn |           logn |      logn |

Wyższe wymiary

d > 1

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |     n(logn)^d |     n logn |      n(logn)^d | n(logn)^d |
|Query         |    k+(logn)^d | k+(logn)^d |     k+(logn)^d |  (logn)^d |
|Space         | n(logn)^(d-1) |     n logn | n(logn)^(d-1)) | n(logn)^d |

Tabele te są tworzone w GitHub formatowaniem cenowych - zobacz ten GIST jeśli chcesz ładnie sformatowane tabele.