Université Batna 2 Module : ASDD3 Années : 2 Année Licence
TD N °4 : Les Arbres Binaires de recherches ABR
Exercice 1 :
Combien y a-t-il d’arbres binaires de recherche dont les éléments sont {3, 5, 8, 12}?
Exercice 2 :
On considère tous les nombres compris entre 1 et 1000. Donnez deux ordres d’insertion de ces nombres dans un
ABR :
– Un qui va donner un arbre complètement déséquilibré, c’est-à-dire de hauteur maximale possible ;
– Un qui va donner un arbre équilibré, c’est-à-dire le moins haut possible.
Exercice 3 :
- Insérer successivement les entiers 7, 2, 9, 0, 5, 6, 8 et 1 dans un arbre binaire de recherche initialement vide.
- Que devient cet arbre après suppression de 2 puis de 7 ?
Exercice 4 :
On suppose que les entiers compris entre 1 et 1000 sont disposés dans un arbre binaire de recherche, et on
souhaite retrouver le nombre 363. Parmi les séquences suivantes, lesquelles ne pourraient pas être la séquence
de nœuds parcourus ?
a) 2, 252, 401, 398, 330, 344, 397, 363 ;
b) 924, 220, 911, 244, 898, 258, 362, 363 ;
c) 925, 202, 911, 240, 912, 245, 363 ;
d) 2, 399, 387, 219, 266, 382, 381, 278, 363 ;
e) 935, 278, 347, 621, 299, 392, 358, 363.
* Est-il nécessaire de faire des schémas ? Écrire sous une forme minimale la propriété à vérifier.
Exercice 5 :
Q1) Donner la représentation sous forme d’arbre binaire de l’expression arithmétique suivante :
y = x+ (y+2) * z / (y+1)
Q2) Donner le résultat de parcours : préfixé, infixé et postefixé de l’arbre précédent.
Exercice 6 Arbres binaires
Considérer l’arbre suivant :
N Contenu [Link] [Link]
1 * 2 3
2 + 4 5
3 - 6 7
4 3 0 0
5 / 8 9
6 8 0 0
7 * 10 11
8 4 0 0
9 2 0 0
10 2 0 0
11 3 0 0
Université Batna 2 Module : ASDD3 Années : 2 Année Licence
TD N °4 : Les Arbres Binaires de recherches ABR
1- Dessiner cet arbre.
2- Quelle est la hauteur de l’arbre ?
3- Est-ce que cet arbre est un arbre strictement binaire, un arbre parfait (=complet) ?
4- Afficher cet arbre binaire de la manière préfix, puis infixe, et ensuite postfix.
Exercice 7 :
Soit l’Arbre binaire de recherche suivant :
1- On utilise un tableau T_ARB pour représenter cet arbre. Donner ce tableau.
2- Ajouter la valeur 115 à cet arbre. Quel est alors l’indice J du tableau tel queT_ARB[J]=115?
3- Quelle est la hauteur de cet arbre ?
4- Quelle est la taille de cet arbre ?
5- Dessiner l’arbre obtenu après suppression de 70 sur l’arbre initial.
Soit la procédure récursive suivante :
6- Donner la liste des valeurs obtenues en exécutant cette procédure sur l’arbre initial.
7- Comment modifier la procédure précédente pour obtenir la liste triée par ordre croissant?
Université Batna 2 Module : ASDD3 Années : 2 Année Licence
TD N °4 : Les Arbres Binaires de recherches ABR
Exercice1 :
Exercice2 :
– Pire ordre : 1 puis 2 puis 3 ... puis 1000.
Mais aussi : 1 puis 1000 puis 2 puis 999 puis 3... puis 500 puis 501.
– Meilleur ordre : on insere à chaque fois le mileu comme racine ; puis on recommence par récurrence.
Plusieurs racines possibles. On prend par exemple 512 pour avoir une meilleure récursion. Plusieurs ordres possibles :
– 512 256 128 64 32 16 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15 ... (correspond à une création en parcours préfixe)
– 512 256 768 128 384 640 896 64... (correspond à une création de haut en bas)
Exercice3 :
On remarque ci-dessous que l’on préserve mieux l’équilibre de l’arbre en alternant l’utilisation du prédécesseur
et du successeur. Une solution est de tirer au hasard celui que l’on utilise
Université Batna 2 Module : ASDD3 Années : 2 Année Licence
TD N °4 : Les Arbres Binaires de recherches ABR
Exercice4 :
Pour chaque séquence, il faut tenter de reconstituer le parcours dans l’ABR en vérifiant la propriété des ABR :
“pour tout nœud x, les clés du sous-arbre gauche sont inférieures à la clé de x, les clés du sous-arbre droit sont
supérieures à la clé de x”.
Pour les séquences 1, 2 et 4, c’est possible. Par contre pour les séquences 3 et 5, cela ne l’est pas.
Dans la séquence 3, la sous-séquence 911, 240, 912 est impossible, car 240 est nécessairement le fils
gauche de 911 et donc 912 appartient au sous arbre gauche de 911, ce qui est impossible dans un ABR.
Dans la séquence 5, la sous-séquence 347, 621, 299 est impossible, car 621 est nécessairement le fils
droit de 347 et donc 299 appartient au sous-arbre droit de 347, ce qui est impossible dans un ABR.
Finalement, en notant (xi) la suite des valeurs parcourues, il suffit de vérifier que :
Exercice5 :
Q1 :
Université Batna 2 Module : ASDD3 Années : 2 Année Licence
TD N °4 : Les Arbres Binaires de recherches ABR
Q2)
Représentation préfixé : = y + x * + y 2 / z + y 1
Représentation infixé : y = x + y + 2 * z / y + 1
Représentation postfixé : y x y 2 + z y 1 + / * + =
Q3)
Exercice 6 :
1- .
2- La hauteur de l’arbre est 3.
3- Cet arbre est strictement binaire car chaque nœud a zéro ou deux fils. Par contre, cet
arbre est ni parfait ni dégénéré (Un arbre binaire est dit dégénéré si chacun de ses nœuds a au plus un fils)
4- Préfix : * + 3 / 4 2 - 8 * 2 3.
Infixe 3 + 4 / 2 * 8 - 2 * 3
Postfix 3 4 2 / + 8 2 3 * - *
Université Batna 2 Module : ASDD3 Années : 2 Année Licence
TD N °4 : Les Arbres Binaires de recherches ABR
Exercice 7 :
1-.
2- .
115 devient le fils droit de 110. 110 est à la position 6 de T_ARB donc 115 sera à la position (2*6)+1 =13. On mettra donc
T_ARB[13] :=115.
3- Quelle est la hauteur de cet arbre ?
La hauteur est le plus long chemin entre la racine et une feuille. Ici, 4.
4- Quelle est la taille de cet arbre ?
On appelle taille d’un arbre le nombre de ses nœuds . Ici, 14.
5- Dessiner l’arbre obtenu après suppression de 70 sur l’arbre initial.
Selon le cours, on remplace 70 par le plus petit élément de son sous arbre droit :
Université Batna 2 Module : ASDD3 Années : 2 Année Licence
TD N °4 : Les Arbres Binaires de recherches ABR
On pourrait aussi supprimer70 et le remplacer par le plus grand élément de son sous arbre
gauche
6-Donner la liste des valeurs obtenues en exécutant cette procédure sur l’arbre
initial.
100-130-200-250-150-110-70-90-80-50-60-20-30
7) Comment modifier la procédure précédente pour obtenir la liste triée par
ordre croissant ?
Pour obtenir la liste triée par ordre croissant, il suffit de modifier la procédure lecture :
