Baum mit log n Aufwand für Einfügen und Löschen und.

[VincentK]

Hallo,

für die Implementierung einer Lösung für das Sichtbarkeitsproblem brauche ich eine Datenstruktur, die eine sortiere Liste mit Double-Schlüsseln speichern kann, für das Einfügen und Löschen einen Aufwand von log n besitzt und zusätzlich noch folgende Bedingung besitzt:
Es muss mit konstanten Aufwand möglich sein, die beiden Nachbarn - also Vor- und Nachfolger bezüglich der Sortierung - eines Blattes ermitteln zu können.

Dies soll mit einem Baum möglich sein, bei dem die Blätter durch eine Liste verkettet sind.


Im Moment kann ich mir nicht vorstellen, wie man so eine Struktur erstellen soll? Natürlich könnte ich das TreeMap von Java benutzen (Rot-Schwarz Baum), aber dort kann ich mir nicht vorstellen, wie ich die Einträge noch ohne einen Aufwand größer log n sortiert mit einer Liste verketten soll.

Hat jemand von euch einen Tipp für mich?

 

[musiKk]

Ein B+-Baum waere da vielleicht geeignet. Da sind alle Blatt-Knoten verkettet. Beim Loeschen und Einfuegen kann es, wenn ein Blatt- oder Zwischenknoten mal zu voll wird auch ein wenig Aufwand zum Umsortieren geben, aber irgendwo muss man einen Abstrich machen; den perfekten Baum, der alles kann, gibts meines Wissens nicht. Und so schlecht kann er nicht sein, schliesslich wird er in Datenbanksystemen als Indexstruktur verwendet.

 

[VincentK]

Aber sind die Blätter eines B+-Baums nicht nur einfach verkettet, zeigen also nur auf ihren Nachfolger? Damit könnte man den Vorgänger ja leider nicht mit konstantem Aufwand ermitteln.

 

[musiKk]

Nein, die sind meines Wissens auch rueckwaerts verkettet. Das wird auch fuer Loeschvorgaenge und eine damit eventuell notwendige Umverteilung der Datenzeiger benoetigt.

 

[VincentK]

Dann wäre das die perfekte Lösung. Standardmäßig scheint so ein Baum nicht in Java integriert zu sein, ich werde mich mal auf die Suche nach Implementierungen machen.

 

[VincentK]

Hab anscheinend eine Implementierung gefunden, die ich mir morgen mal in Ruhe anschauen werde.

Danke für die Tipps, musiKk!