Balancing ein Binary Tree (AVL)

StackOverflow https://stackoverflow.com/questions/133610

Frage

Ok, das ist eine andere, in der Theorie Reich für die CS Jungs um.

In den 90er Jahren ich ziemlich gut tat BST bei der Umsetzung. Das einzige, was ich konnte nie um meinen Kopf bekommen war die Kompliziertheit des Algorithmus ein Binary Tree (AVL).

zum Ausgleich

Könnt ihr mir helfen, auf das?

War es hilfreich?

Lösung

möglicherweise ein Sündenbock Baum hat den einfachste Balance-Bestimmungsalgorithmus zu verstehen. Falls eine Einfügung der neue Knoten verursacht zu tief sein, findet er einen Knoten, um die neu zu gewichten, um Gewichtsausgleich suchen, anstatt Höhe Balance. Die Regel für die, ob auf Löschen wieder im Gleichgewicht ist ebenfalls einfach. Es speichert keine obskuren Informationen in den Knoten. Es ist schwieriger zu beweisen, dass es korrekt ist, aber Sie nicht, dass müssen den Algorithmus verstehen ...

Im Gegensatz zu einem AVL es nicht höhen ausgewogen zu allen Zeiten. Wie Rot-Schwarz seine Unwucht begrenzt, aber im Gegensatz zu rot-schwarz, es ist abstimmbar mit einem Parameter, so dass für die meisten praktischen Zwecke sieht es so ausgewogen wie Sie es brauchen. Ich vermute, dass, wenn Sie stimmen sie zu fest, aber es endet als schlecht oder schlechter als AVL für Worst-Case-Einfügungen.

Antwort auf Frage bearbeiten

Ich werde meinen persönlichen Weg zum Verständnis der AVL-Bäume liefern.

Als erstes müssen Sie verstehen, was ein Baum dreht, so ignorieren alles, was Sie jemals die AVL-Algorithmen und zu verstehen, dass gehört habe. Erhalten Sie gerade in Ihrem Kopf, die eine Rechtsdrehung ist und eine linke Drehung, und was jeder tut, um den Baum, oder auch die Beschreibungen der genauen Methoden werden Sie nur verwirren.

Als nächstes wird verstehen, dass der Trick für den Ausgleich AVL-Bäume ist, dass jeder Knoten Datensätze in ihm die Differenz zwischen der Höhe seiner linken und rechten Teilbäume. Die Definition von ‚Höhe ausgewogen‘ ist, dass dies zwischen -1 und 1 inklusive für jeden Knoten im Baum.

Als nächstes wird verstehen, dass, wenn Sie hinzugefügt haben, oder einen Knoten entfernt, Sie unausgewogen den Baum haben. Aber man kann nur haben, das Gleichgewicht der Knoten geändert, die Vorfahren des Knotens hinzugefügt oder entfernt werden. Also, was du gehst, ist Ihr Weg zu tun, arbeiten wieder auf den Baum, keine unausgeglichenen Knoten balancieren Drehungen mit Ihnen finden, und ihre Balance Score zu aktualisieren, bis der Baum wieder ausgeglichen wird.

Der letzte Teil des Verstehens es die spezifischen Drehungen in einem anständigen Referenz verwendet zu sehen ist, jeden Knoten neu zu gewichten Sie finden: Das ist die „Technik“ es ist in Bezug auf die hohe Konzept entgegengesetzt. Sie müssen nur noch die Details erinnern, während AVL-Baum-Code zu ändern oder vielleicht während der Datenstrukturen Prüfungen. Es ist Jahre her, seit ich das letzte Mal im Debugger AVL-Baum-Code, so viel wie offen hatte - Implementierungen zu einem Punkt bekommen neigen, wo sie arbeiten und dann bleiben arbeiten. Also wirklich, ich kann mich nicht erinnern. Sie können sortieren sie von Arbeit auf einem Tisch ein paar Poker-Chips verwenden, aber es ist schwer, um sicherzustellen, dass Sie wirklich alle Fälle haben (es gibt nicht viele). Beste nur um es zu sehen.

Dann gibt es das Geschäft alles in Code zu übersetzen.

Ich glaube nicht, dass bei der Code mich sehr hilft bei jeder Stufe mit Ausnahme der letzten, so ignorieren sie. Selbst im besten Fall, in dem der Code eindeutig geschrieben wird, wird es wie ein Lehrbuch Beschreibung des Prozesses aussehen, aber ohne die Diagramme. In einem typischen Fall ist es ein Durcheinander von C struct Manipulation. Halten Sie sich also nur auf die Bücher.

Andere Tipps

Ich glaube nicht, ist es gut, komplette Codes für Knoten-Balancing-Algorithmen um eine Nachricht schreiben, da sie ziemlich groß werden. Allerdings ist der Wikipedia-Artikel über rot-schwarze Bäume eine komplette C-Implementierung des Algorithmus enthält und der Artikel über AVL Bäume auch mehrere Links zu qualitativ hochwertigen Implementierungen hat.

Diese beiden Implementierungen sind genug für die meisten Allzweck-Szenarien.

Ich habe in letzter Zeit einige Arbeit mit AVL-Bäumen zu tun.

Die beste Hilfe ich in der Lage war zu finden, wie sie zum Ausgleich war über Google zu suchen.

ich um diesen Pseudo-Code nur codiert (wenn Sie verstehen, wie Drehungen zu tun, 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
  }
}

Ich bin damit einverstanden, ein komplettes Programm nicht angemessen wäre.

Während klassische AVL und RB Baum einen deterministischen Ansatz verwenden, würde ich vorschlagen, einen Blick haben bei " Randomisierte binäre Suchbäume „, die weniger kostspielig sind im Gleichgewicht zu halten und einen guten Ausgleich unabhängig von der statistischen Verteilung der Tasten zu gewährleisten.

Der AVL-Baum ist ineffizient, weil Sie möglicherweise viele Umdrehungen pro Einfügen / Löschen zu tun haben.

Der Rot-Schwarz-Baum ist wahrscheinlich eine bessere Alternative, da Einfügungen / Löschungen viel effizienter sind. Diese Struktur gewährleistet der längste Weg zu einem Blatt ist nicht mehr als zweimal der kürzeste Weg. Während also weniger ausgeglichen als ein AVL-Baum, die schlimmsten unausgeglichen Fälle vermieden werden.

Wenn Ihr Baum wird viele Male gelesen werden, und wird nicht verändert, nachdem es erstellt wird, kann es den zusätzliche Aufwand für einen vollständig ausgewogenen AVL-Baum wert sein. Auch der Rot-Schwarz-Baum erfordert eine zusätzliche Bit Speicher für jeden Knoten, die dem Knoten des „Farbe“ geben.

einen AVL-Baumes Zum Ausgleich Ich schrieb eine Reihe von Funktionen, die ich dachte, hier mit jedem teilen. Ich denke, diese Implementierung ist einwandfrei. Anfragen / Fragen / Kritik sind natürlich willkommen:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

ein Anfänger zu sein Stackoverflow, versuchte ich meinen Code hier veröffentlichte, war aber mit schlechten Formatierungsproblemen stecken. So hochgeladen die Datei auf dem obigen Link.

Prost.

gibt es eine vollständige Implementierung eines Selbstausgleich avl Baum @ http: // code.google.com/p/self-balancing-avl-tree/ . es setzt auch logarithmische Zeit verketten und Split-Operationen sowie eine Karte / multimap Sammlungen

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top