Als Programmierer wann sollte ich einen RB-Baum, B-Baum oder einen AVL-Baum verwenden? Was sind die wichtigsten Punkte, die berücksichtigt werden müssen, bevor über die Wahl entschieden wird?Wann wählen Sie RB-Baum, B-Baum oder AVL-Baum?
Kann jemand bitte mit einem Szenario für jede Baumstruktur erklären, warum es über andere mit Bezug auf die Schlüsselpunkte gewählt wird?
Nehmen Sie dies mit einer Prise Salz:
B-Baum, wenn Sie mehr als Tausende von Produkten verwalten und Sie sie von einer Diskette oder einem langsamen Speichermedium Paging.
RB-Baum, wenn Sie ziemlich häufige Einfügungen, Löschungen und Abfragen auf dem Baum tun.
AVL-Struktur, wenn Ihre Einfügungen und Löschungen relativ zu Ihren Abfragen selten sind.
Nur um einige Details hinzuzufügen: B-Bäume können variable Anzahl von Kindern haben, die es erlauben, viele Datensätze zu halten, aber immer noch einen Baum mit kurzer Höhe. Der RB-Baum hat weniger strenge Regeln für das Rebalancing, die Einfügungen/Löschungen schneller machen als der AVL-Baum. Umgekehrt ist der AVL-Baum strenger ausbalanciert, so dass Nachschlagevorgänge schneller als RB-Baum sind. – pschang
RB-Bäume haben auch eine bessere Leistung O (1) bei der Neuverteilung, was sie für dauerhafte Datenstrukturen mit Roll-Back und Roll-Forward geeigneter macht. –
Wenn Datenstrukturen wählen Sie handeln aus Faktoren wie
ich durch das Lesen der Wikipedia-Artikel verwiesen von Robert Harvey beginnen würde.
Pragmatisch neigt der durchschnittliche Programmierer beim Arbeiten in Sprachen wie Java dazu, die bereitgestellten Klassen zu verwenden. Wenn bei einer Leistungsoptimierungsaktivität festgestellt wird, dass die Sammelleistung problematisch ist, kann nach alternativen Implementierungen gesucht werden. Es ist selten das Erste, was eine geschäftliche Entwicklung berücksichtigen muss. Es ist extrem selten, dass man solche Datenstrukturen von Hand implementieren muss, es gibt normalerweise Bibliotheken, die verwendet werden können.
Um fair zu sein, fragte das OP: "Wann sollte ich die Verwendung in Erwägung ziehen?" Und nicht "Wann sollte ich die Umsetzung in Betracht ziehen?". Während der letzte Absatz wahr ist, liefert er im Zusammenhang mit dieser Frage keinen großen Wert. Auch bei Bibliotheken müssen Sie die Algorithmen verstehen, um effektiv die Struktur auszuwählen, die am besten zu Ihren Geschäftsanforderungen passt. – Dan
Ich denke, B + Bäume sind eine gute allgemeine Zweck geordnet Container Datenstruktur, auch im Hauptspeicher. Selbst wenn virtueller Speicher kein Problem ist, ist Cache-Freundlichkeit oft, und B + -Bäume sind besonders gut für sequentiellen Zugriff - die gleiche asymptotische Leistung wie eine verkettete Liste, aber mit Cache-Freundlichkeit nahe bei einem einfachen Array. All dies und O (log n) suchen, einfügen und löschen.
B + Bäume haben jedoch Probleme - wie die Elemente innerhalb von Knoten bewegt, wenn Sie fügt/löscht, Zeiger auf diese Elemente ungültig. Ich habe eine Container-Bibliothek, die "cursor maintenance" ausführt - Cursor fügen sich selbst an den Blattknoten an, auf den sie in einer verknüpften Liste verweisen, so dass sie automatisch repariert oder ungültig gemacht werden können. Da es selten mehr als ein oder zwei Cursor gibt, funktioniert es gut - aber es ist trotzdem ein bisschen mehr 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 nur die Zeiger und denken daran, dass Sie sie jetzt als eine andere Datenstruktur behandeln. Unter anderem bedeutet dies, dass Sie ganz einfach O (n) zusammenführen können - konvertieren Sie beide Bäume in Listen, fusionieren Sie sie und konvertieren Sie sie wieder in einen Baum.
Noch eine Sache ist Speicherzuweisung und Freigabe.In einem Binärbaum kann dies aus den Algorithmen herausgelöst werden - der Benutzer kann einen Knoten erstellen und dann den Einfügealgorithmus aufrufen, und Löschvorgänge können Knoten extrahieren (sie aus dem Baum lösen, aber den Speicher nicht freigeben). In einem B-Baum oder B + -Baum funktioniert das offensichtlich nicht - die Daten werden in einem Knoten mit mehreren Elementen gespeichert. Schreib-Einfügemethoden, die die Operation "planen", ohne Knoten zu modifizieren, bis sie wissen, wie viele neue Knoten benötigt werden und dass sie zugewiesen werden können, ist eine Herausforderung.
Rot schwarz vs. 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, Splay-Bäume, Rot-Schwarz-Bäume und Treaps, einschließlich verschiedener Konvertierungen. Einige dieser Methoden wurden nur implementiert, weil mir irgendwann langweilig war. Ich bin mir nicht sicher, ob ich die Treap-Methoden überhaupt getestet habe. Der Grund, warum ich Rot-Schwarz-Bäume statt AVL gewählt habe, liegt darin, dass ich persönlich die Algorithmen besser verstehe - was nicht bedeutet, dass sie einfacher sind, es ist nur ein Zufall der Geschichte, dass ich mit ihnen vertrauter bin.
Eine letzte Sache - Ich habe meine B + Baumbehälter ursprünglich nur als Experiment entwickelt. Es ist eines dieser Experimente, die nie wirklich beendet wurden, aber ich ermutige andere nicht dazu, es zu wiederholen. Wenn alles, was Sie benötigen, ein bestellter Container ist, ist die beste Antwort diejenige, die Ihre vorhandene Bibliothek bereitstellt - z. std :: map usw. in C++. Meine Bibliothek hat sich über Jahre entwickelt, es hat eine ganze Weile gedauert, bis sie stabil war, und ich habe erst vor relativ kurzer Zeit entdeckt, dass sie technisch nicht portabel ist (abhängig von etwas undefiniertem Verhalten WRT offset).
Im Speicher B-Tree hat den Vorteil, wenn die Anzahl der Elemente mehr als 32000 ist ... Betrachten Sie speedtest.pdf von stx-btree.
Nun, ich für meinen Teil schätze diese Frage - derzeit präsentiert mit einer Auswahl von fastutil IntAVLTreeSet vs IntRBTreeSet. – Yang