Exercice 1 : (Représentation d’un tas en tableau)
A) Donner la représentation de l’arbre suivant dans un tableau (en suivant les règles de construction d’un tas sous forme de tableau):
Solution :
Les règles pour représenter un tas sous format d’un tableau sont comme suit :
- La racine est à la première position du tableau avec l’indice 1 (le premier indice du tableau n’est pas 0 comme pour le C/C++).
- Chaque fils gauche d’un nœud doit être à la position 2*i de l’indice du père. Par exemple, si le père est à l’indice 3, son fils gauche est à l’indice 6 du tableau.
- Chaque fils droite d’un nœud doit être à la position 2*i+1 de l’indice du père. Par exemple, si le père est à l’indice 3, son fils droite est à l’indice 7 du tableau.
- Si on applique les règles précédentes sur un arbre donné, et on ne trouve pas de case vide dans le tableau, alors l’arbre en question a la structure d’un tas.
A) En appliquant les règles précédentes sur l’arbre, on obtient le tableau suivant :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| A | B | C | E | F | G | H | I | J |
B) On peut voir que les cases avec l’indice 4, 8,9 et 12 sont vides, donc on peut constater que l’arbre ne peut pas être un tas.
Remarque 1 : Un tas est considéré comme un arbre binaire parfait. Donc par définition, c’est un arbre dans lequel tous les niveaux sont remplis, 1-niveau avec 1 nœud, 2-niveau avec 2 nœuds, 3-niveau avec 4 nœuds, 4-niveau avec 8 nœuds…etc. Sauf, le dernier qui doit seulement être rempli de gauche à droite.
Remarque 2 : Visuellement, il est très facile de distinguer un tas, dans le sens où tous les niveaux sont pleins, il n’y a pas de vide dans les niveaux. Sauf le dernier, qui est rempli de gauche à droite. Pour le transcrire en tableau l’opération est très simple, il suffit d’écrire chaque niveau de l’arbre l’un après l’autre dans le tableau. C’est comme si vous êtes en train de transcrire l’arbre de gauche à droite sur une seule ligne.
Exercice 2 : (Algorithmes et complexité d’un tas)
Avec le TAS max suivant :
A) Ajouter l’élément de priorité 15 (dessiner tous les arbres intermédiaires jusqu’à l’arbre final)
B) Donner l’algorithme (idée générale ou pseudo-code) d’Ajout d’un élément.
C) Retirer un élément « Suppression« .
D) Donner l’algorithme (idée générale ou pseudo-code) de retrait d’un élément
E) Estimer la complexité des algorithmes de l’Ajout et la Suppression dans un tas.
F) Déduire la complexité des algorithmes d’Ajout et de Suppression dans une file d’attente (FIFO) avec priorité.
Solution :
Le tas est une structure de données utilisée pour 2 principaux algorithmes : Algorithme de Tri (ce n’est pas le cas pour cet exercice), ou une file (FIFO) à priorité, dans laquelle la valeur maximale est en tête de file lors de l’opération Défiler, pour le tas max. Pour le tas min c’est l’inverse, c’est la valeur minimale qui se trouve en tête de file.
Deux conditions sont nécessaires pour concevoir un tas :
- Le tas doit être un arbre binaire parfait.
- Quelque soit un nœud dans le tas ses fils doivent obligatoirement être plus petits que leur père, pour le tas max. Et inversement pour le tas min, les fils doivent être plus grands que le père.
A) Ajouter l’élément de priorité 15
Étape 1 : (Insérer l’élément 15 au dernier niveau le plus à gauche)
Étape 2 : (Permuter élément 15 avec son père si l’élément est plus grand que le père)
Étape 3 : (Permuter élément 15 avec son père si l’élément est plus grand que le père)
Étape 4 : (S’arrêter si l’élément 15 est inférieur à son père)
B) L’algorithme pour ajouter un élément au tas :
- Créer un nœud et lui donner la valeur à ajouter.
- Insérer le nœud à la dernière position du tas, ça veut dire tout au dernier niveau le plus à gauche.
- Permuter avec la valeur du père tant que le père est supérieur à la valeur insérée pour le tas max. Ou au contraire, tant que le père est inférieur à la valeur insérée pour le tas min.