Wann sollte man einen RB-Baum, einen B-Baum oder einen AVL-Baum wählen?

Wann sollte ich als Programmierer in Betracht ziehen, einen RB-Baum, einen B-Baum oder einen AVL-Baum zu verwenden? Was sind die wichtigsten Punkte, die berücksichtigt werden müssen, bevor Sie sich für eine Wahl entscheiden?

Kann jemand bitte mit einem Szenario für jede Baumstruktur erklären, warum sie in Bezug auf die wichtigsten Punkte gegenüber anderen ausgewählt wird?

Nehmen Sie dies mit einer Prise Salz:

B-Tree, wenn Sie mehr als Tausende von Elementen verwalten und diese von einer Festplatte oder einem langsamen Speichermedium aus pagen.

RB-Baum, wenn Sie häufig Bäume einfügen, löschen und abrufen.

AVL-Baum, wenn Ihre Einfügungen und Löschungen im Vergleich zu Ihren Abrufen selten sind.

Ich denke, B + -Bäume sind eine gute allgemeine geordnete Containerdatenstruktur, selbst im Hauptspeicher. Selbst wenn der virtuelle Speicher kein Problem darstellt, ist die Cache-Freundlichkeit häufig ein Problem, und B + -Bäume eignen sich besonders gut für den sequentiellen Zugriff - dieselbe asymptotische Leistung wie eine verknüpfte Liste, jedoch mit einer Cache-Freundlichkeit in der Nähe eines einfachen Arrays. All dies und O (log n) suchen, einfügen und löschen.

B + -Bäume haben jedoch Probleme - z. B. die Elemente, die sich beim Einfügen / Löschen innerhalb von Knoten bewegen und Zeiger auf diese Elemente ungültig machen. Ich habe eine Containerbibliothek, die "Cursor-Wartung" durchführt - Cursor hängen sich an den Blattknoten an, auf den sie derzeit in einer verknüpften Liste verweisen, sodass sie automatisch repariert oder ungültig gemacht werden können. Da es selten mehr als einen oder zwei Cursor gibt, funktioniert es gut - aber es ist trotzdem ein zusätzliches Stück Arbeit.

Eine andere Sache ist, dass der B + -Baum im Wesentlichen genau das ist. Ich denke, Sie können die Nicht-Blatt-Knoten entfernen oder neu erstellen, je nachdem, ob Sie sie benötigen oder nicht, aber mit binären Baumknoten erhalten Sie viel mehr Flexibilität. Ein Binärbaum kann in eine verknüpfte Liste und zurück konvertiert werden, ohne Knoten zu kopieren. Sie ändern lediglich die Zeiger und denken dann daran, dass Sie ihn jetzt als eine andere Datenstruktur behandeln. Dies bedeutet unter anderem, dass Sie eine ziemlich einfache O (n) -Zusammenführung von Bäumen erhalten - konvertieren Sie beide Bäume in Listen, führen Sie sie zusammen und konvertieren Sie sie dann wieder in einen Baum.

Eine weitere Sache ist die Speicherzuweisung und -freigabe. In einem Binärbaum kann dies von den Algorithmen getrennt werden - der Benutzer kann einen Knoten erstellen und dann den Einfügealgorithmus aufrufen, und Löschvorgänge können Knoten extrahieren (sie vom Baum trennen, aber den Speicher nicht freigeben). In einem B-Baum oder B + -Baum funktioniert das offensichtlich nicht - die Daten befinden sich in einem Knoten mit mehreren Elementen. Das Schreiben von Einfügemethoden, die den Vorgang "planen", ohne die Knoten zu ändern, bis sie wissen, wie viele neue Knoten benötigt werden und dass sie zugewiesen werden können, ist eine Herausforderung.

Rot schwarz gegen AVL? Ich bin mir nicht sicher, ob es einen großen Unterschied macht. Meine eigene Bibliothek verfügt über eine richtlinienbasierte "Tool" -Klasse zum Bearbeiten von Knoten mit Methoden für doppelt verknüpfte Listen, einfache Binärbäume, Spreizbäume, rot-schwarze Bäume und Treaps, einschließlich verschiedener Konvertierungen. Einige dieser Methoden wurden nur implementiert, weil ich mich zu der einen oder anderen Zeit gelangweilt hatte. Ich bin mir nicht sicher, ob ich die Treap-Methoden überhaupt getestet habe. Der Grund, warum ich rot-schwarze Bäume anstelle von AVL gewählt habe, ist, dass ich die Algorithmen persönlich besser verstehe - was nicht bedeutet, dass sie einfacher sind, es ist nur ein Zufall der Geschichte, dass ich sie besser kenne.

Eine letzte Sache - ich habe meine B + -Baumcontainer ursprünglich nur als Experiment entwickelt. Es ist eines dieser Experimente, die nie wirklich endeten, aber ich würde andere nicht ermutigen, es zu wiederholen. Wenn Sie nur einen geordneten Container benötigen, verwenden Sie am besten den Container, den Ihre vorhandene Bibliothek bereitstellt - z. B. std :: map usw. in C ++. Meine Bibliothek hat sich im Laufe der Jahre weiterentwickelt, es hat eine ganze Weile gedauert, bis sie stabil war, und ich habe erst vor relativ kurzer Zeit festgestellt, dass sie technisch nicht portierbar ist (abhängig von ein wenig undefiniertem WRT-Offset).

Im Speicher hat B-Tree den Vorteil, wenn die Anzahl der Elemente mehr als 32000 beträgt ... Schauen Sie sich speedtest.pdf von stx-btree an .

Bei der Auswahl von Datenstrukturen tauschen Sie Faktoren wie z

• Abrufgeschwindigkeit v Aktualisierungsgeschwindigkeit
• Wie gut die Struktur mit Worst-Case-Operationen zurechtkommt, z. B. das Einfügen von Datensätzen, die in einer sortierten Reihenfolge eintreffen
• Platz verschwendet

Ich würde damit beginnen, die Wikipedia-Artikel zu lesen, auf die Robert Harvey verweist.

Pragmatisch gesehen verwendet der durchschnittliche Programmierer bei der Arbeit in Sprachen wie Java tendenziell die bereitgestellten Sammlungsklassen. Wenn bei einer Aktivität zur Leistungsoptimierung festgestellt wird, dass die Erfassungsleistung problematisch ist, kann nach alternativen Implementierungen gesucht werden. Es ist selten das erste, was eine geschäftsorientierte Entwicklung berücksichtigen muss. Es ist äußerst selten, dass solche Datenstrukturen von Hand implementiert werden müssen. In der Regel können Bibliotheken verwendet werden.