Plan
Les arbres • Motivations
• Définitions
• Propriétés
• Parcours d’un arbre général
–en profondeur,
–en largeur
–Préfixe, suffixe, postfixe
• Les arbres binaires de recherche
1 2
Motivations (Liste Vs Arbre) Motivations (Liste Vs Arbre)
Pour une liste L=[5,2,21,-4,3,21,19,25] ●
L'utilisation des arbres permet de gagner considérablement
Le coût pour accéder à la valeur 25 varie entre 1 et 8 ●
Mémoire de stockage.
Alors que pour un arbre le coût varie entre 1 et 3 ●
Complexité :
⇒ D'une manière générale le coût pour chercher un élément ●
Temps
dans une liste est O(n) alors que dans un arbre (équilibré) est ●
Mémoire
O(log2(n))
Le cas pire Le cas meilleur
●
Le complexité pour chercher un élément est :
●
O(n) pour une liste O(n)
●
O(log2(n)) pour un arbre dans le cas meilleur et O(n) dans le
cas pire.
3 4
Définitions (les arbres généraux) Définitions (les arbres généraux)
●
Un arbre est une structure de données récursive ●
La racine r de l'arbre est l'unique nœud ne possédant pas de
●
Un arbre général est un ensemble de nœuds organisé de façon parent
hiérarchique à partir d’un nœud distingué qui est la racine • Chaque nœud peut donner naissance à une ou plusieurs
Nœud racine branches Nœud racine
Nœud
La branche 5 – 2 La branche 5 – 21
Nœud
Nœud (Feuille)
Nœud (Feuille)
Nœud (Feuille) Nœud (Feuille)
5 6
Les arbres généraux Les arbres généraux
●
Tout nœud x qui n’est pas la racine a • Une branche est le chemin qui joint un nœud à la racine
●
un unique parent, noté parent(x) (appelé « père » – ex : la branche 147
●
0 ou plusieurs fils ; fils(x) désigne l’ensemble des fils de x • Donner le(s) chemin(s) des branches suivantes:
●
Un nœud sans fils est une feuille. – 1 → 9 : ………………….
– 1 → 10 : ………………...
●
14 est le père de ……
●
8 est le fils de …….
●
Donner les feuilles de l'arbre ci-dessus:
………………………………………………………….
7 8
Arbre binaire Arbre binaire
Un arbre binaire est un ensemble fini de valeurs qui est : Un arbre binaire est un ensemble fini de valeurs qui est :
Øsoit vide. ●
soit vide.
Øsoit constitué d’une racine et des valeurs de deux arbres binaires ●
soit constitué d’une racine et des valeurs de deux arbres binaires
disjoints appelés sous-arbres gauche et sous-arbre droit de la racine. disjoints appelés sous-arbre gauche et sous-arbre droit de la racine.
Nœud racine
Fils droit de 5
Fils gauche de 5
Fils droit de 25
Fils gauche de 15
Arbre binaire Arbre non binaire Arbre binaire
9 10
Arbre binaire : Parcours Arbre binaire : Parcours
parcours en largeur parcours en profondeur
• Dans un parcours en largeur, on énumère les nœuds par ordre
Parcours préfixe: tout Nœud est suivi des nœuds de son sous-arbre
croissant de profondeur des nœuds Autrement dit, de haut en bas,
Gauche puis des nœuds de son sous-arbre Droit.
niveau par niveau (et de gauche a droite). – Donner le parcours préfixe: …………………………………...
• Exemple: Parcours infixe : tout Nœud est précédé des nœuds de son sous-arbre
– Donner le parcours en largeur de l’arbre suivant: Gauche et suivi des nœuds de son sous-arbre Droit.
…………………………………………………………….. – Donner le parcours infixe: …………………………………...
Parcours suffixe : tout Nœud est précédé des nœuds de son sous-arbre
Gauche et des nœuds de son sous-arbre Droit.
– Donner le parcours suffixe: …………………………………...
11 12 12
Les arbres binaires de recherches Les arbres binaires de recherches
Un arbre binaire[r,G,D] est un arbre binaire de recherche (ou ABR) s’il Un arbre binaire[r,G,D] est un arbre binaire de recherche (ou ABR) s’il vérifié les trois
vérifié les trois conditions suivantes : conditions suivantes :
●
La valeur de la racine r est inférieure ou égale à toutes les valeurs de son SAD
●
La valeur de la racine r est inférieure ou égale à toutes les valeurs de ●
La valeur de la racine r est supérieurs ou égale à toutes les valeurs de son SAG
son SAD ●
Les deux sous arbres G et D, sont des arbres binaires de recherches.
●
La valeur de la racine r est supérieurs ou égale à toutes les valeurs de
son SAG
9 9
●
Les deux sous arbres G et D, sont des arbres binaires de recherches.
16 12 5 12
4 10 20 4 7 20
Exemple1 Exemple2
Arbre binaire, qui n’est pas
Arbre binaire de recherche
un arbre de recherche
13 14
Arbre binaire et le langage C Création d’un arbre contenant que la racine.
Énoncé
En C, nous pouvons représenter un arbre par une structure de données de la Donner le code de la fonction Noeud* creerRacine(int valeur), qui permet de créer
forme : un arbre contenant que la racine (valeur) et deux fils gauche=NULL et
typedef struct Noeud { droit=NULL.
int donnee; // Donnée stockée dans le nœud
Solution
struct Noeud *gauche; // Pointeur vers le sous-arbre gauche
struct Noeud *droit; // Pointeur vers le sous-arbre droit Noeud* creerRacine(int valeur) {
} Noeud; Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
if (nouveau == NULL) {
printf("Erreur d'allocation mémoire\n");
exit(1);
}
nouveau->donnee = valeur;
nouveau->gauche = NULL;
nouveau->droit = NULL;
return nouveau;
}
16
Ajouter un élément à un ABR.
Énoncé
Donner le code de la fonction Noeud* inserer(Noeud* racine, int valeur), qui
permet d’ajouter un nouvel élément contenant la valeur valeur, à l’arbre racine.
Solution
Noeud* inserer(Noeud* racine, int valeur) {
// Si l'arbre est vide, créer un nouveau nœud
if (racine == NULL) {
return creerRacine(valeur);
}
// Sinon, descendre dans l'arbre
if (valeur < racine->donnee) {
racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droit = inserer(racine->droit, valeur);
}
return racine;
} 17
