Wann wählen Sie RB-Baum, B-Baum oder AVL-Baum?
Als Programmierer, als sollte ich in Erwägung ziehen, ein RB-Baum, B - Baum oder AVL-Baum?
Was sind die wichtigsten Punkte, die berücksichtigt werden muss vor der Entscheidung über die Wahl?
Kann mir bitte jemand erklären, mit einem Szenario für jede Struktur, warum es gewählt, über andere, mit Verweis auf die wichtigsten Punkte?
InformationsquelleAutor der Frage Palladin | 2009-10-19
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Nehmen Sie diese mit einer Prise Salz:
B-Baum, wenn Sie die Verwaltung mehr als Tausende Gegenstände und du bist paging Sie von einer Diskette oder einer langsamen Speichermedium.
RB-Baum, wenn du tust, eine relativ häufige Einfügungen, Löschungen und-Abrufe auf dem Baum.
AVL-Baum, wenn Ihr Einfügungen und Löschungen sind selten in Bezug auf Ihre Abfragen.
InformationsquelleAutor der Antwort blwy10
Denke ich, dass B+ - Bäume sind eine gute Allzweck-bestellt-container-Datenstruktur, sogar im Hauptspeicher. Auch wenn der virtuelle Speicher ist nicht ein Problem, cache-Freundlichkeit oft ist, und B+ - Bäume sind besonders gut für sequentiellen Zugriff auf das gleiche asymptotische Leistung als eine verknüpfte Liste, aber mit cache-Freundlichkeit der Nähe ein einfaches array. All dies und noch O(log n) suchen, einfügen und löschen.
B+ - Bäume Probleme haben, obwohl - wie die beweglichen Gegenstände, um innerhalb von Knoten, wenn Sie tun, fügt/löscht, der Aufhebung von Zeigern auf die Elemente. Ich habe eine container-Bibliothek, das tut "cursor Wartung" - Cursor hängen sich an den Blatt-Knoten, mit dem Sie derzeit die Referenz in einer verknüpften Liste, so dass Sie behoben werden kann oder automatisch ungültig. Da es selten mehr als ein oder zwei Cursor, es funktioniert gut - aber es ist ein bisschen Arbeit, alle gleich.
Andere Sache ist, dass der B+ - Baum ist im Grunde nur, dass. Ich denke, Sie können abzustreifen, oder erstellen Sie die nicht-Blatt-Knoten, je nachdem, ob Sie Sie brauchen oder nicht, aber mit binären Baum Knoten erhalten Sie viel mehr Flexibilität. Einen binären Baum umgewandelt werden können, um eine verknüpfte Liste und wieder zurück, ohne Sie zu kopieren Knoten - ändern Sie einfach den Zeiger dann denken Sie daran, dass Sie die Behandlung als eine andere Daten-Struktur jetzt. Unter anderem bedeutet dies, dass Sie relativ einfach O(n) Zusammenführen von Bäumen - konvertieren Sie beide Bäume zu Listen, verschmelzen Sie, und wandeln Sie dann wieder an einen Baum.
Noch eine andere Sache ist die Speicherreservierung und zu befreien. In einem binären Baum, diese können abgetrennt werden, aus der algorithmen - der Benutzer kann ein Knoten erstellt wird, dann rufen Sie die insert-Algorithmus, und löscht extrahieren können Knoten (trennen Sie von dem Baum, aber nicht den Speicher frei). In einem B-Baum oder B+-Baum, das offensichtlich nicht funktioniert - die Daten werden live in einem multi-Element-Knoten. Schreiben einfügen von Methoden, die den "plan" den Vorgang ohne ändern von Knoten, bis Sie wissen, wie viele neue Knoten benötigt werden, und dass Sie zugeordnet werden können, ist eine Herausforderung.
Rot schwarz vs. AVL? Ich bin mir nicht sicher, es macht keinen großen Unterschied. Meine eigene Bibliothek hat ein policy-basiertes "tool" - Klasse zur Bearbeitung von Knoten, die mit Methoden für doppelt verketteten Listen, einfache binäre Bäume, splay-Bäume, rot-schwarz-Bäume und treaps, einschließlich der verschiedenen Konvertierungen. Einige dieser Methoden wurden nur durchgeführt, weil ich gelangweilt war, zu einer Zeit oder einem anderen. Ich bin mir nicht sicher, ich habe die auch getestet, die treap-Methoden. Der Grund, warum ich wählte rot-schwarz-Bäume, anstatt AVL ist, denn ich persönlich verstehe die algorithmen besser - was nicht bedeutet, Sie sind einfacher, es ist nur ein Zufall der Geschichte, dass ich mehr bin mit Ihnen vertraut.
Eine Letzte Sache - ich habe nur ursprünglich entwickelte ich ein B+ - Baum-Container als experiment. Es ist eines dieser Experimente, die nie zu Ende geht wirklich, aber es ist nicht etwas, ich würde andere ermutigen, zu wiederholen. Wenn alles, was Sie brauchen, ist ein bestellter container, die beste Antwort ist es, die eine, dass Sie Ihre vorhandenen Bibliothek bietet - z.B. std::map etc in C++. Meine Bibliothek entwickelte sich im Laufe der Jahre, es dauerte eine ganze Weile, um es stabil, und ich habe gerade vor kurzem entdeckt, es ist technisch nicht tragbar (abhängig von etwas Undefiniertes Verhalten WRT offsetof).
InformationsquelleAutor der Antwort Steve314
In Gedächtnis-B-Baum hat den Vorteil, wenn die Anzahl der Elemente ist mehr als 32000... Sehen speedtest.pdf von stx-btree.
InformationsquelleAutor der Antwort stan5
Bei der Auswahl Daten-Strukturen, Sie handeln aus Faktoren wie
Ich würde anfangen, durch das Lesen der Wikipedia-Artikel verwiesen wird, die von Robert Harvey.
Pragmatisch, wenn arbeiten in Sprachen wie Java ist der Durchschnittliche Programmierer neigt dazu, verwenden Sie den collection-Klassen zur Verfügung gestellt. Wenn in einer performance-tuning-Aufgabe entdeckt man, dass die Sammlung die Leistung problematisch ist, dann kann man versuchen alternative Implementierungen. Es ist selten das erste, was ein business-led-Entwicklung ist zu berücksichtigen. Es ist extrem selten, dass man muss, um solche Datenstrukturen von hand, es sind in der Regel Bibliotheken, die verwendet werden können.
InformationsquelleAutor der Antwort djna