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

200

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.

Aditya
źródło
12
To nie jest duplikat, to pytanie brzmi, czy drzewa fenwick są uogólnieniem warkocza interwałowego, a moje pytanie jest bardziej szczegółowe i różne.
Aditya
7
Odpowiedź nie została udzielona na stackoverflow.com/questions/2795989/... , tam odpowiedź podaje jedynie definicję.
Aditya
12
Jak to jest zbyt szerokie? „Jakie są różnice między xiy?” jest tak wyraźny i skupiony, jak to tylko możliwe. To jest bardzo dobre pytanie.
IVlad
16
I nigdzie nie ma dobrej odpowiedzi na to pytanie. Dobra odpowiedź będzie świetna dla społeczności
Aditya
22
Większość tych struktur danych (z wyjątkiem drzew Fenwicka) zostało przejrzanych w tym pliku pdf: „Drzewa wyszukiwania interwałów, segmentów, zakresu i priorytetów” (autor: DT Lee). Możesz też przeczytać go jako rozdział z tej książki: „Handbook of Data Structures and Applications” .
Evgeny Kluev

Odpowiedzi:

319

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ń
Lior Kogan
źródło
12
Naprawdę mam wrażenie, że segmentuj drzewa <drzewa interwałów z tego. Czy jest jakiś powód, aby preferować drzewo segmentów? Np. Prostota wdrożenia?
j_random_hacker
7
@j_random_hacker: Algorytmy oparte na drzewach segmentów mają zalety w niektórych bardziej złożonych, wielowymiarowych wariantach zapytania o interwały. Na przykład znalezienie, które nierównoległe segmenty linii przecinają się z oknem 2D.
Lior Kogan,
5
Dzięki, byłbym zainteresowany wszelkimi opracowaniami, jakie możesz w tej sprawie podać.
j_random_hacker
3
@ j_random_hacker, drzewa segmentów mają jeszcze inne interesujące zastosowanie: RMQ (zapytania minimalne w zakresie) w czasie O (log N), gdzie N jest całkowitym rozmiarem przedziału.
ars-longa-vita-brevis
1
Dlaczego drzewa segmentów O (n log n) są spacjami? Przechowują N liści + N / 2 + N / 4 + ... + N / 2 ^ (log N), a ta suma to O (N), jeśli się nie mylę. Również odpowiedź @ icc97 podaje również przestrzeń O (N).
Ant
24

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.

icc97
źródło
2
Co rozumiesz przez zgłoszone wyniki?
Pratik Singhal
@ PS06756 algorytmy wyszukiwania często mają czas działania log (n), gdzie n jest wielkością wejściową, ale mogą dawać wyniki, które są liniowe w n, czego nie można zrobić w czasie logarytmicznym (wyprowadzenie n liczb w czasie log (n) nie jest możliwe) .
oerpli
1
Czy drzewo segmentów nie powinno mieć O(n logn) spacew pierwszej tabeli?
Danny_ds,