Corrigé bref - UQAC

Corrigé en bref arbres AVL Rappels de cours : Si B est un arbre AVL et si on ajoute ou supprime un sommet à B, alors
- si cela ne provoque aucun déséquilibre, on a toujours un arbre AVL.
- sinon soit x le sommet le plus bas déséquilibré (i.e. de déséquilibre
2 ou -2):
- si x a un déséquilibre de 2 et est tel que son fils gauche
- a un déséquilibre de 1, alors une rotation rd(x,B) permet de
rééquilibrer l'arbre
- a un déséquilibre de -1, alors une rotation rgd(x,B) permet de
rééquilibrer l'arbre
- si x a un déséquilibre de -2 et est tel que son fils droit
- a un déséquilibre de -1, alors une rotation rg(x,B) permet de
rééquilibrer l'arbre
- a un déséquilibre de 1, alors une rotation rdg(x,B) permet de
rééquilibrer l'arbre
- pas d'autres cas possible. rd (rg) = rotation droite (gauche); rdg (rgd)= rotation droite gauche
(gauche droite).
Rotation droite
[pic]
Rotation gauche
[pic]
Rotation gauche droite
[pic]
Rotation droite gauche
[pic] A. Les AVL sont d'abord des arbres de recherche, ils sont donc tels que
tout n?ud a une clé supérieure à celles des n?uds de son sous arbre gauche
et inférieure à celles des n?uds de son sous arbre droit. De plus ils sont
H-équilibrés : en tout n?ud, la différence de hauteur entre les sous arbres
gauche et droit est au plus égal à 1. B. L'adjonction est d'abord une adjonction comme feuille dans l'arbre
binaire de recherche. Ensuite, il faut remonter le chemin depuis cette
feuille jusqu'à la racine pour corriger les déséquilibres. On ajoute 1 si
on remonte depuis la gauche et on retranche 1 si on remonte depuis la
droite. Si l'un d'eux devient ±2, on pratique une rotation «!ad hoc!». On
arrête la remontée si le déséquilibre est nul, puisque cela implique que la
hauteur de ce sous arbre n'a
pas changée. C. Il est essentiel de maintenir en permanence les déséquilibres des n?uds
de l'arbre au fur et à mesure des adjonctions. Si on ne le fait pas, on
risque de ne pas faire les corrections aux bons endroits. L'adjonction de
35 implique une rdg en 25. Celle de 5 implique une rd en 25. Celle de 20
une rgd en 35. Celle de 65 une rg en 35. Celle de 40 une rdg en 35. Celle
de 50 une rdg en 25.
Celle de 55 une rg en 45. D. Comme cela a été vu pour l'exercice sur les arbres binaires de
recherche, la liste infixée d'un AVL est une liste ordonnée. N'oublions pas
qu'un AVL est d'abord un arbre binaire de recherche. E. La suppression d'un n?ud est d'abord une suppression dans un arbre
binaire de recherche: localisation du n?ud, s'il a deux fils remplacement
de la valeur par celle qui est à l'extrémité du bord gauche du sous arbre
droit et le n?ud à supprimer est alors ce n?ud extrémité, et enfin
suppression du n?ud (initial ou extrémité) qui a au plus un fils en mettant
le sous arbre restant à sa place. Ensuite, on remonte le chemin depuis le
n?ud supprimé jusqu'à la racine en corrigeant les déséquilibres. On
retranche 1 si on remonte depuis la gauche et on ajoute 1 si on remonte
depuis la droite. Si l'un d'eux devient ±2, on pratique une rotation "ad
hoc". On arrête la remontée si le déséquilibre est différent de 0, puisque
cela implique que la hauteur de ce sous arbre n'a pas
changée. Notons qu'il peut y avoir plusieurs rotations à effectuer. F. La suppression de 45 conduit à un déséquilibre -2 sur 50, et donc une
rdg sur ce n?ud. Cette rotation conduisant à diminuer la hauteur de l'arbre
correspondant (le déséquilibre est nul), il faut poursuivre les corrections
au delà, ce qui conduit à un déséquilibre +2 sur 40, et donc une rgd sur ce
n?ud. G. La suppression de 30 conduit à son remplacement par 35, et la
suppression du n?ud où était 35. Le déséquilibre de 40 devient -2,
nécessitant une rg en 40.