Datenstrukturen - Beste selbstausgleichende BST zum schnellen Einfügen einer großen Anzahl von Knoten

Translate

Ich konnte Details zu mehreren selbstausgleichenden findenBSTs durch mehrere Quellen, aber ich habe keine guten Beschreibungen gefunden, die genau beschreiben, welche in verschiedenen Situationen am besten zu verwenden ist (oder ob es wirklich egal ist).

ich will einBSTDas ist optimal für die Speicherung von mehr als zehn Millionen Knoten. Die Reihenfolge des Einfügens der Knoten ist grundsätzlich zufällig, und ich werde niemals Knoten löschen müssen, sodass die Einfügezeit das einzige ist, was optimiert werden müsste.

Ich beabsichtige, damit zuvor besuchte Spielzustände in einem Puzzlespiel zu speichern, damit ich schnell überprüfen kann, ob bereits eine vorherige Konfiguration gefunden wurde.

This question and all comments follow the "Attribution Required."

Alle Antworten

Translate

Rot schwarzist besser als AVL für einfügungsintensive Anwendungen. Wenn Sie eine relativ einheitliche Suche vorhersehen, ist Rot-Schwarz der richtige Weg. Wenn Sie eine relativ unausgewogene Suche vorsehen, bei der neuere Elemente mit größerer Wahrscheinlichkeit erneut angezeigt werden, möchten Sie sie verwendenBäume spreizen.

Quelle
Translate

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

Der einzige Grund für die Verwendung von aBSTwäre, wenn Sie den Inhalt des Containers in Schlüsselreihenfolge auflisten möchten. Es hört sich sicher nicht so an, als ob Sie das tun möchten. In diesem Fall gehen Sie zur Hash-Tabelle.O(1)Einfügen und Suchen, keine Sorge um das Löschen, was könnte besser sein?

Quelle
Anastasia Lee
Translate

Die beiden balancieren sich selbst ausBSTs Ich kenne mich am besten mit rot-schwarz und ausAVLDaher kann ich nicht mit Sicherheit sagen, ob andere Lösungen besser sind, aber wie ich mich erinnere, hat Rot-Schwarz eine schnellere Einfügung und einen langsameren Abruf im Vergleich zuAVL.

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

Quelle
Translate

[Hash-Tabellen haben] O (1) Einfügen und Suchen

Ich denke das ist falsch.

Wenn Sie den Schlüsselbereich 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önnen das Array mischen und dann einen linearen Scan in der erwarteten O (1) -Zeit durchführen. Wenn das Zeug endlich ist, ist das Zeug leicht O (1).

Angenommen, Ihre Hash-Tabelle speichert eine beliebige Bitfolge. es spielt keine große Rolle, solange es unendlich viele Schlüssel gibt, von denen jeder endlich ist. Dann müssen Sie alle Bits einer Abfrage- und Einfügeeingabe lesen, andernfalls füge ich y0 in einen leeren Hash ein und frage y1 ab, wobei sich y0 und y1 an einer einzelnen Bitposition unterscheiden, die Sie nicht betrachten.

Angenommen, die Schlüssellängen sind kein Parameter. Wenn Ihre Einfügung und Suche O (1) benötigt, dauert insbesondere das Hashing O (1), was bedeutet, dass Sie nur eine begrenzte Menge der Ausgabe der Hash-Funktion betrachten (von der es wahrscheinlich ist)benur eine endliche Ausgabe, gewährt).

Dies bedeutet, dass es bei endlich vielen Buckets unendlich viele Zeichenfolgen geben muss, die alle den gleichen Hashwert haben. Angenommen, ich füge eine Menge davon ein, dh ω (1), und beginne mit der Abfrage. Dies bedeutet, dass Ihre Hash-Tabelle auf einen anderen O (1) -Einfügungs- / Suchmechanismus zurückgreifen muss, um meine Fragen zu beantworten. Welches und warum nicht einfach direkt nutzen?

Quelle