Eine Alternative zu zwei AVL-Bäumen

Question

Ich habe derzeit Daten, die ich auf zwei verschiedene Arten sortiert haben muss, aus einer Zeit und Raumkomplexität PoV, gibt es eine Alternative zu zwei Bäumen, einer nach Datum und einer nach ID-Nummer? Ich muss in der Lage sein, Listen in der Reihenfolge von Daten und einzelnen Benutzern nach ID zurückzugeben, und ich würde es vorziehen, nicht durchqueren zu müssen oder, noch schlimmer, zu traversieren und dann nach den Array-Returns zu sortieren.

Jeder Einblick oder Hilfe wird sehr geschätzt, danke!

Answer 1

Sie könnten dies in einem Baum tun, aber Sie würden O (logN) Leistung nur für das Datum erhalten. Die direkte ID-Abfrage wäre sowieso O (N) (d. H. Durchqueren des gesamten Baums, um eine exakte Übereinstimmung zu finden), da die Reihenfolge unbestimmt wäre.

Wenn Ihre ID auf dem benötigten Datum basieren könnte (ich meine, wenn die ID basierend auf dem Datum generiert werden könnte) - dann könnten Sie die O (N) Zeitkomplexität auf O (logN + M) reduzieren, Wobei M - eine Teilmenge von IDs für ein bestimmtes Datum ist.

Je nach Ihrer Reaktionszeit und Speicheranforderungen können Sie nur einen Baum behalten oder mit einem HashMap IDs paaren.

Answer 2

TreeMap implementiert Red-Black tree, die eine Alternative zu AVL ist.

Answer 3

Sie könnten mit einem LinkedHashMap (Objekte gespeichert und abgerufen in der Reihenfolge des Hinzufügens oder last access + alle Standard-HashMap-Operationen mit O (1) Komplexität).

Wenn Sie komplexere Datumszugriffsmuster (Bereiche, Punktabfragen) benötigen, verwenden Sie möglicherweise die gleiche Idee, aber mit einer skip list anstelle einer verknüpften Liste. In diesem Fall ist der Zugriff nach dem Datum O (logN).

Und dann gibt es auch eine Option, die gleiche (verknüpfte Liste oder Überspringen-Liste) über einen Baum zu bauen, wo Sie Werte nach ID setzen.