[PDF] Les arbres binaires de recherche PDF td

Exercice 3 Écrire une fonction Hauteur(x) prenant un arbre binaire et rendant sa hauteur, c'est à dire le nombre d'éléments

Exercice 1 Définir une structure struct noeud_s permettant de coder un n÷ud d' un arbre binaire contenant une valeur entière Ajouter des typedef pour définir

[PDF] Exercice sur les arbres binaires de recherche

A-Rappelez les propriétés des arbres binaires de recherche B-Rappelez ce qu' est l'opération d'adjonction aux feuilles C-Construire l'arbre binaire de recherche

[PDF] SUJET + CORRIGE

Exercice 1 : ABR : algorithmes et complexités (20 points) Rappels : Les Arbres Binaires de Recherche (ABR) sont des arbres binaires qui satisfont la propriété

[PDF] Les arbres binaires de recherche

Exercice 3 Écrire une fonction Hauteur(x) prenant un arbre binaire et rendant sa hauteur, c'est à dire le nombre d'éléments

[PDF] TP 10 Arbres binaires de recherche - Normale Sup

Exercice 1 Définir une structure struct noeud_s permettant de coder un n÷ud d' un arbre binaire contenant une valeur entière Ajouter des typedef pour définir

[PDF] Travaux Dirigés Exercices corrigés sur les arbres

Solution de l'exercice 1 1 Exercices corrigés sur les arbres Soit le tableau suivant qui représente un arbre binaire T en triplets (info, gauche, droit) :

[PDF] TD : Arbres Binaires de Recherche (ABR) - ISIMA

Les exercices sont inspirés de [1] Dans toute la suite nous supposerons qu'un arbre binaire de recherche self est construit récursivement par l'utilisation de

[PDF] TD5 : Arbres Binaires

Tout noeud du sous-arbre gauche de N a une valeur inférieure à n Exercice 4 Écrire la fonction qui vérifie si un arbre donné est bien un arbre binaire de

[PDF] TD No3

Exercice 1 arbres binaires Exercice 2 arbres binaires de recherche Dessinez l'arbre binaire de recherche obtenu par ajout successif aux feuilles des

[PDF] TD7

Cette séance de Travaux dirigée est consacrée à l'étude du type de donnée arbre binaire Exercice 1 (Arbres binaires) 1 Implanter la spécification ABin en

[PDF] exercice corrigé arbre rouge et noir

[PDF] arbre binaire de recherche en c

[PDF] les arbres en c openclassroom

[PDF] arbre binaire de recherche algorithme

[PDF] arbre binaire de recherche algorithme suppression

[PDF] parcours en profondeur arbre

[PDF] arbre binaire complet

[PDF] dénombrement cours

[PDF] arbre de probabilité pile ou face

[PDF] arbre de probabilité seconde

[PDF] arbre probabilité conditionnelle

[PDF] arbre de décision exercices corrigés

[PDF] arbre de décision data mining

[PDF] cours arbre de décision

[PDF] classification par arbre de décision

Institut GaliléeAlgorithmique et arbres

Année 2010-2011L2

TD 6

Les arbres binaires de recherche

