Jakie są różnice między drzewami segmentowymi, drzewami interwałowymi, drzewami indeksowanymi binarnie i drzewami zakresowymi?

Question

Jakie są różnice między drzewami segmentowymi, drzewami interwałowymi, drzewami indeksowanymi binarnie i drzewami zakresowymi?

Jakie są różnice między drzewami segmentowymi, drzewami interwałowymi, drzewami indeksowanymi binarnie i drzewami zakresowymi w kategoriach:

Klucz idea / definicja
aplikacje
Wydajność / porządek w wyższych wymiarach / zużycie przestrzeni

Proszę nie podawać tylko definicji.

213

algorithm tree graph-algorithm interval-tree segment-tree

Author: Michael Petrotta, 2013-07-04

Source

2 answers

Nie żebym mógł coś dodać do Lior ' s answer , ale wygląda na to, że przydałby się dobry stół.

Jeden Wymiar

k 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 |

Te tabele są tworzone w Github sformatowanym Markdown-zobacz ten Gist Jeśli chcesz, aby tabele były ładnie sformatowane.

27

Author: icc97,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2019-10-30 13:30:46

score 338 · Accepted Answer

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

drzewo segmentów przechowuje interwały i jest zoptymalizowane pod kątem zapytań "który z tych interwałów zawiera dany punkt ".
drzewo interwałówrównież przechowuje interwały, ale zoptymalizowane pod kątem " które z tych interwałów nakładają się na dany interwał" zapytań. Może być również używany do zapytań punktowych-podobnie jak drzewo segmentów.
Range tree przechowuje punkty i zoptymalizowano dla zapytań" które punkty mieszczą się w danym przedziale".
binarne drzewo indeksowane przechowuje liczbę pozycji na indeks i jest zoptymalizowane pod kątem zapytań " ile pozycji znajduje się pomiędzy indeksami m I n ".

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

drzewo segmentów - O (N logn) czas przetwarzania wstępnego, O (k+logn) czas zapytań, o (n logn) przestrzeń
drzewo interwałowe - O(N logn) czas przetwarzania wstępnego, O(k+logn) zapytanie czas, O (N) przestrzeń
Range tree - O (N logn) czas przetwarzania wstępnego, O (k+logn) czas zapytania, O (N) przestrzeń
binarne drzewo indeksowane - O (N logn) czas przetwarzania wstępnego, o (logn) czas zapytań, o (n) przestrzeń

(k jest liczbą 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że być dodany/usunięty w czasie O (logn) (zobacz tutaj )
Interval tree - interwał może być dodany/usunięty w czasie O (logn)
Range tree - nowe punkty można dodawać/usuwać w czasie O (logn) (zobacz tutaj)
binarne drzewo indeksowane - Liczba pozycji na indeks może być zwiększona w czasie O (logn)

Wyższe wymiary (d>1):

drzewo segmentów - O(n (logn)^d) czas przetwarzania wstępnego, O (k+(logn)^d) czas zapytania, O(n (logn)^(d-1)) przestrzeń
drzewo interwałowe - O(N logn) czas przetwarzania wstępnego, O(k+(logn)^d) czas zapytania, O (n logn) przestrzeń
Range tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1))) space
binarne drzewo indeksowane - O (N (logn)^d) czas przetwarzania wstępnego, O ((logn)^d) czas zapytania, O(n (logn)^d) przestrzeń