Binary Search Tree mit 2 Schlüsseln

Question

Ich habe eine Datenbank von Benutzern mit ihren Benutzernamen und IDs. Dies sind die Operationen, die Programm verarbeiten:

insert, delete (von username), search (von username), print (druckt alle Benutzer Informationen, sortiert nach ihrer id)

Zeitkomplexität von ersten drei Operationen shouldn nicht mehr als O(log n) und für den Druck sollte es O(n) sein. Lösung sollte mit einem ausgewogenen BST implementiert werden.

Meine Idee, das Problem zu lösen, ist zu 2 BST zu haben, der Schlüssel von einem ist id und für einen anderen ist username. So können wir auf ein Element mit ihrem Namen oder ihrer ID sowohl in O (log n) -Zeit zugreifen. Dies verdoppelt jedoch Speicherplatz und Betriebszeit.

Gibt es eine Möglichkeit, Elemente sowohl durch ihre username und id in O(log n) Zeit auf eine bessere Weise als das, was ich erklärte, zuzugreifen?

Answer 1

Meine Idee, das Problem zu lösen, ist zu 2 BST zu haben, Schlüssel ist id und für andere username ist. So können wir auf ein Element über ihre username oder id beide in O(log n) Zeit zugreifen. Aber dies verdoppelt Speicherplatz und Zeit von Operationen.

Was Sie vorschlagen, verdoppelt in der Tat die Speicher- und Zeitanforderungen für Ihre Datenstruktur. (Nur Einfügungen und Löschungen benötigen doppelte Zeit. Die anderen Operationen benötigen keine zusätzliche Zeit). Es sei jedoch daran erinnert, dass O(2 log n) im Allgemeinen genauso behandelt wird wie O(log n) und viel weniger als O(n) ist. Zur Veranschaulichung habe ich 2 log n und n grafisch dargestellt. Beachten Sie, dass sie gleich sind, wenn n2 oder 4 ist. log n ist im Wesentlichen eine flache Linie im Vergleich zu n.

Ich schlage vor, dass Sie nicht besser als das mit ausgewogenen BSTs (oder überhaupt, für diese Angelegenheit) tun können. Da Sie basierend auf username in O(log n) Zeit suchen müssen, muss username der Schlüssel für den Baum sein. Sie müssen jedoch auch die Benutzer nach id in O(n) Zeit abgerufen abrufen. Das verbietet es im Wesentlichen, sie nach dem Abrufen zu sortieren, weil Sie sie nicht schneller als O(n log n) sortieren können. Sie müssen daher bereits nach id sortiert sein. Daher muss id ein Schlüssel für den Baum sein. Daher brauchst du zwei Bäume.

Answer 2

Während 2 Bäume in Ordnung sind, können Sie auch eine Hashtabelle zum Suchen und Löschen sowie einen sortierten Index zum Drucken verwenden. Ein rot-schwarzer Baum ist für den sortierten Index in Ordnung.

jedoch, wenn aufeinander folgende IDs nicht negative ganze Zahlen sind, wird es noch effizienter sein, eine einfache Anordnung zu erhalten, in der Position i das Objekt mit der ID von i enthält. Jetzt können Sie drucken, indem Sie einfach das Array durchlaufen. Und die Hash-Tabellenwerte können IDs sein, für die diese auf das jeweilige Objekt im Array "zeigen".