Domaine Sciences et Technologies
Licence 3 Informatique
Algorithmique 2 : TD 7
Code UE : SIN4U04L
Année 2024-25 Dictionnaires
Exercice 1 (Arbres binaires de recherche)
(a) Construire un arbre binaire de recherche en insérant successivement, à partir de l’arbre
vide, les entiers de 1 à 7.
(b) Dans quel ordre insérer les éléments de 1 à 7 pour obtenir un arbre de hauteur minimale ?
Plusieurs ordres sont-ils possibles ?
(c) Quel est le nombre maximum de nœuds d’un arbre binaire de hauteur h ?
(d) Donner des bornes inférieures et supérieures sur la profondeur du nœud le plus profond
d’un arbre binaire à n éléments.
(e) L’arbre ci-dessous est-il un arbre binaire de recherche (pour les entiers, avec la comparaison
usuelle) ? Si besoin, le corriger en modifiant les valeurs d’un nombre minimum de nœuds.
12
7 19
2 9 15 23
11 14 17 26
(f) Illustrer l’algorithme de suppression, en supprimant le nœud de valeur 19.
Exercice 2 (AVL-arbres)
(a) Construire un AVL-arbre en partant de l’arbre vide et en ajoutant successivement les
éléments 51, 44, 32, 26, 17, 59, 23, 21, et enfin 24.
(b) L’arbre de gauche ci-dessous est-il un AVL-arbre ? Justifier votre réponse.
8 8
2 10 3 10
1 6 9 12 2 6 9 12
4 7 11 13 1 5 7 11 13
3 5 4
(c) Supprimer l’élément 3 de l’AVL-arbre de droite ci-dessus en utilisant l’algorithme vu
en cours.
(d) Quel est le nombre maximum de nœuds dans un AVL-arbre de hauteur n ?
Exercice 3 (Arbres rouge-noir)
Les arbres rouge-noirs sont une des nombreuses autres structures de données concrètes
implémentant des arbres binaires de recherche équilibrés, avec des performances similaires aux
AVL-arbres. Plutôt que de garder dans chaque nœud la hauteur du sous-arbre correspondant,
nous ajoutons juste une simple information de couleur : un nœud peut être ou rouge, ou noir
(blanc ou noir sur les dessins).
Bien sûr, il nous faut des propriétés additionnelles pour pouvoir équilibrer les arbres, en plus
des propriétés des arbres binaires de recherche. Les voici :
(1) Tout chemin entre la racine et un nœud vide contient le même nombre de nœuds noirs.
(2) Le parent d’un nœud rouge, s’il existe, est un nœud noir.
(a) Les arbres suivants sont-ils des arbres rouge-noirs valides ? Justifier votre réponse.
21 15
8 23 8 18
5 13 29 5 11 16 20
3 6 11 15 24 31 2 7 9 14
18 13
13 23
5 15 20 29
3 10 24 31
6 12
(b) Si T a n nœuds noirs, combien peut valoir au maximum le nombre r de nœuds rouges
dans T ?
(c) Soit hn (T ) le nombre de nœuds noirs d’un chemin de la racine à une feuille d’un arbre
rouge-noir T . Donner une borne sur le nombre minimum de nœuds (noirs ou rouges) dans
T , en fonction de hn (T ).
(d) Quelle est la hauteur maximum h d’un arbre rouge-noir, en fonction de hn (T ) ?
(e) En déduire que l’opération recherche dans un arbre rouge-noir a une complexité de O(log n),
où n est le nombre de nœuds.
(f) Pour coder l’insertion, nous sommes confrontés au problème suivant : g et d sont deux arbres
avec hn (g) = hn (d) + 1, et e est un élément tel que le nœud (g, e, d) forme un arbre binaire
de recherche. Malheureusement, que ce nouveau nœud soit rouge ou noir, la propriété (1)
sera violée. Trouver un moyen de rétablir l’invariant à l’aide de rotations.
Exercice 4 (Tables de hachage)
Voici un ensemble de valeurs que nous devons stocker, ainsi que leur image par quatre fonctions
de dispersion vers l’intervalle J0, 7K.
h1 h2 h3 h4
congre 1 3 0 7
daurade 4 3 7 6
grondin 6 7 6 3
lotte 6 5 4 3
merlan 2 2 3 4
rascasse 4 7 6 6
saint-pierre 1 5 1 3
vive 6 3 4 6
(a) Construire la table de dispersion de taille 8 par chaı̂nage pour ces valeurs en utilisant h1
puis en utilisant h4 .
(b) Construire la table coucou de taille 8 pour ces valeurs en utilisant h1 et h2 , puis en utilisant
h3 et h4 .
