Embed Size (px)
Citation preview
Chapitre VII. Arbres (suite)
Arbres binaires
1
• Dans un arbre binaire un nœud peut avoir au plus deux fils
• Fils Gauche (FG) • Fils Droit (FD)
Définition (1)
1
2
4
56
7
8 9
2
Définition (2)
• La base : un arbre vide est un arbre binaire
• La récurrence : si r est un nœud et si B1 et B2 sont des arbres binaires alors il existe un arbre binaire avec une racine r et un sous-arbre gauche B1 et un sous-arbre droit B2
• Non-symétrie :
>=< 2,1, BBrB
>>∅∅<∅>≠<∅>∅∅<< ,,,,,,,, rrrr
6
1 1
6
≠
3
Structures de données pour les arbres binaires
• Type PtrNoeud = ^Noeud Enregistrement Noeud
info : TypeInfo FilsGauche : PtrNoeud FilsDroit : PtrNoeud Fin Enregistrement;
info
info info
FG
FG FG
FD
FD FD
4
Type abstrait Arbre Binaire
• Type Arbre =PtrNoeud • Signature • Type Arbre • Opérations • Arbre-vide : ->Arbre • <-,-,-> : PtrNoeud X Arbre X Arbre ->Arbre • Racine: Arbre ->PtrNoeud • FG : Arbre ->Arbre • FD : Arbre ->Arbre • contenu : PtrNoeud>Info • est-vide? : Arbre ->Booléen
5
Axiomes
• Préconditions • Racine(B) est-defini-ssi B<> arbre-vide • G(B) est-defini-ssi B<> arbre-vide • D(B) est-defini-ssi B<> arbre-vide • Axiomes • Racine(<r,B1,B2>)=r • G(<r,B1,B2>)=B1 • D(<r,B1,B2>)=B2
6
• Chaque nœud est soit une feuille soit d’un degré = 2
Arbres Binaires complets
1
2
4
56
7
8 9
1
4
56
7
8 9
7
Un arbre complet d’arité 2
• Cas particulier des arbres binaires complets : toutes les feuilles ont la même profondeur
1
4
56
7
8 9
1
4
56
7
8 98
Un arbre complet d’arité 2
(1) Combien de feuilles y a–t-il dans un arbre complet d’arité 2 et de profondeur h?
• Les feuilles sont les fils des nœuds à la profondeur h-1 • La racine a 2 fils à la profondeur 1, chacun d’eux a 2 fils à la
profondeur 2,, • 2x2 • Etc… • Le nombre de feuilles est donc 2h
• La hauteur d’un arbre complet comportant n feuilles est donc lg n
(2) Combien de nœuds internes ? • 1 – racine +2 +2x2 + …+ 2h-1 = 12
122
1
0 −
−=∑
−
=
hh
i
i
9
Parcours des arbres binaires(1)
• Parcours en profondeur • Procédure Parcours(B: Arbre) • Début
– Si est-vide(B) alors Terminaison – sinon – Traitement 1 – Parcours(FG(B)) – Traitement 2 – Parcours (FD(B)) – Traitement 3 – FSi FinParcours –
10
• Procédure ParcoursPréfixe(B: Arbre) • Début
– Si est-vide(B) alors Terminaison – sinon – Traitement 1 – Parcours(FG(B)) – Parcours (FD(B)) FinParcours –
Parcours en Ordre-« Préfixe »
1
4
56
7
8 9
1,6,5,7,4,8,9
« +ab »
11
Ordre « Infixe » • Procedure ParcoursInfixe(B: Arbre) • Début
– Si est-vide(B) alors Terminaison – sinon – Parcours(g(B)) – Traitement 2 – Parcours (d(B)) – FSi FinParcours
1
4
56
7
8 9
6,1,7,5,8,4,9
« a+b »
12
Ordre suffixe- postfixe
• Procédure ParcoursSuffixe(B: Arbre) • Début
– Si est-vide(B) alors Terminaison – sinon – Parcours(FG(B)) – Parcours (FD(B)) – Traitement 3 – FSi FinParcours
1
4
56
7
8 9
6,7,8,9,4,5,1 13
Représentation des expressions arithmétiques
x
y
*
-
a b
+Expression usuelle:
x+(a-b)*y
14
Représentation des expressions arithmétiques
x
y
*
-
a b
+Préfixe
+ x * - a b y
+ (x)(*-aby)
(*(-(a)(b))(y))
Chaque opérateur précède ces deux opérandes
15
Représentation des expressions arithmétiques
x
y
*
-
a b
+Postfixe
x a b – y * +
(x)(ab-y*)+
(ab-)(y)*
(a)(b)-
Chaque opérateur est précédé par ces deux opérandes 16
Représentation des expressions arithmétiques
x
y
*
-
a b
+Infixe
x+a-b*y
Ambigüité!
Ajouter systématiquement les parenthèses aux expressions
17
Arbres binaires de recherche
• Objectif : ordonner par clés les informations stockées. • Les opérations : recherche, min, max, prédécesseur, successeur,
insérer, supprimer. • Dans le meilleur de cas la complexité de ces opérations est • Dans le pire des cas , n – nombre de nœuds
• Propriété fondamentale : • B: ABR, x –nœud • SAG : sous-arbre gauche de racine r=x • SAD: sous-arbre droit de racine r=x • Si • Si
( )nΘ
Θ lg n( )
][][)( xcléycléxSAGy ≤⇒∈
][][)( xcléycléxSADy ≥⇒∈
5
3 7
18
ABR : quelques opérations
• Pb : Imprimer toutes les clés dans l’ordre croissant • Solution : parcours Infixe (FG, r, FD) • Procedure ParcoursInfixe (x: Arbre) • Debut
– Si x<>Nil – alors – ParcoursInfixe(FG(x)) – imprimer (clé(x)) – ParcoursInfixe(FD(x)) – FSi – Fin ParcoursInfixe
7
6
3
52 8
Résultat : 2 3 5 6 7 8 19
Recherche dans un ABR(1)
• Problème : rechercher un nœud ayant une clé donnée. • La fonction renvoie NIL si la clé ne se trouve pas dans l’arbre ou
le pointeur sur le nœud qui contient la clé. • Fonction RechercheABR (A: PtrNoeud, k: entier):PtrNoeud • Debut
– Si est-vide(A) ou k=clé[A] – alors retourner A – sinon – Si k< clé(A) – alors retourner RechercheABR(FG(A),k) – sinon retourner RechercheABR(FD(A),k) – FSi – FSi Fin recherche
Complexité la hauteur de l’arbre −Θ hh),( 20
Recherche dans un ABR(2)
• Algorithme itératif • Fonction RechercheIterABR(A: PtrNoued, k: entier) :
PtrNoeud • Début
– TQ A<>NIL et clé(A)<>k faire • Si k<clé(A)
alors A:= FG(A) sinon A:=FD(A)
FSi FTQ FinRechercheIterABR
21
MinMax dans un ABR
Min : aller toujours à gauche jusqu'à atteindre le dernier FG – feuille { les test est-vide(A) =faux} Tq FG(A)< > Nil A:=FG(A) FTq retourner contenu(A) Max : réciproque { les test est-vide(A) =faux} Tq FD(A)< > Nil A:=FD(A) FTq retourner contenu(A)
22
Insertion dans les ABRs Procédure Insérer(val x : Type Info, réf A: PtrNœud ) Debut Si A=Nil alors new A A^.info:=x; A^.FilsG:=Nil; A^.FilsD:=Nil; sinon Si x<A^.info alors Insérer(x, A^.FilsG) sinon Si x>A^.Info alors Insérer(x, A^.FilsD) sinon FSi FSi
FSi FinInsérer
23
Suppression dans un ABR
• Supprimer le nœud contenant la clé X donnée • La relation d’ordre doit être préservée • (1) Si c’est un nœud sans fils – la suppression est
immédiate • (2) Si c’est un nœud qui a un seul fils, il suffit de
remplacer le noeud par ce fils • (3) Si c’est un nœud qui a deux fils, alors remplacer le
nœud contenant l’élément à supprimer par celui qui lui est immédiatement inférieur(qui contient le plus grand élément de son sous-arbre gauche).
24
