Exercice sur les arbres AVL

Voici une liste aléatoire de 15 éléments. Notez que vous pouvez faire cet
exercice en prenant une autre liste aléatoire!; évidemment, il y a peu de chances
que vous obteniez le même résultat.

25  60   35   10   5   20   65   45   70   40   50   55   30   15

On s’intéresse aux arbres AVL.

A-Rappelez les propriétés des arbres AVL.
B-Rappelez ce qu’est l’opération d’adjonction dans un arbre AVL.
C-Construire l’arbre AVL par adjonction des valeurs successives, dans l’ordre de la liste. On s’attachera particulièrement à expliquer le raisonnement.
D-Donner la liste infixée de l’arbre obtenu, en justifiant votre raisonnement. Quelle propriété a-t-elle!? Est-ce toujours le cas!?
E-Rappelez ce qu’est l’opération de suppression.
F-Donner l’arbre obtenu par suppression de 45 dans l’arbre ci-dessous, en justifiant votre raisonnement.

G-Donner l’arbre obtenu par suppression de 30 dans l’arbre obtenu en F.

A. Les AVL sont d’abord des arbres de recherche, ils sont donc tels que tout noeud a une clé supérieure à celles des noeuds de son sous arbre gauche et inférieure à celles des noeuds de son sous arbre droit. De plus ils sont Héquilibrés, donc tels que en tout noeud, la différence de hauteur entre les sous
arbres gauche et droit est au plus de 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 noeuds 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 noeud est d’abord une suppression dans un arbre binaire de recherche!: localisation du noeud, 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 noeud à supprimer est alors ce noeud extrémité, et enfin suppression du noeud
(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 noeud 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 a 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 noeud. 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 noeud.

G. La suppression de 30 conduit à son remplacement par 35, et la suppression du noeud où était 35. Le déséquilibre de 40 devient –2, nécessitant une rg en 40.