Parcours dun arbre binaire
l'ordre postfixe : on liste chaque sommet la dernière fois qu'on le rencontre. Ce qui donne ici : . . . 3. l'ordre infixe : on liste chaque sommet ayant un fils
Arbres binaires
Pères et fils : le sommet 3 est le père de 7 le sommet 6 est le fils de 2. Il est d'usage de dessiner un arbre en plaçant un père au dessus de ses.
Marches permutations et arbres binaires aléatoires
Les sommets sont nu- mérotés à partir de 0 par ordre de création. On commence avec un arbre réduit à un sommet (numéroté 0). Puis
TP 8 : Arbres binaires de recherche
d'un arbre binaire de manière à lire la structure de l'arbre. si le noeud à enlever a deux fils on le remplace par le sommet de plus petite valeur dans ...
Matrice de ramification des arbres binaires*
A tout sommet d'un arbre binaire on associe son nornbre de S/r-ah/et- puis on considkre une matrice dite de ramification
Arbres
simple : il n'existe pas d'arête reliant un sommet à lui-même et deux Dans un arbre binaire strict tout nœud interne a une arité égale à 2.
Arbres binaires
Dans ce contexte il est fréquent de parler de nœud au lieu de sommet. Autre exemple
Une bijection entre binaires et certaines Jacobi arbres matrices de
Arbres binaires. Dans un arbre binaire (enracine et ordonne) tout sommet different de la racine a un ascendant. Tout sommet interne 0 a deux descendants: un
Sur le nombre de registres nécessaires à lévaluation dune
d'une expression arithmétique» sur les arbres binaires est étudiée de façon Appelons point simple d'un arbre binaire tout sommet dont un seul fils.
Algorithmique et Structures de données
On appelle arbre binaire complet un arbre binaire tel que chaque sommet interne a exac- tement 2 fils. 1. Donner des exemples d'arbres binaires complets. 2.
[PDF] Parcours dun arbre binaire
A partir de ce contour on définit trois parcours des sommets de l'arbre : 1 l'ordre préfixe : on liste chaque sommet la première fois qu'on le rencontre
[PDF] Arbres binaires
Un arbre binaire de recherche (en abrégé : ABR) permet l'implémentation sous forme d'arbre binaire de certaines structures de données stockant des éléments
[PDF] Les arbres binaires — - Pascal Delahaye
16 mai 2019 · Chaque élément de l'arbre est appelé un sommet 2 Chaque sommet renvoyant sur d'autres données (intersection) est appelé un noeud On parle
[PDF] Cours 4 : Les arbres binaires
Un arbre binaire est constitué de nœuds • Chaque nœud « pointe » vers deux nœuds de l'étage inférieur ?Version récursive • Un arbre binaire peut être
[PDF] modification Arbre et arborescence Arbres binaires Parcours
23 oct 2014 · Théorème Théorème 4 2: Il existe une bijection qui transforme un arbre planaire ayant n sommet en un arbre binaire complet ayant 2n+1 sommets
[PDF] Feuille 5 : Arbres binaires
On appelle arbre binaire complet un arbre binaire tel que chaque sommet interne a exacte- ment 2 fils 1 Donner des exemples d'arbres binaires complets 2
[PDF] TP 8 : Arbres binaires de recherche - Cedric-Cnam
d'un arbre binaire de manière à lire la structure de l'arbre si le noeud à enlever a deux fils on le remplace par le sommet de plus petite valeur dans
[PDF] Arbres binaires de recherche - CNU 27 Marseille
On parle dans ce cas d'arbre non planté puisqu'il n'y a pas de sommet particulier qui joue le rôle de racine Les sommets sont voisins les uns des autres il n
[PDF] Structures de données et algorithmes
conventionnel et il est basé sur un arbre de recherche binaire malgré qu'ils aient le même nombre de sommet (7) leurs structures sont
[PDF] Structures de données: listes piles files arbres binaires
Les arbres binaires I41 : Types de données 58 dépiler(p) p v p v / sommet sommet arbre binaire de recherche d'une valeur relativement à une
C'est quoi le sommet d'un arbre binaire ?
Le sommet de l'arbre s'appelle la racine. Un nœud qui ne poss? pas d'enfant est appelé feuille. Les nœuds autre que la racine et les feuilles sont appelés nœuds internes. Une branche est une suite de nœud consécutifs de la racine vers une feuille.Comment connaître la hauteur d'un arbre binaire ?
La taille d'un arbre binaire non vide vaut : 1 + taille(sous-arbre gauche) + taille(sous-arbre droit). La hauteur d'un arbre binaire non vide vaut : 1 + max(hauteur(sous-arbre gauche), hauteur(sous-arbre droit)).Quelle est la complexité dans le pire cas de la recherche d'un élément dans un arbre binaire de recherche de hauteur H contenant n nœuds ?
La complexité en temps dans le pire des cas de l'algorithme de recherche d'une clé dans un arbre binaire de recherche équilibré est donc O(log2(n)).- En algorithmique, la rotation d'un arbre binaire de recherche permet de changer la structure d'un arbre binaire de recherche ou ABR sans invalider l'ordre des éléments. Une telle rotation consiste en fait à faire remonter un nœud dans l'arbre et à en faire redescendre un autre.
IREM DE LYON
Parcours d"un arbre binaire
Un arbre binaire est un arbre avec racine dans lequel tout noeud a au plus deux fils : un éventuel fils
gauche et un éventuel fils droit.On illustrera avec l"arbre binaire suivant :r
a c hd ij `b e kf1 Balade autour de l"arbre
On se balade autour de l"arbre en suivant les pointillés dans l"ordre des numéros indiqués :r
a c hd ij `b e kf1 2 34567 89
101112131415
16171819202122
1IREM DE LYON
1.1 Première définition des trois parcours
A partir de ce contour, on définit trois parcours des sommets de l"arbre : 1.l "ordrep réfixe: on li stech aqueso mmetl apr emièrefois qu "onle r encontredan sla b alade.C eq ui
donne ici : ... 2.l "ordrepost fixe: on liste c haquesomm etla der nièrefois q u"onle r encontre.C eq uidonn ei ci: . ..
3.l "ordrein fixe: on li stec haquesommet ay antu nfils gauche l asecon defois qu "onl ev oitet cha que
sommet sans fils gauche la première fois qu"on le voit. Ce qui donne ici : ...Une résolution
1. or drepréfixe : r,a,c,h,d,i,j,`,b,e,k,f. 2. or drepost fixe: h,c,i,`,j,d,a,k,e,f,b,r. 3. or dreinfix e: c,h,a,i,d,`,j,r,k,e,b,f.1.2 Seconde définition des trois parcours Dans la balade schématisée plus haut, on ajoute les fils fantômes manquants :r a c hd ij `b e kfOn peut ainsi considérer qu"on passe une fois à gauche de chaque noeud (en descendant), une fois en-
dessous de chaque noeud, une fois à droite de chaque noeud (en remontant). soit lor squ"onp asseà leu rga uche, soit lor squ"onp asseà leu rdr oite, soit lor squ"onp asseen-dessous .Une résolution
1.A g auche: préfix e.2
IREM DE LYON
2.A d roite: post fixe.
3.E n-dessous: i nfixe.2 Algorithmes récursifs
Pour chacun des parcours définis ci-dessus (postfixe, infixe, préfixe), définir récursivement le parcours.
Une résolution
1.P arcoursp réfixe.Pseudo-code
ParcoursPréfixe (Arbre binaire T de racine r )
Afficher clef [ r ]
ParcoursPréfixe (Arbre de racine fils_gauche [ r ]) ParcoursPréfixe (Arbre de racine fils_droit [ r ])2.P arcoursp ostfixe.Pseudo-code
ParcoursPostfixe (Arbre binaire T de racine r )
ParcoursPostfixe (Arbre de racine fils_gauche [ r ]) ParcoursPostfixe (Arbre de racine fils_droit [ r ])Afficher clef [ r ]3.P arcoursin fixe.
Pseudo-code
ParcoursInfixe (Arbre binaire T de racine r )
ParcoursInfixe (Arbre de racine fils_gauche [ r ])Afficher clef [ r ]
ParcoursInfixe (Arbre de racine fils_droit [ r ])3 Représentation en machineChaque noeud de l"arbre T est representé par un objet ayant un champ clef (des valeurs à trier par
exemple), un champ père, un champ fils_gauche, un champ fils_droit (stockent des pointeurs). Lorsque père[x]=NIL,xest la racine de l"arbre. Lorsquexn"a pas de fils gauche, fils_gauche[x]=NIL(idem pour fils_droit). La racine de l"arbreTest pointée par l"attribut racine[T]. Lorsque racine[T]=NIL,
l"arbre est vide.3IREM DE LYON
4 Complexité d"un parcours infixe
Vérifier qu"avecnnoeuds, le parcours infixePseudo-codeParcours_Infixe (arbre binaire T de racine x)
Six distinct de NIL*****temps constant T(0)=c pour un sous¡arbre vide alors Parcours_Infixe ( arbre de racine fils_gauche [x]) *****temps T(k)Afficher clef [x]
*****temps constant dParcours_Infixe ( arbre de racine fils_droit [x])
*****temps T(n¡k¡1)FinSiprend un temps en£(n) (établir avec les notations suggérées ci-dessus :T(n)AE(cÅd)nÅc)
Une résolution
Amorce :T(0)AEcAE(cÅd)£0Åc.
Hérédité :
T(n)AET(k)ÅT(n¡k¡1)Åd
AE(cÅd)nÅc¡(cÅd)ÅcÅd
AE(cÅd)nÅc
5 La notation polonaise inverse
Écrire les sommets de l"arbre ci-dessous pour chacun des ordres postfixe, préfixe, infixe :¥
ab¡ cdÅ efPour le parcours infixe, on ajoute la convention suivante : on ajoute une parenthèse ouvrante à chaque
fois qu"on entre dans un sous-arbre et on ajoute une parenthèse fermante lorsqu"on quitte ce sous-
arbre.4IREM DE LYON
Une résolution
1. P réfixe(n otationpolo naise): ¥,£,Å,a,b,¡,c,d,Å,e,f. 2. P ostfixe(p olonaisein verse): a,b,Å,c,d,¡,£,e,f,Å,¥. 3.I nfixe: a,Å,b,£,c,¡,d,¥,e,Å,f.
Avec un ajout de parenthèses (ouvrante en rencontrant le noeud racine du sous arbre pour la pre-mière fois et fermante lorsqu"on le rencontre pour la dernière fois, avec exception sur les sous-
arbres constitués d"une feuille) :¡(aÅb)£(c¡d)¢¥(eÅf).L"infixe nécessite cette convention pour lever les ambiguïtés, les deux autres non. La préfixe consiste à
voir les opérateurs comme des fonctions de deux variables : [Å(a,b),¡(c,d)],Å(e,f)´ Idem avec la postfixe mais avec la fonction écrite sur la droite.6 Le tri du bijoutierOn dispose d"une liste de nombres. Par exemple, la liste 7, 9, 3, 5, 4, 1, 8. On associe à chaque élémentn
de la liste un noeudv(initialisation : père[v]=NIL, fils_gauche[v]=NIL, fils_droit[v]=NIL, clef[v]=n).Pseudo-code
Arbre_Insérer(Arbre T, noeud z)
y:=NIL x:=racine [T]TantQuex distinct de NIL faire
y:=xSiclef [z] alorsx:= fils_gauche [x] sinonx:= fils_droit [x] FinSi FinTantQue
père[z]:=y Siy=NIL
alorsracine [T]:=z sinon Siclef [z] alorsfils_gauche [y]:=z sinonfils_droit [y]:=z FinSi FinSi5
IREM DE LYON
1. D resserl "arbreobt enuen app liquantl "algorithmeArbr e_Inséreraux élément sde la l iste(dan s
l"ordre de la liste) en partant d"un arbre vide pour le premier élément, chaque appel à l"algorithme
modifiant l"arbre. 2. L "undes pa rcourspost fixe,infi xe,préfixe de la liste t riela liste .Lequ el? 3. D ansl acon structionde l "arbrepou ru neli sted ennombres, quel est le nombre de comparaisons effectuées dans le pire des cas? 4. Q uele stl en ombrede compa raisonse ffectuéessi l "arbrefi nalest un arbr ebin airecomplet (arbr e
binaire dans lequel tout noeud autre qu"une feuille a deux fils et dans lequel les feuilles sont tous
des noeuds de même profondeur). Une résolution
1. L "arbreobt enu: 7
3 15 49
8 2. Le p arcoursin fixetr iel ali ste.Les é lémentsde g auchesont e ne ffetpar const ructionp luspetit s
qu"un noeud et sont affichés avant le noeud dans l"ordre infixe et les éléments de droite qui sont,
par construction, plus grands sont affichés dans l"ordre infixe après le noeud. Par "récurrence", on
a donc un affichage des éléments de la liste dans l"ordre. On peut donner une version graphique de ce parcours en projetant verticalement les noeuds sur une droite horizontale (à dessiner sous l"arbre). 3. Le p iredes cas corr espondaux cas où la li stee sttr iée(or drec roissantou décr oissant).Le nombr e
de comparaisons à effectuer est alors de 1Å2Å¢¢¢Å(n¡1)AE12 n(n¡1). 4. P ourajou teru nn oeuda univ eaude p rofondeurp(la racine étant au niveau de profondeur 0), on effectuepcomparaisons. Si la profondeur esth, on aura effectué une comparaison pour chacun des deux noeuds de profondeur 1 (2£1), deux comparaisons pour chacun des 22noeuds de pro- fondeur 2 ( total 2 1Å2£22), tros comparaisons pour chacun des 23noeuds de profondeur 3 (total
2 1Å2£22Å3£23) ...
Le nombre de comparaisons pour une profondeurhest (preuve facile par récurrence) : h X jAE1j£2jAE(h¡1)£2hÅ1Å26 IREM DE LYON
Avecnnoeuds (c"est à dirennombres à trier), on a 1Å2Å22Å¢¢¢Å2hAE2hÅ1¡1 et
h X On a donc un cas optimal enO(nlog(n)) et on peut montrer (comme pour le quick sort) que la hauteur moyenne d"un arbre binaire de recherche construit aléatoirement à partir denclefs estO(log(n)) (référence : introduction à l"algorithmique, Cormen, Leiserson,Rivest, Stein, éditions
Dunod, 2002, page 258, paragraphe 12.4).
Les caractéristiques de temps sont les mêmes que pour le quick sort, mais avec un avantage du on crée un arbre de recherche pour le tri du bijoutier).7 Références 1. I ntroductionà l "algorithmique.A uteurs: C ormen,Le iserson,Riv est,S tein.E ditionf rançaise: D u-
nod 2002. Plus de 1100 pages sur les algorithmes et les structures de référence. Le chapitre 12 concerne les
arbres binaires de recherche. 2. U nar ticlede J ean-ClaudeO riolsur le site de l "apmepa vecu npas sagesur l et ridu b ijoutier: 3. Le cou rsde Pierr eA udibert(P aris8 )en l igne:
quotesdbs_dbs44.pdfusesText_44
FinTantQue
père[z]:=ySiy=NIL
alorsracine [T]:=z sinonSiclef [z] alorsfils_gauche [y]:=z sinonfils_droit [y]:=z FinSi FinSi5
IREM DE LYON
1. D resserl "arbreobt enuen app liquantl "algorithmeArbr e_Inséreraux élément sde la l iste(dan s
l"ordre de la liste) en partant d"un arbre vide pour le premier élément, chaque appel à l"algorithme
modifiant l"arbre. 2. L "undes pa rcourspost fixe,infi xe,préfixe de la liste t riela liste .Lequ el? 3. D ansl acon structionde l "arbrepou ru neli sted ennombres, quel est le nombre de comparaisons effectuées dans le pire des cas? 4. Q uele stl en ombrede compa raisonse ffectuéessi l "arbrefi nalest un arbr ebin airecomplet (arbr e
binaire dans lequel tout noeud autre qu"une feuille a deux fils et dans lequel les feuilles sont tous
des noeuds de même profondeur). Une résolution
1. L "arbreobt enu: 7
3 15 49
8 2. Le p arcoursin fixetr iel ali ste.Les é lémentsde g auchesont e ne ffetpar const ructionp luspetit s
qu"un noeud et sont affichés avant le noeud dans l"ordre infixe et les éléments de droite qui sont,
par construction, plus grands sont affichés dans l"ordre infixe après le noeud. Par "récurrence", on
a donc un affichage des éléments de la liste dans l"ordre. On peut donner une version graphique de ce parcours en projetant verticalement les noeuds sur une droite horizontale (à dessiner sous l"arbre). 3. Le p iredes cas corr espondaux cas où la li stee sttr iée(or drec roissantou décr oissant).Le nombr e
de comparaisons à effectuer est alors de 1Å2Å¢¢¢Å(n¡1)AE12 n(n¡1). 4. P ourajou teru nn oeuda univ eaude p rofondeurp(la racine étant au niveau de profondeur 0), on effectuepcomparaisons. Si la profondeur esth, on aura effectué une comparaison pour chacun des deux noeuds de profondeur 1 (2£1), deux comparaisons pour chacun des 22noeuds de pro- fondeur 2 ( total 2 1Å2£22), tros comparaisons pour chacun des 23noeuds de profondeur 3 (total
2 1Å2£22Å3£23) ...
Le nombre de comparaisons pour une profondeurhest (preuve facile par récurrence) : h X jAE1j£2jAE(h¡1)£2hÅ1Å26 IREM DE LYON
Avecnnoeuds (c"est à dirennombres à trier), on a 1Å2Å22Å¢¢¢Å2hAE2hÅ1¡1 et
h X On a donc un cas optimal enO(nlog(n)) et on peut montrer (comme pour le quick sort) que la hauteur moyenne d"un arbre binaire de recherche construit aléatoirement à partir denclefs estO(log(n)) (référence : introduction à l"algorithmique, Cormen, Leiserson,Rivest, Stein, éditions
Dunod, 2002, page 258, paragraphe 12.4).
Les caractéristiques de temps sont les mêmes que pour le quick sort, mais avec un avantage du on crée un arbre de recherche pour le tri du bijoutier).7 Références 1. I ntroductionà l "algorithmique.A uteurs: C ormen,Le iserson,Riv est,S tein.E ditionf rançaise: D u-
nod 2002. Plus de 1100 pages sur les algorithmes et les structures de référence. Le chapitre 12 concerne les
arbres binaires de recherche. 2. U nar ticlede J ean-ClaudeO riolsur le site de l "apmepa vecu npas sagesur l et ridu b ijoutier: 3. Le cou rsde Pierr eA udibert(P aris8 )en l igne:
quotesdbs_dbs44.pdfusesText_44
FinSi5
IREM DE LYON
1.D resserl "arbreobt enuen app liquantl "algorithmeArbr e_Inséreraux élément sde la l iste(dan s
l"ordre de la liste) en partant d"un arbre vide pour le premier élément, chaque appel à l"algorithme
modifiant l"arbre. 2. L "undes pa rcourspost fixe,infi xe,préfixe de la liste t riela liste .Lequ el? 3. D ansl acon structionde l "arbrepou ru neli sted ennombres, quel est le nombre de comparaisons effectuées dans le pire des cas? 4.Q uele stl en ombrede compa raisonse ffectuéessi l "arbrefi nalest un arbr ebin airecomplet (arbr e
binaire dans lequel tout noeud autre qu"une feuille a deux fils et dans lequel les feuilles sont tous
des noeuds de même profondeur).Une résolution
1.L "arbreobt enu: 7
3 15 498 2.
Le p arcoursin fixetr iel ali ste.Les é lémentsde g auchesont e ne ffetpar const ructionp luspetit s
qu"un noeud et sont affichés avant le noeud dans l"ordre infixe et les éléments de droite qui sont,
par construction, plus grands sont affichés dans l"ordre infixe après le noeud. Par "récurrence", on
a donc un affichage des éléments de la liste dans l"ordre. On peut donner une version graphique de ce parcours en projetant verticalement les noeuds sur une droite horizontale (à dessiner sous l"arbre). 3.Le p iredes cas corr espondaux cas où la li stee sttr iée(or drec roissantou décr oissant).Le nombr e
de comparaisons à effectuer est alors de 1Å2Å¢¢¢Å(n¡1)AE12 n(n¡1). 4. P ourajou teru nn oeuda univ eaude p rofondeurp(la racine étant au niveau de profondeur 0), on effectuepcomparaisons. Si la profondeur esth, on aura effectué une comparaison pour chacun des deux noeuds de profondeur 1 (2£1), deux comparaisons pour chacun des 22noeuds de pro- fondeur 2 ( total 21Å2£22), tros comparaisons pour chacun des 23noeuds de profondeur 3 (total
21Å2£22Å3£23) ...
Le nombre de comparaisons pour une profondeurhest (preuve facile par récurrence) : h X jAE1j£2jAE(h¡1)£2hÅ1Å26IREM DE LYON
Avecnnoeuds (c"est à dirennombres à trier), on a 1Å2Å22Å¢¢¢Å2hAE2hÅ1¡1 et
h X On a donc un cas optimal enO(nlog(n)) et on peut montrer (comme pour le quick sort) que la hauteur moyenne d"un arbre binaire de recherche construit aléatoirement à partir denclefsestO(log(n)) (référence : introduction à l"algorithmique, Cormen, Leiserson,Rivest, Stein, éditions
Dunod, 2002, page 258, paragraphe 12.4).
Les caractéristiques de temps sont les mêmes que pour le quick sort, mais avec un avantage du on crée un arbre de recherche pour le tri du bijoutier).7 Références 1.I ntroductionà l "algorithmique.A uteurs: C ormen,Le iserson,Riv est,S tein.E ditionf rançaise: D u-
nod 2002.Plus de 1100 pages sur les algorithmes et les structures de référence. Le chapitre 12 concerne les
arbres binaires de recherche. 2. U nar ticlede J ean-ClaudeO riolsur le site de l "apmepa vecu npas sagesur l et ridu b ijoutier: 3.Le cou rsde Pierr eA udibert(P aris8 )en l igne:
quotesdbs_dbs44.pdfusesText_44[PDF] retour ? l'unité proportionnalité
[PDF] le timbre d'un son
[PDF] psychologie criminelle cours pdf
[PDF] passage ? l'acte psychologie
[PDF] cours de criminologie générale pdf
[PDF] livre criminologie pdf
[PDF] tétraèdre régulier propriétés
[PDF] passage ? l'acte
[PDF] tétraèdre propriétés
[PDF] grille d'estimation de la dangerosité d'un passage ? l'acte suicidaire pondération
[PDF] intervenir auprès de la personne suicidaire ? l'aide de bonnes pratiques
[PDF] grille estimation dangerosité suicidaire
[PDF] grille d'évaluation de l'urgence suicidaire
[PDF] rapport d'intervention auprès de la personne suicidaire
