AVL-Baum der balance

Implementierte ich ein AVL-Baum, aber ich habe ein problem.

Angenommen, ich habe folgenden Baum:

AVL-Baum der balance

Und nach hinzufügen weiterer Knoten:

AVL-Baum der balance

Nun muss ich drehen, knoten5 nach Links:

AVL-Baum der balance

Aber nach der rotation, ist es immer noch unsymmetrisch.

Wo bin ich einen Fehler zu machen?

  • Es erfordert eine doppelte Drehung, drehen 11 und dann 5.
  • Danke, dass wusste ich nicht. ich lese wikipedia-Artikel, aber ich verstehe nicht sehr gut wie Sie, um zu bestimmen, Doppel-Drehung erneut abgefragt. Können Sie erklären, es in einer einfachen Art und Weise?
  • BTW 7 gezogen werden sollte, in den rechten Knoten.
  • Warum? es ist weniger als 10, und ich denke, es muss auf der linken Seite.
  • LOL! Ich weiß es nicht 10. Ich dachte, es ist 1. (mit einem Punkt) Sorry!
  • Und auch für Persisch 😉

InformationsquelleAutor MRB | 2013-10-09
  1. 19

    Das Vorgestellte Szenario entspricht der Rechts-Links - Fall von Wikipedia Beschreibung.

    Dein Fehler ist, dass Sie drehen Sie die unbalancierte Knoten (5) auf einmal, ohne zunächst die Durchführung einer rotation der sub-Baum.

    Im Allgemeinen mit P als der unausgeglichene Knoten L als der linke Unterbaum und R als dessen Rechte sub-Baum die folgenden Regeln sollten befolgt werden bei der insertion:

    balance(N) = Depth(Nleft) - Depth(Nright)

if (balance(P) > 1)  //P is node 5 in this scenario
{
    if (balance(L) < 0)
    {
        rotate_left(L);
    }

    rotate_right(P);
}
else if (balance(P) < -1) //P is node 5 in this scenario
{
    if (balance(R) > 0)  //R is node 11 in this scenario
    {
        rotate_right(R); //This case conforms to this scenario
    }

    rotate_left(P);      //... and of course this, after the above
}

    So manchmal zwei Rotationen durchgeführt werden müssen, und manchmal nur eine.

    Das ist schön visualisiert Wikipedia:

    AVL-Baum der balance

    In der oberen Zeile zeigt Situationen, wenn zwei Rotationen nötig sind. Die mittlere Zeile zeigt die möglichen Szenarien, wenn eine Drehung ist ausreichend. Zusätzliche Rotationen transformieren die top-row-Szenario für die Mitte-row-Szenario.

    Insbesondere für diesen Baum:

    AVL-Baum der balance

    Nach 7 Hinzugefügt:

    AVL-Baum der balance

    Das Gleichgewicht der 5 ist 2. Dies entspricht dem Szenario mit einem Kommentar markiert oben im pseudo-code und auch die top-row-Szenario (das auf der rechten Seite) in dem Wikipedia-Bild. Also, bevor 5 Links gedreht, seinen rechten Teilbaum 11 muss rechts gedreht:

    AVL-Baum der balance

    Und es wird:

    AVL-Baum der balance

    Nur jetzt, es ist der einfache Fall (mittlere Reihe rechts Szenario, in dem Wikipedia-Bild), um das Gleichgewicht wiederherzustellen, auf 5 durch eine Links-rotation:

    AVL-Baum der balance

    Und der Baum wird wieder ausgeglichen:

    AVL-Baum der balance

    InformationsquelleAutor BartoszKP
  2. 0

    Lassen Sie mich versuchen zu analysieren, umfassender,
    Für einen binären Baum avl-Baum der Höhe Unterschied, dass jeder Knoten von jedem linken Blatt nicht das Recht-die meisten Blatt liegen muss, innerhalb von { -1, 0, 1}.

    Insertion für AVL:

    Gibt es vier Fälle für die AVL-einfügen-
    L - L
    L - R
    R - R
    R - L

    Nun,
    Fall (a). [wenn das Gleichgewicht > 1] L-L(Links - left) Ein Knoten X gegen die { -1, 0, 1} constraint-und
    hat Links Höhe mehr als Recht - gibt, die zuerst nach Links von L
    hat eine linke sub-Kind Y dessen linke Höhe ist größer als die Rechte .. wieder L
    Aktion - Drehen um Y im Uhrzeigersinn. dh. eine Drehrichtung rechts.

    Fall (b) (L -R-Fall)Angenommen, einige Z-Knoten eingefügt werden, Z, wird es zuerst ausgewertet, bei denen Blatt, Links oder rechts, es ist platziert. Richtig, wenn mehr Gewicht nach Links, wenn weniger Gewicht.
    sagen,' Z', neue Knoten, wt(Z') > wt(Z), dh, Z' eingesetzt ist als Rechte Kind von Z, bei L - R, den ganzen link ZZ wird gegen den Uhrzeigersinn gedreht, jetzt ist es L-L Fall-und damit gelöst mit oben genannten Fall (a). dh. man nach Links und dann eine rechts-Drehung.

    Fall (c) [wenn-balance < -1] (R - R Fall) Auch R - R Fall, wenden Sie einfach den binary-search-Regel für Einstellungen, und in diesem Fall funktioniert. dh. eine Drehrichtung Links.

    Fall (d) (R - L Fall) Es ist die erste umgebaute R-R-Fall und damit gelöst mit oben genannten Fall (c). dh. eine rechts und dann eine Links-rotation.

    InformationsquelleAutor hi.nitish
Schreibe einen Kommentar