|
|
Examinons un sous arbre de racine le plus
jeune antécédent qui devient non équilibré suite à une insertion. Prenons
le cas où le facteur d'équilibrage est 1 pour ce jeune antécédent. La figure
suivante illustre ce cas.
|
|
A désigne le plus jeune antécédent devenu
non équilibré. Puisque f(A)=1, son sous arbre gauche est non NIL. Soit donc B
le fils gauche. f(B) doit donc avoir la valeur 0. Ce nœud B devait avoir avant
l'insertion des sous arbres (droit et gauche) la même profondeur, soit h=n.
Puisque f(A)=1, le sous arbre de A doit aussi avoir h=n.
Deux
cas sont à considérer figure a) et b) :
Dans
a), le nouveau nœud est inséré dans le sous arbre gauche de B. Donc f(B)
devient 1 et f(A) devient 2.
Dans b), le nouveau nœud est inséré dans le sous arbre droit de B. f(B)
devient -1 et f(A) devient 2.
Afin de maintenir l'arbre binaire équilibré,
il est nécessaire de transformer l'arbre de telle sorte que :
(i) -l'inordre soit préservé.
(ii) -l'arbre transformé
soit équilibré.
1. Si
une rotation droite est faite sur le sous arbre de racine A dans la figure a),
on obtient l'arbre a) suivant qui respecte (i) et (ii).
|
|
2.
Considérons la figure b) dans laquelle le nouveau nœud est inséré dans le
sous arbre droit de B. Soit C le fils droit de B. Trois cas peuvent se présenter:
- C est le nouveau nœud créé.
- le nœud créé est dans le sous gauche de C.
- le nœud créé est dans le sous arbre droit de C.
La figure b) illustre le cas où le nouveau nœud
est dans le sous arbre gauche de C. Si on fait une rotation gauche du sous arbre
de racine B suivie par une rotation droite du sous arbre de racine A on obtient
l'arbre b) qui respecte (i) et(ii).
Le raisonnement est le même pour le cas où
le facteur d'équilibrage est -1.
