Bestes selbstausgleichendes BST zum schnellen Einfügen einer großen Anzahl von Knoten

Question

Ich konnte Details zu mehreren Selbstausgleichen finden BSTIch habe mehrere Quellen durchsucht, aber ich habe keine guten Beschreibungen gefunden, die detailliert beschreiben, welche davon in verschiedenen Situationen am besten verwendet werden kann (oder wenn es wirklich keine Rolle spielt).

ich will ein BST Dies ist optimal für die Speicherung von mehr als zehn Millionen Knoten.Die Reihenfolge, in der die Knoten eingefügt werden, ist grundsätzlich zufällig und ich muss nie Knoten löschen, daher ist die Einfügezeit das Einzige, was optimiert werden müsste.

Ich beabsichtige, damit zuvor besuchte Spielzustände in einem Puzzlespiel zu speichern, damit ich schnell überprüfen kann, ob eine frühere Konfiguration bereits aufgetreten ist.

Answer 1

Rot schwarz ist für einfügungsintensive Anwendungen besser als AVL.Wenn Sie ein relativ einheitliches Erscheinungsbild erwarten, ist Rot-Schwarz die richtige Wahl.Wenn Sie eine relativ unausgewogene Suche erwarten, bei der kürzlich angezeigte Elemente mit größerer Wahrscheinlichkeit erneut angezeigt werden, möchten Sie diese verwenden Spreizbäume.

Answer 2

Warum ein verwenden? BST überhaupt?Nach Ihrer Beschreibung funktioniert ein Wörterbuch genauso gut, wenn nicht sogar besser.

Der einzige Grund für die Verwendung von a BST wäre, wenn Sie den Inhalt des Containers in der Schlüsselreihenfolge auflisten möchten.Es hört sich sicherlich nicht so an, als ob Sie das tun möchten. In diesem Fall sollten Sie sich für die Hash-Tabelle entscheiden. O(1) Einfügen und Suchen, keine Angst vor dem Löschen, was könnte besser sein?

Answer 3

Die beiden balancieren sich selbst aus BSTDie Farben, mit denen ich am besten vertraut bin, sind Rot-Schwarz und AVL, Daher kann ich nicht mit Sicherheit sagen, ob andere Lösungen besser sind, aber soweit ich mich erinnere, hat Rot-Schwarz im Vergleich zu Rot-Schwarz eine schnellere Einfügung und einen langsameren Abruf AVL.

Wenn also das Einfügen eine höhere Priorität als das Abrufen hat, ist Rot-Schwarz möglicherweise die bessere Lösung.

Answer 4

[Hash-Tabellen haben] O(1) Einfügung und Suche

Ich denke, das ist falsch.

Wenn Sie den Schlüsselraum auf endlich beschränken, können Sie zunächst die Elemente in einem Array speichern und einen linearen O(1)-Scan durchführen.Oder Sie könnten das Array neu sortieren und dann einen linearen Scan in der erwarteten Zeit von O(1) durchführen.Wenn Dinge endlich sind, sind sie leicht O(1).

Nehmen wir also an, Ihre Hash-Tabelle speichert jede beliebige Bitfolge.Es spielt keine große Rolle, solange es eine unendliche Menge von Schlüsseln gibt, von denen jeder endlich ist.Dann müssen Sie alle Bits aller Abfrage- und Einfügungseingaben lesen, andernfalls füge ich y0 in einen leeren Hash ein und frage nach y1, wobei sich y0 und y1 an einer einzelnen Bitposition unterscheiden, die Sie nicht betrachten.

Aber nehmen wir an, die Schlüssellängen sind kein Parameter.Wenn Ihre Einfügung und Suche O(1) benötigen, benötigt insbesondere das Hashing O(1) Zeit, was bedeutet, dass Sie nur eine endliche Menge an Ausgaben der Hash-Funktion betrachten (von der wahrscheinlich auszugehen ist). Sei nur eine endliche Ausgabe, zugegeben).

Das bedeutet, dass es bei endlich vielen Buckets eine unendliche Menge von Strings geben muss, die alle den gleichen Hashwert haben.Angenommen, ich füge viel ein, d.ω(1) davon und beginnen Sie mit der Abfrage.Das bedeutet, dass Ihre Hash-Tabelle auf einen anderen O(1)-Einfügungs-/Suchmechanismus zurückgreifen muss, um meine Anfragen zu beantworten.Welches und warum nicht einfach direkt verwenden?