Woher weißt du, wo Rotationen in einem AVL-Baum durchgeführt werden sollen?

So, ich bin selbst Lehr-AVL-Bäume, und ich verstehe die Grundidee dahinter, aber ich will nur sichergehen, dass meine intuition in die Tat umzusetzen es gilt:

Werde ich überprüfen Sie mit der Links-rotation-

So, folgende situation ist einfach:

Wenn wir die 3, den Baum wieder ins Gleichgewicht selbst zu:

Aber ist die rotation auf der Grundlage der addition der 3 oder das Ungleichgewicht der Teilbaum verwurzelt in 7? Ist es auch basiert auf dem Ungleichgewicht der Baum verwurzelt an 8?

Folgenden Beispiel ist, wo die Dinge erhalten ein wenig haarig, meiner Meinung nach:

So, in diesem Fall, den Teilbaum unter 7 ist gut, wenn die 3 Hinzugefügt, so dass Teilbaum braucht nicht zu rotieren. Aber der Baum bei 9 ist unausgewogen mit dem Zusatz von 3, so dass wir der Basis die Drehung am 9. Wir erhalten:

Also schriftlich mein code, den ich ziemlich bald, würden Sie den folgenden code, beginnend von kleinen unterstrukturen arbeiten bis zu größeren teilbäumen den trick tun?

pseudocode:

function balanceTree(Node n){

  if (n is not null){

    balanceTree(n.rightchild);
    balanceTree(n.leftchild);
  }

  if (abs(balanceFactor(n))>1){

    rotateAsNeeded(n);//rotate based on balance factor

  }

}

Vielen Dank im Voraus!

InformationsquelleAutor der Frage Skorpius | 2013-06-21

33

Den pseudocode, die du gepostet hast richtig die balance eines Baumes. Das heißt, es ist zu ineffizient, um praktisch zu sein - merken, dass Sie sich rekursiv erkunden, den gesamten Baum zu tun versuchen rebalancing-Operationen, der alle Einfügungen und Löschungen nehmen O(n) Zeit, frisst alle Effizienzgewinne mit einer ausgewogenen Struktur.

Die Idee hinter den AVL-Bäumen ist, dass Global Neugewichtung der Baum kann getan werden, indem iterativ anwenden lokalen Rotationen. In anderen Worten, wenn Sie eine Einfügung oder Löschung und tun müssen-Baum-Rotationen, diese Drehungen nicht erscheinen in zufälligen stellen in der Struktur. Sie werden immer erscheinen an den access-Pfad, den Sie nahm, beim einfügen oder löschen von Knoten.

Zum Beispiel, dass Sie neugierig über das einfügen der Wert 3 in diesem Baum:
```
      9
     /\
    7   10
   /\
  6   8
```
Let ' s start off durch das schreiben, den Unterschied in der balance-Faktoren, die mit jedem Knoten (es ist wichtig, dass die AVL-Baum-Knoten, die diese Informationen speichern, da es ist, was es möglich macht, zu tun, Einfügungen und Löschungen effizient):
```
           9(+1)
         /      \
       7 (0)    10 (0)
      /\
  6(0)   8(0)
```
So, jetzt lasst uns sehen, was passiert, wenn wir einfügen 3. Dies stellen die 3 hier:
```
           9(+1?)
          /      \
        7 (0?)    10 (0)
       /  \
   6(0?)   8(0)
   /
 3(0)
```
Beachten Sie, dass ich ' ve markiert alle Knoten, die auf den Zugriff auf Pfad mit einem? da sind wir nicht mehr sicher, was Ihre balance-Faktoren sind. Da wir fügten ein neues Kind für 6, dadurch ändert sich die balance-Faktor für die 6-Knoten +1:
```
           9(+1?)
          /      \
        7 (0?)    10 (0)
       /  \
   6(+1)   8(0)
   /
 3(0)
```
Ähnlich, der linke Teilbaum von 7 wuchs in die Höhe, so seine Bilanz Faktor sollte erhöht werden:
```
           9(+1?)
          /      \
        7 (+1)    10 (0)
       /  \
   6(+1)   8(0)
   /
 3(0)
```
Schließlich 9 ist der linke Teilbaum gewachsen, womit sich das:
```
           9(+2!)
          /      \
        7 (+1)    10 (0)
       /  \
   6(+1)   8(0)
   /
 3(0)
```
Und hier finden wir, dass 9 hat ein balance-Faktor von +2, was bedeutet, dass wir tun müssen, um eine rotation. Beratung Wikipedia ist toll-Tabelle der AVL-Baum-Rotationenkönnen wir sehen, dass wir in dem Fall, wo wir ein Gleichgewicht haben-Faktor von +2, wenn das linke Kind hat eine balance-Faktor von +1. Dies bedeutet, dass wir eine rechts-Drehung und ziehen Sie die 7 über 9, wie hier gezeigt:
```
        7(0)
       /  \
   6(+1)     9(0)
   /      /  \
 3(0)    8(0)   10 (0)
```
Et voilà! Der Baum ist jetzt ausgeglichen.

Beachten Sie, dass, wenn wir haben diese Korrektur Verfahren, die wir nicht haben, um über den gesamten Baum. Stattdessen wird alles, was wir tun mussten, war Blick entlang der access-Pfad und überprüfen Sie jeden Knoten gibt. In der Regel, wenn die Implementierung eines AVL-Baumes, Ihre Eingabe zu Verfahren folgende Schritte aus:
- Wenn der Baum null ist:
  - Sie den Knoten mit balance-Faktor zu 0.
  - Zurück, dass die Baum-Höhe hat sich um 1 erhöht.
- Ansonsten:
  - Wenn der einzufügende Wert entspricht dem aktuellen Knoten, nichts zu tun.
  - Ansonsten rekursiv einfügen der Knoten in den richtigen Teilbaum und erhalten die Menge, die der Baum-Höhe hat sich geändert.
  - Update des balance-Faktors dieses Knotens auf der Grundlage der Betrag, den der Teilbaum der Höhe verändert werden.
  - Wenn diese Mandate eine Reihe von Drehungen, die Sie ausführen.
  - Zurück die sich daraus ergebende änderung in der Höhe des Baumes.
Da alle diese Operationen sind lokal, die gesamte Arbeit basiert ausschließlich auf der Länge der Zugang-Pfad, in diesem Fall ist O(log n), da AVL-Bäume immer ausgeglichen.

Hoffe, das hilft!

PS: Dein erste Beispiel war dieser Baum:
```
      8
     /\
    7   10
   /
  6
 /
3
```
Beachten Sie, dass dieser Baum nicht wirklich eine rechtliche AVL-Baum, da der balance-Faktor des root-Knoten +2. Wenn Sie konsequent Baum Gleichgewicht mit der AVL-Algorithmus, werden Sie nie begegnen diesem Fall.

InformationsquelleAutor der Antwort templatetypedef

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.