Balancieren eines Binärbaums (AVL)

Question

Ok, dies ist ein weiteres Beispiel aus dem Bereich der Theorie für die CS-Leute hier.

In den 90er Jahren war ich bei der Einführung von BST recht erfolgreich. Das Einzige, was ich nie in den Griff bekam, war die Komplexität des Algorithmus zum Ausgleich eines Binärbaums (AVL).

Könnt ihr mir dabei helfen?

Answer 1

Ich glaube nicht, dass es gut ist, vollständige Codes für Knotenausgleichsalgorithmen hier zu posten, da sie ziemlich groß werden. Allerdings ist der Wikipedia-Artikel über rot-schwarze Bäume enthält eine vollständige C-Implementierung des Algorithmus und den Artikel über AVL-Bäume hat ebenfalls mehrere Links zu hochwertigen Implementierungen.

Diese beiden Implementierungen sind für die meisten Allzweckszenarien ausreichend.

Answer 2

Ein Sündenbock-Baum ist möglicherweise der am einfachsten zu verstehende Algorithmus zur Bestimmung des Gleichgewichts. Wenn eine Einfügung dazu führt, dass der neue Knoten zu tief ist, findet er einen Knoten, um den herum er das Gleichgewicht wiederherstellt, indem er das Gewichtsgleichgewicht und nicht das Höhengleichgewicht betrachtet. Die Regel, ob bei einer Löschung ein Ausgleich vorgenommen werden soll, ist ebenfalls einfach. Sie speichert keine geheimnisvollen Informationen in den Knoten. Es ist schwieriger zu beweisen, dass sie korrekt ist, aber das braucht man nicht, um den Algorithmus zu verstehen...

Im Gegensatz zu einem RBL ist es jedoch nicht immer höhenbalanciert. Wie bei Rot-Schwarz ist die Unausgewogenheit begrenzt, aber im Gegensatz zu Rot-Schwarz ist sie mit einem Parameter einstellbar, so dass sie für die meisten praktischen Zwecke so ausgewogen aussieht, wie Sie es brauchen. Ich vermute jedoch, dass es bei einer zu engen Einstellung genauso schlecht oder schlechter als AVL für Worst-Case-Einfügungen ist.

Antwort auf Frage bearbeiten

Ich werde meinen persönlichen Weg zum Verständnis von RBL-Bäumen aufzeigen.

Zuerst müssen Sie verstehen, was eine Baumrotation ist, also ignorieren Sie alles andere, was Sie jemals über die RBL-Algorithmen gehört haben, und verstehen Sie das. Machen Sie sich klar, was eine Rechtsdrehung und was eine Linksdrehung ist und was beide mit dem Baum machen, sonst verwirren Sie die Beschreibungen der genauen Methoden nur.

Der Trick, um AVL-Bäume auszubalancieren, besteht darin, dass in jedem Knoten die Differenz zwischen der Höhe des linken und des rechten Teilbaums gespeichert wird. Die Definition von "Höhe ausgeglichen" ist, dass dies zwischen -1 und 1 für jeden Knoten im Baum liegt.

Wenn Sie nun einen Knoten hinzugefügt oder entfernt haben, kann es sein, dass Sie den Baum aus dem Gleichgewicht gebracht haben. Sie können jedoch nur das Gleichgewicht der Knoten verändern, die Vorfahren des hinzugefügten oder entfernten Knotens sind. Sie arbeiten sich also den Baum hinauf, indem Sie alle unausgewogenen Knoten, die Sie finden, mit Hilfe von Rotationen ausgleichen und ihren Gleichgewichtswert aktualisieren, bis der Baum wieder ausgeglichen ist.

Der letzte Teil des Verstehens besteht darin, in einem guten Nachschlagewerk die spezifischen Drehungen nachzuschlagen, die für die Neugewichtung jedes gefundenen Knotens verwendet werden: Das ist die "Technik" im Gegensatz zum eigentlichen Konzept. Man muss sich die Details nur merken, wenn man den AVL-Baumcode ändert oder vielleicht bei Prüfungen über Datenstrukturen. Es ist Jahre her, dass ich das letzte Mal AVL-Baumcode auch nur im Debugger geöffnet hatte - Implementierungen neigen dazu, einen Punkt zu erreichen, an dem sie funktionieren und dann auch zu bleiben. Ich kann mich also wirklich nicht erinnern. Man kann es mit ein paar Pokerchips auf einem Tisch ausrechnen, aber es ist schwer, sicher zu sein, dass man wirklich alle Fälle hat (es gibt nicht viele). Am besten ist es, einfach nachzuschlagen.

Dann geht es darum, das Ganze in Code zu übersetzen.

Ich glaube nicht, dass ein Blick auf die Codelisten in irgendeiner Phase sehr hilfreich ist, außer in der letzten, also ignorieren Sie sie. Selbst im besten Fall, wenn der Code klar und deutlich geschrieben ist, wird er wie eine Lehrbuchbeschreibung des Prozesses aussehen, nur ohne die Diagramme. Im typischeren Fall handelt es sich um ein Durcheinander von C-Strukturmanipulationen. Halten Sie sich also einfach an die Bücher.

Answer 3

Ich habe in letzter Zeit einige Arbeiten mit AVL-Bäumen durchgeführt.

Die beste Hilfe, die ich finden konnte, war eine Google-Suche, um herauszufinden, wie man sie ausgleicht.

Ich habe einfach um diesen Pseudocode herumgecodet (wenn man versteht, wie man Rotationen macht, ist es ziemlich einfach zu implementieren).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Answer 4

Ich stimme zu, dass ein vollständiges Programm nicht angemessen wäre.

Während die klassische AVL und der RB-Baum einen deterministischen Ansatz verwenden, würde ich vorschlagen, einen Blick auf " Zufallsgesteuerte binäre Suchbäume "die weniger kostspielig sind und unabhängig von der statistischen Verteilung der Schlüssel ein gutes Gleichgewicht garantieren.

Answer 5

Der AVL-Baum ist ineffizient, weil man pro Einfügung/Löschung potenziell viele Rotationen durchführen muss.

Der Rot-Schwarz-Baum ist wahrscheinlich eine bessere Alternative, da Einfügungen/Löschungen viel effizienter sind. Diese Struktur garantiert, dass der längste Pfad zu einem Blatt nicht mehr als das Doppelte des kürzesten Pfades beträgt. Damit ist er zwar weniger ausgewogen als ein AVL-Baum, aber die schlimmsten Fälle von Unausgewogenheit werden vermieden.

Wenn Ihr Baum viele Male gelesen und nach der Erstellung nicht mehr verändert wird, kann sich der zusätzliche Aufwand für einen vollständig ausgeglichenen AVL-Baum lohnen. Auch der Rot-Schwarz-Baum erfordert ein zusätzliches Bit an Speicherplatz für jeden Knoten, das die "Farbe" des Knotens angibt.