| Der letzte Beitrag |
| yummy93 |
(a, b) - Baum: Datenstruktur modifizieren
Meine Frage:
Hallo zusammen,
für die Uni muss ich folgende Aufgaben lösen:
Betrachten Sie einen (a, b)-Baum B, der n Objekte speichert.
(i) Geben Sie detailliert an, wie zu einem gegebenen Objekt aus B der Nachfolger bzw. der Vorgänger in B bestimmt werden kann. Ihr Verfahren soll eine Laufzeit von O(log n) haben.
(ii) Modifizieren Sie die Datenstruktur so, dass die Bestimmung des Nachfolgers bzw. des Vorgängers in O(1) Zeit möglich ist. Geben Sie Ihre Modifikation an und beschreiben Sie detailliert, wie die Operationen insert und delete entsprechend abgeändert werden müssen. Auch die modifizierten Fassungen dieser Operationen sollen eine Laufzeit von O(log n) haben.
Den ersten Teil habe ich bereits mit dem binären Suchen gelöst. Bei dem zweiten bin ich mir aber recht unsicher. Ich habe den Tipp bekommen, dass man dafür doppelt verkettete Listen benötigt. Diese haben aber doch beim Einfügen und Löschen eine Laufzeit von O(1) und bei der Bestimmung des Vorgängers bzw. Nachfolgers O(log n). Gefordert ist das aber genau anders herum.
Meine Ideen:
Ich dachte mir, dass man die Datenstruktur eher als Skip Liste angeben sollte. Hier haben insert und delete immerhin eine Laufzeit von O(log n). Nur beim Bestimmen des Vorgängers bzw. Nachfolgers ist es hier dann doch auch O(log n), oder irre ich mich?!
Vielleicht habe ich einfach einen Denkfehler...über Tipps würde ich mich daher sehr freuen 
Danke! |
|
|
