Was sind die Unterschiede zwischen Segmentbäumen, Intervallbäumen, binär indizierten Bäumen und Bereichsbäumen?

Was sind Unterschiede zwischen Segmentbäumen, Intervallbäumen, binär indizierten Bäumen und Bereichsbäumen in Bezug auf:

• Schlüsselidee / Definition
• Anwendungen
• Leistung / Auftrag in höheren Dimensionen / Platzverbrauch

Bitte geben Sie nicht nur Definitionen an.

Alle diese Datenstrukturen werden zur Lösung verschiedener Probleme verwendet:

• Der Segmentbaum speichert Intervalle und ist für Abfragen optimiert, bei denen " welches dieser Intervalle einen bestimmten Punkt enthält ".
• Der Intervallbaum speichert auch Intervalle, ist jedoch für Abfragen optimiert, " welche dieser Intervalle sich mit einem bestimmten Intervall überschneiden ". Es kann auch für Punktabfragen verwendet werden - ähnlich wie beim Segmentbaum.
• Der Bereichsbaum speichert Punkte und optimiert für Abfragen, " welche Punkte in ein bestimmtes Intervall fallen ".
• Der binär indizierte Baum speichert die Anzahl der Elemente pro Index und ist für die Abfrage " Wie viele Elemente befinden sich zwischen Index m und n " optimiert .

Leistung / Platzverbrauch für eine Dimension:

• Segmentbaum - O (n logn) Vorverarbeitungszeit, O (k + logn) Abfragezeit, O (n logn) Raum
• Intervallbaum - O (n logn) Vorverarbeitungszeit, O (k + logn) Abfragezeit, O (n) Raum
• Bereichsbaum - O (n logn) Vorverarbeitungszeit, O (k + logn) Abfragezeit, O (n) Raum
• Binär indizierter Baum - O (n logn) Vorverarbeitungszeit, O (logn) Abfragezeit, O (n) Raum

(k ist die Anzahl der gemeldeten Ergebnisse).

Alle Datenstrukturen können dynamisch sein, da das Nutzungsszenario sowohl Datenänderungen als auch Abfragen umfasst:

• Segmentbaum - Intervall kann in O (logn) Zeit hinzugefügt / gelöscht werden (siehe hier )
• Intervallbaum - Intervall kann in O (logn) Zeit hinzugefügt / gelöscht werden
• Bereichsbaum - Neue Punkte können in O (logn) Zeit hinzugefügt / gelöscht werden (siehe hier )
• Binär indizierter Baum - Die Anzahl der Elemente pro Index kann in O (logn) -Zeit erhöht werden

Höhere Abmessungen (d> 1):

• Segmentbaum - O (n (logn) ^ d) Vorverarbeitungszeit, O (k + (logn) ^ d) Abfragezeit, O (n (logn) ^ (d-1)) Raum
• Intervallbaum - O (n logn) Vorverarbeitungszeit, O (k + (logn) ^ d) Abfragezeit, O (n logn) Raum
• Bereichsbaum - O (n (logn) ^ d) Vorverarbeitungszeit, O (k + (logn) ^ d) Abfragezeit, O (n (logn) ^ (d-1))) Raum
• Binär indizierter Baum - O (n (logn) ^ d) Vorverarbeitungszeit, O ((logn) ^ d) Abfragezeit, O (n (logn) ^ d) Raum

Nicht, dass ich Lior's Antwort etwas hinzufügen könnte könnte, aber es scheint, als könnte es einen guten Tisch vertragen.

Eine Dimension

k ist die Anzahl der gemeldeten Ergebnisse

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

Höhere Abmessungen

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 |

Diese Tabellen werden in Github-formatiertem Markdown erstellt. Sehen Sie sich diese Liste an, wenn Sie möchten, dass die Tabellen gut formatiert werden.