Type en C des arbres binaires (également utilisé pour les ABR) : typedef struct noeud _s { struct noeud _s*parent; struct noeud _s*gauche; struct noeud _s*droite; element _t e; *ab_t,*abr_t;

Exercice 1.

Combien y a t"il de formes d"arbres binaires différents à (respectivement)1,2,3,4noeuds? Les dessiner (sans donner de contenu aux noeuds). Pournfixé quelconque donner un exemple d"arbre binaire de hauteur majorée parlogn+ 1, et un exemple d"arbre binaire de hauteurn.

Exercice 2.

Écrire une fonctionTaille(x)prenant un arbre binaire et rendant le nombre de ses éléments.

Exercice 3.

Écrire une fonctionHauteur(x)prenant un arbre binaire et rendant sa hauteur, c"est à dire le nombre d"éléments contenus dans la plus longue branche.

Exercice 4.

Dans les deux exemples d"arbres binaires de recherche de la figure 1 :

1. où peut-on insérer un élément de clé 13?

2. comment peut-on supprimer l"élément de clé 14?

12 3 25
14 15 14 5 29
18 1519

Figure 1:Deux arbres binaires de recherche

Les rotations des arbres binaires sont données dans la figure 2. Elles se lisent comme ceci. Une rotation à droite de centrexconsiste en : prendre l"élémentadex, le sous-arbre droite Edex, la racineydu sous-arbre gauche dex, l"élémentbcontenu dansy, etCetDles deux sous-arbres gauche et droite dey; remplaceraparbdansx, remplacer le sous-arbre gauche de xparC, et le sous-arbre droite dexpar un arbre de racine contenanta(on utiliseypour des raisons d"implantation) et dont les sous-arbres gauche et droite sont respectivementDetE. La rotation à gauche de centrexest l"opération réciproque.

Avec cette manière d"écrire les rotations la référence dexà son parent n"a pas besoin d"être

mise à jour. Il est assez standard de trouver une version qui échange la place dexet deyplutôt

que d"échanger leurs éléments mais nous ne l"utilisons pas ici.

3. Sur le premier exemple de la figure 1, faire : une rotation à droite de centre le noeud de

clé 3; puis une rotation à gauche de centre le noeud de clé 14. 1 a b CD E b Ca DE rotation_droite(x) rotation_gauche(x)yx yx

Figure 2:Rotations gauche et droite. Dans cette version les élémentsaetbsont échangés entre

les noeudsxetymaisxgarde sa place dans l"arbre qui le contient.

4. Sur le second exemple de la figure 1, à l"aide de rotations dont vous préciserez le sens et le

centre, amener le noeud de clé 9 à la racine.

5. Démontrer que toute rotation préserve la propriété d"être un arbre de recherche.

6. Écrire l"algorithme de rotation à droite enC.

7. Écrire un algorithme permettant de remonter à la racine n"importe quel noeud d"unarbre

binaire de recherche, à l"aide de rotations.

Exercice 5(Insertion / suppression ABR).

Former un arbre binaire de recherche en insérant successivement et dans cet ordre les élé-

ments :10,7,3,9,11,5,6,4,8(répondre en représentant l"arbre obtenu). Supprimer l"élément7.

(répondre en représentant le nouvel arbre. Il y a deux réponses correctes possibles,selon la

variante choisie pour l"algorithme de suppression, n"en donner qu"une seule).

31,5 pt13 min

Exercice 6(À la fois ABR et tas?).

Un tas est nécessairement un arbre binaire quasi-parfait. Est-il toujours possible d"organiser un ensemble denclés (nquelconque) en tas max de manière à ce que cet arbre binaire soit aussi un arbre binaire de recherche? (Justifier par un raisonnement ou un contre-exemple).

21,5 pt9 min

Exercice 7.

On peut afficher les éléments d"un ABR de taillenen ordre trié en un tempsO(n).

1. Expliquer comment et argumenter sur le temps d"exécution.

2. Est-ce que la propriété de tas permet d"afficher en ordre trié et en tempsO(n)les éléments

d"un tas de taillen? Argumenter. Indication : on peut planter(former) un tas denéléments en un tempsΘ(n). 2

CorrigéCorrection de l"exercice 1.

Un seul arbre à un noeud, deux à deux nøeuds :

Cinq à trois noeuds :

Quatorze arbres à quatre noeuds (non dessinés). On peut le calculer en trouvant la récurrence :

C n+1=n? k=0C k×Cn-k Qui donne iciC4=C0×C3+C1×C2+C2×C1+C3×C1= 5 + 2 + 2 + 5 = 14. (nombres de

Catalan).

Pournfixé l"arbre quasi-parfait ànnoeuds est tel que si sa hauteur esthalors : 2 L"arbre peigne est quand à lui exactement de hauteurn.

Correction de l"exercice 2.

int taille(ab _t x) { if (estVide(x)) { return 0; return 1 + taille(gauche(x)), taille(droite(x));

Correction de l"exercice 3.

void hauteur(ab _t x) { if (estVide(x)) { return 0; return 1 + max(hauteur(gauche(x)), hauteur(droite(x)));

Correction de l"exercice 4.

L"insertion est donnée par les figures 3 et 4.

La suppression est donnée par les figures 5 et 6.

1. Figure 7.

2. rotation à gauche de centre 5, puis rotation à droite de centre 14.

3 12 3 25
14 1315
Figure 3:Un arbre binaire de recherche -corrigé 14 5 29
13 18 1519
Figure 4:Un autre arbre binaire de recherche -corrigé

3. Il faut montrer la préservation de la propriété d"arbre de recherche. Onse contente de

montrer que si l"arbre à gauche de la figure est un arbre binaire de recherche alors l"arbre à droite en est un,et réciproquement. En effet, pour l"arbre qui contient l"un de cesdeux arbres comme sous-arbre, le fait de remplacer l"un par l"autre ne fait aucune différence : les deux sous-arbres ont mêmes ensembles d"éléments. Pour chacun des deux arbres de la figure on montre qu"être un arbre de recherche, sous l"hypothèse queC,DetEen sont, cle(e), ce qui conclue.

4./*Rotations :

x -> a ---rot. droite de centre x--> b <- x b E <--rot. gauche de centre x--- C a

C DD E

void rotation _droite(ab_t x){ element _t tmp; ab _t y; assert(x && x->gauche); y = x->gauche; *échange des éléments*/ tmp = x->e; x->e = y->e; 4 12 3 25
15 Figure 5:Un arbre binaire de recherche -corrigé B 15 5 29
18 19 Figure 6:Un autre arbre binaire de recherche -corrigé B y->e = tmp; *déplacement des sous-arbres*/ x->gauche = y->gauche; y->gauche = y->droite; y->droite = x->droite; x->droite = y; *mise à jour des parents*/ (x->gauche)->parent = x; (y->droite)->parent = y; void rotation _gauche(ab_t x){ element _t tmp; ab _t y; assert(x && x->droite); y = x->droite; *échange des éléments*/ tmp = x->e;quotesdbs_dbs3.pdfusesText_6

[PDF] [PDF] Les arbres binaires de recherche