Discussion :

[84mickael]

Bonjour,

Pour l'école j'ai fait l'implémentation des AVL, en Java. Chaque noeud contient une donnée "desequilibre" (= hauteur (filsGauche) - hauteur (filsDroit)).

Après une rotation droite, le déséquilibre de 2 noeuds (sommet et filsGauche qui deviennent respectivement filsDroit et sommet) est modifié. Je sais qu'il est possible de trouver grâce à une formule es nouvelles valeurs des déséquilibres. J'en ai trouvé une sur un site internet :



Celle-ci ne fonctionne pas chez moi, notamment car leur déséquilibre est égal à "filsDroit - filsGauche". J'ai essayé de la comprendre, de l'inverser mais le résultat reste faux.

Cela fait plusieurs heures que je manipule mes données dans tous les sens pour retrouver une formule cohérente avec mon implémentation... mais impossible d'y arriver. Si quelqu'un pouvait m'indiquer cette formule (dans un premier temps pour une rotation droite), et mieux, me l'expliquer... je lui en serai très reconnaissant.

Merci d'avance.

[84mickael]

Sans forcément passer par une formule, si quelqu'un connait la méthode efficace (pas de calcul de hauteur) pour recalculer les déséquilibres après une rotation, en analysant toutes les situations... je suis aussi preneur, car je n'y arrive vraiment pas.

Merci.

[84mickael]

Je pense avoir trouvé...

ROTATION GAUCHE :

(A) Sommet ==RG==> (A') FilsGauche
(B) FilsDroit ==RG==> (B') Sommet

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
A' = A + 1 - min(0, B)
B' = B + 1 + max(0, A')

ROTATION DROITE :

(A) Sommet ==RD==> (A') FilsDroit
(B) FilsGauche ==RD==> (B') Sommet

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
A' = A - 1 - max(0, B)
B' = B - 1 + min(0, A')

Je teste, ça a l'air de marcher...