Apa perbedaan antara pohon segmen, pohon interval, pohon indeks biner dan pohon jarak?

Apa perbedaan antara pohon segmen, pohon interval, pohon indeks biner dan pohon rentang dalam hal:

• Gagasan / definisi utama
• Aplikasi
• Performa / ketertiban dalam dimensi / konsumsi ruang yang lebih tinggi

Tolong jangan hanya memberikan definisi.

Semua struktur data ini digunakan untuk memecahkan masalah yang berbeda:

• Pohon segmen menyimpan interval, dan dioptimalkan untuk kueri " yang mana dari interval ini berisi titik tertentu ".
• Interval tree juga menyimpan interval, tetapi dioptimalkan untuk kueri " yang mana dari interval ini tumpang tindih dengan interval yang diberikan ". Ini juga dapat digunakan untuk kueri titik - mirip dengan pohon segmen.
• Rentang pohon menyimpan poin, dan dioptimalkan untuk kueri " yang jatuh dalam interval tertentu ".
• Pohon biner diindeks menyimpan item-hitung per indeks, dan dioptimalkan untuk " berapa banyak item yang ada antara kueri indeks m dan n ".

Konsumsi Kinerja / Ruang untuk satu dimensi:

• Pohon segmen - O (n logn) waktu preprocessing, O (k + logn) waktu query, O (n logn) ruang
• Interval tree - O (n logn) waktu preprocessing, O (k + logn) waktu query, O (n) spasi
• Rentang pohon - O (n logn) waktu preprocessing, O (k + logn) waktu query, O (n) ruang
• Binary Indexed tree - O (n logn) waktu preprocessing, O (logn) waktu query, O (n) space

(k adalah jumlah hasil yang dilaporkan).

Semua struktur data dapat bersifat dinamis, dalam arti bahwa skenario penggunaan mencakup perubahan dan kueri data:

• Pohon segmen - interval dapat ditambahkan / dihapus dalam waktu O (logn) (lihat di sini )
• Interval tree - interval dapat ditambahkan / dihapus dalam waktu O (logn)
• Pohon rentang - poin baru dapat ditambahkan / dihapus dalam waktu O (logn) (lihat di sini )
• Binary Indexed tree - item-count per indeks dapat ditingkatkan dalam waktu O (logn)

Dimensi yang lebih tinggi (d> 1):

• Pohon segmen - O (n (logn) ^ d) waktu preprocessing, O (k + (logn) ^ d) waktu permintaan, O (n (logn) ^ (d-1)) ruang
• Interval tree - O (n logn) waktu preprocessing, O (k + (logn) ^ d) waktu permintaan, O (n logn) ruang
• Rentang pohon - O (n (logn) ^ d) waktu preprocessing, O (k + (logn) ^ d) waktu permintaan, O (n (logn) ^ (d-1))) ruang
• Binary Indexed tree - O (n (logn) ^ d) waktu preprocessing, O ((logn) ^ d) waktu permintaan, O (n (logn) ^ d) ruang

Bukannya aku bisa menambahkan apa pun pada jawaban Lior , tapi sepertinya itu bisa dilakukan dengan tabel yang bagus.

Satu dimensi

k adalah jumlah hasil yang dilaporkan

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

Dimensi Tinggi

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 |

Tabel ini dibuat di Github Formatted Markdown - lihat Gist ini jika Anda ingin tabel diformat dengan baik.