1 Corrigé de l’examen de Structures de données du 8 février 2003 Exercice 1 Que
1 Corrigé de l’examen de Structures de données du 8 février 2003 Exercice 1 Question A Un arbre AVL est un arbre binaire de recherche qui est H-équilibré. Un arbre binaire de recherche est tel que la clé de tout nœud est plus grande que toutes les clés des nœuds de son sous arbre gauche et plus petite que toutes les clés des nœuds de son sous arbre droit. Un arbre binaire est H-équilibré si en tout nœud, la différence de hauteur entre les sous arbres gauche et droit est au plus de 1. On peut constater sur l’arbre donné qu’il s’agit bien d’un arbre binaire de recherche, et que de plus il est H- équilibré. On peut le décorer avec les déséquilibres (-, =, +). Question B L’adjonction dans un arbre AVL consiste d’abord à faire une adjonction d’une feuille dans un arbre binaire de recherche, en recherchant l’endroit où doit être le nœud en tant que feuille. Pour cela, partant de la racine, on descend dans l’arbre, à gauche ou à droite, selon que la clé de l’élément ajouté est inférieure ou supérieure à la clé du nœud, jusqu’à rencontrer un arbre vide qui est remplacé par un nouveau nœud contenant l’élément ajouté. Ensuite, on remonte le chemin vers la racine, en corrigeant les déséquilibres (+1 si on remonte depuis la gauche et –1 si on remonte depuis la droite), en vérifiant que le résultat reste dans les limites (-1, 0 ou +1) et en pratiquant la rotation adaptée si ce n’est pas le cas. Dans tous les cas, on arrête la remontée et les corrections lorsque le déséquilibre résultant est nul. Question C On part de l’arbre ci-dessus, pour ajouter d’abord 50. 50 étant plus grand que 35, on descend à droite. 50 étant plus petit que 60 on descend à gauche. 50 est plus grand que 45 on descend à droite. 50 est plus petit que 55 on descend à gauche. On est sur un arbre vide qui est donc remplacé par le nœud 50, fils gauche de 55. Ceci porte le 2 déséquilibre de 55 à +1, celui de 45 à –1, et celui de 60 à +2. Il faut alors pratiquer une rotation gauche-droite puisque le déséquilibre de 45 est –1. Ceci met 55 à la place de 60 avec un déséquilibre nul!; la remontée est donc terminée, et on obtient l’arbre ci-dessous. Pour ajouter 25 dans ce nouvel arbre, 25 étant plus petit que 35, on descend à gauche. 25 étant plus grand que 10 on descend à droite. 25 étant plus grand que 20 on descend à droite. 25 étant plus petit que 30 on descend à gauche. On est sur un arbre vide qui est donc remplacé par le nœud 25, fils gauche de 30. Ceci porte le déséquilibre de 30 à +1, celui de 20 à –1 et celui de 10 à –2. Il faut alors pratiquer une rotation à gauche puisque le déséquilibre de 30 est –1. Ceci met 20 à la place de 10 avec un déséquilibre nul!; la remontée est terminée et on obtient l’arbre ci-dessous. Question D La liste infixée de l’arbre initial est obtenu en mettant chaque nœud après la liste infixée de son sous arbre gauche et avant la liste infixée de son sous arbre droit. On obtient la liste ci-dessous, qui est ordonnée pour un arbre binaire de recherche. 5, 10, 15, 20, 30, 35, 40, 45, 55, 60, 65 Question E L’opération de suppression consiste d’abord à rechercher le nœud à supprimer. Pour cela, partant de la racine, on descend dans l’arbre, à gauche ou à droite, selon que la clé de l’élément recherché est inférieure ou supérieure à la clé du nœud, jusqu’à trouver le nœud. Si ce nœud a deux fils, on remplace la valeur par celle qui est à l’extrémité du bord gauche du sous arbre droit, et c’est ce dernier nœud qui est supprimé. La suppression du nœud consiste ensuite à raccrocher le sous arbre éventuellement existant (gauche ou droit) à sa place. Ensuite, on remonte le chemin vers la racine, en corrigeant les déséquilibres (-1 si on remonte depuis la gauche et +1 si on remonte depuis la droite), en vérifiant que le résultat reste dans les limites (-1, 0 3 ou +1) et en pratiquant la rotation adaptée si ce n’est pas le cas. Dans tous les cas, on arrête la remontée et les corrections lorsque le déséquilibre résultant est non nul. Question F La suppression de 20 dans l’arbre donné, consiste d’abord à le rechercher. 20 étant plus petit que 25, on descend à gauche. 20 étant plus grand que 15 on descend à droite. On est alors sur le nœud, qui est simplement supprimé, puisqu’il n’a pas de fils. Le déséquilibre de 15 devient +2, ce qui nécessite une rotation à droite puisque le déséquilibre de 10 est +1. Le déséquilibre résultant étant nul, il faut poursuivre la remontée. Le déséquilibre de 25 devient –2, ce qui demande une rotation à gauche puisque le déséquilibre de 40 est –1. On obtient ainsi l’arbre suivant. Question G La suppression de 40 dans l’arbre donné, consiste d’abord à le rechercher. 40 étant plus grand que 25, on descend à droite. On est sur le nœud qui a deux fils. On remplace la valeur par celle située à l’extrémité du bord gauche du sous arbre droit, c’est-à-dire, 45, et on supprime ce nœud. Le déséquilibre de 50 devient –2, ce qui nécessite une rotation à gauche, puisque le déséquilibre de 55 est –1. Le déséquilibre résultant étant nul, il faut poursuivre la remontée. Le déséquilibre de 45 devient nul, et celui de 25 également. Comme on est à la racine, on s’arrête. Exercice 2 Question A En fait l’opération de recherche proposée ici est analogue à la recherche si une liste est une sous liste d’une autre avec en plus l’information sur la position où se trouve 4 cette sous liste. On peut donc s’inspirer de l’exercice correspondant (cf. 15.7 du livre). Question A.1 Lors de l’appel de Recherche (De => L2, Dans => L1), on va donc comparer les 3 éléments de la liste L2 avec les portions de la liste L1 de même longueur, et commencant en 1, puis 2, puis 3, etc. jusque 8, où l’on constatera l’égalité. La valeur retournée sera donc 8. Lors de l’appel de Recherche (De => L3, Dans => L1), on va donc comparer les 4 éléments de la liste L3 avec les portions de la liste L1 de même longueur, et commencant en 1, puis 2, puis 3, etc. jusque 10, (ou 13 éventuellement). A chaque fois, on constatera l’inégalité, et donc à la fin l’exception Erreur_Specification sera levée. Il est certain que la chaîne «!SFIO!» est bien dans le tableau de la liste L1, mais elle est au delà de la fin de la liste, donc elle ne fait pas partie de la liste. Question A.2 On va faire une fonction interne qui contrôle l’égalité de la liste De avec la portion de la sous liste Dans commencant en position En. function Recherche (De, Dans: Texte) return Positive is function Egalite (Decalage: Natural) return Boolean is begin for I in 1..Longueur (De) loop if Ieme (De, I) /= Ieme (Dans, I + Decalage) then return False!; end if!; end loop!; return True!; end Egalite!; for J in 0..Longueur (Dans) – Longueur (De) loop if Egalite (J) then return 1 + J; end if!; end loop!; raise Erreur_Specification!; end Recherche!; Soient n la longueur de la liste De et m la longueur de la liste Dans. 1. Si De est sous liste de Dans, au mieux on le constatera au premier appel de Egalite. Il y aura alors n comparaisons. Au pire, on le constatera à la fin, c’est- à-dire lors du (m-n+1)ème appel de Egalite, les précédents ayant échoués. La complexité au pire est donc en Q(n*(m-n)). En moyenne, on peut dire qu’il y a (m- n)/2 appels de Egalite, chacun d’eux demandant n/2 comparaisons, donnant une complexité en moyenne de Q(n*(m-n)). 2. Si De n’est pas dans Dans, il faudra appliquer Egalite (m-n) fois. Chacun de ces appels demande au mieux 1 comparaison, au pire n, et en moyenne n/2. 5 On constate donc que cet algorithme a une complexité en moyenne et au pire en Q(n*(m-n)). Question B La suppression des espaces qui se suivent est analogue à la procédure Unique sur une liste ordonnée, lorsqu’on supprime un élément de la liste lorsqu’il est égal à celui qui le précède (cf. exercice 16.3 question A du livre). Question B.1 Le résultat de Supprimer_Les_Espaces_Inutiles (L1) est sans effet sur la liste L1. En effet, dans la portion du tableau qui est la représentation de la liste, il n’y a pas deux espaces qui se suivent. Le seul endroit du tableau où ceci se présente est en dehors de la liste. Question B.2 Deux méthodes peuvent être envisagées. La première, simple, utilise l’opération Supprimer des listes. Elle uploads/S4/ ex03-1-corrige.pdf
Documents similaires
-
13
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jui 22, 2022
- Catégorie Law / Droit
- Langue French
- Taille du fichier 0.1959MB