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

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

Odpowiedź nie została udzielona na stackoverflow.com/questions/2795989/... , tam odpowiedź podaje jedynie definicję.

— Aditya

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

I nigdzie nie ma dobrej odpowiedzi na to pytanie. Dobra odpowiedź będzie świetna dla społeczności

— Aditya

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

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

@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,

Dzięki, byłbym zainteresowany wszelkimi opracowaniami, jakie możesz w tej sprawie podać.

— j_random_hacker

@ 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

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

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

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

Czy drzewo segmentów nie powinno mieć O(n logn) spacew pierwszej tabeli?

— Danny_ds,