AVL arbres solde

Le scénario présenté est conforme à la Droite-Gauche cas de cet Wikipedia description.

Votre erreur, c'est que vous faites pivoter le déséquilibre de nœud (5) à la fois, sans d'abord effectuer une rotation de son sous-arbre.

En général avoir P que le déséquilibre du nœud, L comme sa gauche du sous-arbre et R que son droit de sous-arbre, les règles suivantes doivent être suivies au moment de l'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
}

Donc parfois deux rotations doivent être effectuées, et parfois un seul.

C'est bien visualisée à Wikipédia:

La ligne du haut montre des situations quand les deux rotations sont nécessaires. La rangée du milieu présente les scénarios possibles lors d'une rotation est suffisante. Supplémentaires à des rotations de transformer n'importe quel haut de la ligne de scénario pour le moyen-ligne de scénario.

En particulier, pour cet arbre:

Après 7 est ajouté:

L'équilibre de 5 est 2. Ceci est conforme au scénario marqué avec un commentaire ci-dessus dans le pseudo-code et aussi pour le haut de la ligne de scénario (celui de droite) dans le Wikipedia de l'image. Donc, avant de 5 est à gauche-rotation, de son droit de sous-arbre 11 doit être à droite-rotation:

Et il devient:

Seulement maintenant, c'est le cas simple (de mi-ligne droite scénario dans le Wikipedia image) pour rétablir l'équilibre à 5 par un gauche-rotation:

Et l'arbre devient équilibrée:

OriginalL'auteur BartoszKP