Beste selbstausgleich BST für die schnelle Einführung einer großen Anzahl von Knoten

stimmen
8

Ich habe in der Lage gewesen ist, Details über mehr selbstausgleich zu finden BSTs durch mehrere Quellen, aber ich habe keine gute Beschreibungen detailliert , welche ist am besten in verschiedenen Situationen zu verwenden (oder nur, wenn es wirklich keine Rolle spielt).

Ich möchte ein , BSTdie für die Speicherung von mehr als zehn Millionen Knoten optimal ist. Die Reihenfolge der Einfügung der Knoten ist im Grunde zufällig, und ich werde nie brauchen Knoten zu löschen, so ist Einfügezeitpunkt das einzige , was optimiert werden müßte.

Ich beabsichtige, es zu benutzen, die zuvor besuchte Spiel Zustände in einem Puzzle-Spiel zu speichern, so dass ich schnell, wenn eine vorherige Konfiguration bereits angetroffen wurde, überprüfen.

Veröffentlicht am 05/08/2008 um 16:40
quelle vom benutzer
In anderen Sprachen...                            


4 antworten

stimmen
3

Warum ein BSTüberhaupt? Aus Ihrer Beschreibung wird ein Wörterbuch genauso gut funktionieren, wenn nicht besser.

Der einzige Grund für eine Verwendung BSTwäre, wenn Sie den Inhalt des Behälters in der Reihenfolge des Schlüssels zur Liste wollen. Es ist sicherlich nicht klingen wie Sie wollen , dass in diesem Fall für die Hash - Tabelle gehen. O(1)Einsetzen und Suche, keine Sorgen über Löschung, was könnte besser sein?

Beantwortet am 29/08/2008 um 01:10
quelle vom benutzer

stimmen
3

Rot-schwarz ist besser als AVL zum Einsetzen lastigen Anwendungen. Wenn Sie relativ einheitliche Look-up voraussehen, dann Rot-schwarz ist der Weg zu gehen. Wenn Sie ein relativ unausgewogen Nachschauvoraussehen , wo in jüngster Zeit gesehen Elemente sind eher wieder betrachtet werden, die Sie verwenden mögen spreizen Bäume .

Beantwortet am 05/08/2008 um 16:59
quelle vom benutzer

stimmen
0

Die zwei selbstausgleich BSTs ich am meisten vertraut bin mit rot-schwarz und AVL, so kann ich sicher nicht sagen , ob andere Lösungen besser sind, aber wie ich mich erinnere, rot-schwarz hat schnellere Einführung und langsamen Abruf im Vergleich zu AVL.

Also, wenn Einfügung eine höhere Priorität als Retrieval ist, kann rot-schwarz eine bessere Lösung.

Beantwortet am 05/08/2008 um 16:50
quelle vom benutzer

stimmen
-2

[Hash-Tabellen haben] O (1) Einführen und Such

Ich denke, das ist falsch.

Vor allem, wenn Sie den Schlüsselraum begrenzen endlich zu sein, können Sie die Elemente in einem Array speichern und eine O (1) lineare Abtastung tun. Oder Sie könnten das Array shufflesort und dann eine lineare Abtastung in O (1) erwartete Zeit. Wenn Sachen endlich ist, Material ist leicht O (1).

Also lassen Sie uns sagen, dass Ihre Hash-Tabelle eine beliebige Bitfolge gespeichert werden; Es braucht nicht viel Materie, solange es eine unendliche Reihe von Tasten ist, von denen jede endlich sind. Dann haben Sie alle Bits jeder Abfrage und Einfügen Eingabe lesen, ich sonst y0 in einem leeren Hash und Abfrage auf y1 einfügen, wo y0 und y1 an einer einzelnen Bit-Position abweichen, die Sie nicht suchen.

Aber sagen wir mal , die Schlüssellängen sind kein Parameter. Wenn Ihr Einsetzen und O Suche nehmen (1), insbesondere Hashing nimmt O (1) Zeit, was bedeutet , dass Sie nur in einer endlichen Menge von Ausgabe aus der Hash - Funktion suchen (von denen ihm wahrscheinlich zu sein , nur einen endlichen Ausgang gewährt ).

Dies bedeutet, dass mit endlich vielen Eimern, muss es eine unendliche Menge von Zeichenketten sein, die alle den gleichen Hash-Wert haben. Angenommen, ich eine Menge einzufügen, dh ω (1), von denen, und starten abfragt. Dies bedeutet, dass Ihre Hash-Tabelle auf einem anderen O (1) Einfügen / Suchmechanismus fallen muss zurück auf meine Fragen zu beantworten. Welches, und warum nicht nur das direkt verwenden?

Beantwortet am 01/02/2009 um 13:49
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more