Ich habe die article von Steve Yegge über Singletons gelesen. Darin erwähnt er, dass sein Lehrer ihm sagte, AVL Trees sei böse. Ist es nur, dass rote und schwarze Bäume eine bessere Lösung sind?Sind AVL Trees Evil?
Böse von welchem Standpunkt?
Wie immer: Es gibt keine schlechten Werkzeuge, nur schlechte Handwerker.
In meinem Gedächtnis haben AVL-Bäume langsamere Einfügung/Entfernung, aber schnelleres Wiederauffinden als Rot/schwarz. Hauptsächlich wegen des Balance-Algorithmus.
Genau. Wenn Sie eine Karte zum einmaligen Schreiben benötigen, um viele zu lesen, sind AVL-Bäume schwer zu schlagen. Meiner Meinung nach sind sie auch leichter zu implementieren. – erickson
Eine einmal beschreibbare Karte liest sich für mich eher nach einem sortierten Array ... Eine Karte mit Schreibzugriff - selten gelesen - viel klingt mehr als ein AVL-Baum. Stellen Sie sicher, dass Sie auch in diesen Fällen ein sortiertes Array berücksichtigen. Die konstanten Kosten sind erheblich niedriger, so dass Sie viele Einträge benötigen, bevor ein AVL-Tree sowohl den Rot/Schwarz-Baum als auch ein sortiertes Array übertrifft. –
AVL-Bäume sind jedoch in hohem Maße nachvollziehbar. IME, RB-Bäume werden von ihren Machern nicht verstanden - sie befolgen lediglich die Regeln; Sie verstehen wirklich nicht, was konzeptionell vor sich geht. –
Nein, AVL-Bäume sind in keiner Hinsicht böse. Sie sind eine vollständig gültige selbstbalancierende Baumstruktur. Sie haben andere Leistungsmerkmale als rot-schwarze Bäume und diese Unterschiede führen dazu, dass die Menschen einen rot-schwarzen Baum über einen AVL-Baum wählen. Aber das macht sie nicht böse.
Ich bin sicher, dass AVL-Bäume auf die gleiche Weise böse sind, wie GOTO böse ist oder BUBBLE SORT ist böse.
Algorithmen sind nicht böse, aber Algorithmen springen auch nicht auf und ab, um Ihnen zu sagen, wann sie angemessen sind.
Goto ist kein Algorithmus und ist wirklich kein legitimer Vergleich. – Imagist
Das Problem w/bubble sort ist, dass es keine echten Kompromisse gibt, die es überlegen machen. Das kann man für AVL-Bäume nicht sagen. –
:: snark :: Bubble sort verwendet sehr wenig Code und lässt sich leicht in einer traditionellen Turing-Maschine realisieren. – dmckee
Splay Trees sind viel kühler. :)
Nein, sie sind nicht böse, nur ein bisschen schwierig zu programmieren.
AVL Bäume http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Rot Schwarz Baum Link auch dort aus.
Hier ist eine Menge Informationen über die Unterschiede zwischen Rot-Schwarz und AVL-Bäume:
http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948
und ein Papier zu vergleichen die unterschiedlichen Strukturen:
http://www.stanford.edu/~blp/papers/libavl.pdf
Kurz - AVL ist schneller zu suchen, Rot-Schwarz schneller einzufügen.
Die Fogcreek-Verbindung ist schlecht. Der Inhalt ist irreführend. AVL-Bäume benötigen keine O (log n) -Drehungen für das Rebalancing. Max 2. – Jesse
OP rep von 666 bestätigt AVL Trees sind böse – SwDevMan81
Ich denke nicht, dass wir diese Frage dann aufwerten können? ;) –