Algorithmique :

structure des donnes

Franois Lambert

Arbres

Structures arborescentes
De finition informelle
Un arbre est un ensemble de sommets tel que :
il existe un sommet unique appele racine qui na pas de pe re
tous les autres sommets sont atteints a partir de la racine, par une
branche unique

De finition re cursive
Un arbre est constitue de
une racine
une liste darbres disjoints A1, ..., An (sous arbres)
Un sommet de larbre est la racine dun sous-arbre

Reprsentation graphique dun arbre

Exemple dutilisation graphique des arbres

Reprsentation
de lorganisation de fichiers informatiques

dune expression arithmtique

Exemple dutilisation graphique des arbres

Reprsentation
de mots, de phrases (en linguistique)

arbre de drivation en analyse syntaxique

arbre de aabbabab avec
S -> aSb
S ->

Exemple dutilisation graphique des arbres

Reprsentation
arbre gnalogique

arbre de tournoi

Particularit des arbres

Se prtent bien aux algorithmes rcursifs

Terminologie
nud = sommet
pe re dun sommet :
le pre de cesseur dun sommet
fils dun sommet
les successeurs dun sommet
fre res
des sommets qui ont le meme pe re
racine
nud sans pe re
feuille :
nud sans fils
branche
chemin entre 2 nuds

Terminologie
Niveau (profondeur) dun nud
la longueur de la branche depuis la racine

Hauteur dun nud

la longueur de la plus longue branche de ce nud jusqua une
feuille

Hauteur dun arbre

la hauteur de la racine

Taille dun arbre

nombre de ses sommets

Arbres binaires

Arbre binaire
De finition informelle
Dans un arbre binaire, tout nud a au plus deux fils
Un arbre binaire posse de exactement deux sous-arbres
(e ventuellement vides)

De finition re cursive
un arbre binaire est
soit vide
soit compose
dune racine
de deux sous-arbres binaires ABG et ABD disjoints
ABG : sous Arbre Binaire Gauche
ABD : sous Arbre Binaire Droit

Arbres binaires particuliers

Arbre binaire dgnr, filiforme
chaque noeud possde exactement un fils
-> viter

Arbres binaires particuliers

Arbre binaire parfait (complet)
chaque niveau est compltement rempli
Tout sommet est soit une feuille au dernier niveau, soit possde
exactement deux fils

Arbres binaires particuliers

Arbre binaire presque parfait
Tous les niveaux sont compltement remplis sauf ventuellement
le dernier et dans ce cas les feuilles sont le plus a gauche
possible

Arbres binaires particuliers

Arbre binaire quilibr
la diffrence de hauteur entre deux frre ne peut dpasser 1

Arbres binaires de recherche (ABR)

Dans un arbre binaire de recherche
nud racine contient un e le ment X
dans ABG : les nuds sont X
dans ABD : les nuds sont > X

Exemple darbre binaire de recherche

Exemple darbre binaire de recherche

Exemple darbre binaire de recherche

Arbre binaire de recherche quilibr (AVL)

Un arbre binaire de recherche est e quilibre si la diffe rence de hauteur
entre 2 fre res ne de passe pas 1
Du nom des 2 inventeurs (Adelson-Velsky et Landis, 1962)

Implmentation
des arbres binaires

Implmentation des arbres binaires

Imple mentation du TDA ARBRE (binaire)
par cellules cha ne es
par cellules contigues
par curseurs (faux pointeurs)
re alisation des arbres parfaits

Implmentation par cellules chanes

Un arbre binaire est soit :
un pointeur sur le nud racine (arbre non vide)
le pointeur NULL
Un nud est une structure a trois champs :
une e tiquette, valeur (e le ment)
le sous-arbre gauche
le sous-arbre droit
De finition re cursive la plus simple a programmer

Implmentation par cellules chanes

typedef struct nud {

ELEMENT etiq; // e tiquette
struct nud *ag; // ABG : fils gauche
struct nud *ad; // ABD : fils droit
} NOEUD
typedef NUD *ARBRE
#define ARBRE_VIDE NULL

Implmentation par cellules chanes

Implmentation par cellules contiges

Un arbre est une structure a deux champs
un tableau ou sont me morise s les nuds
un entier qui donne lindice de la racine dans le tableau

Un nud est une structure a trois champs

le tiquette du nud
Les indices de ses fils gauche et droit (ou 0 si pas de fils)

Implmentation par cellules contiges

typedef struct noeud {

ELEMENT etiq ; /* e tiquette */
int fg; // fils gauche
int fd; // fils droit
} NOEUD;
typedef struct {
NOEUD tab [TAILLE_MAX ] ;
int racine
} rep;
typedef rep * ARBRE;

Implmentation par cellules contiges

Implmentation par curseurs (faux pointeurs)

Meme principe que les faux pointeurs dans le TDA Liste :
simulation de la me moire : les nuds sont dans un tableau en
variable globale
Un arbre = indice de la racine (0 si vide)
Un nud est une structure a trois champs :
le tiquette du nud
lindice du fils gauche (ou 0 si il est vide)
lindice du fils droit (ou 0 si il est vide)
Gestion des cellules disponibles
marquer les cellules libres et parcourir le tableau pour trouver la
premie re place libre

Implmentation par curseurs (faux pointeurs)

Cas particulier des arbres parfaits

Solution efficace (acce s + place me moire) de re alisation dun arbre
parfait A de N e tiquettes :
Un tableau T avec
T[1] : racine de A
T[i] : e tiquette du pe re
T[2i] : e tiquette du fils gauche
T[2i+1] : e tiquette du fils droit

Cas particulier des arbres parfaits

Si A est larbre parfait suivant :

Alors la ralisation de A est le tableau :

Manipulation
des arbres binaires

Oprations sur les arbres

Calcul de la hauteur

Calcul du nombre de noeuds, du nombre de feuilles

Recherche dun lment

Insertion dun lment

Suppression dun lment

Parcours

Primitives des arbres binaires

ArbreVide(ARBRE A)
indique si un arbre est vide ou non
ARBRE FilsGauche(ARBRE A)
renvoie le fils gauche de larbre A
ARBRE FilsDroit(ARBRE A)
renvoie le fils droit de larbre A
ARBRE EstFeuille(ARBRE A)
indique si larbre A est une feuille
ARBRE ArbreCreer()
cre e et renvoie un arbre

Primitives des arbres binaires

ELEMENT ValeurRacine(ARBRE A)
renvoie le tiquette de la racine de larbre A
ArbreDetruire(ARBRE A)
de truit un arbre A

Parcours darbres binaires

Parcours dun arbre

Parcours dun arbre : parcours de tous les nuds avec
ventuellement lapplication dune fonction (traitement).

Le parcours se fait selon un certain ordre

Parcours en profondeur
un parcours est dit en profondeur si, lorsque larbre nest pas
vide, le parcours de lun des deux sous-arbres ne commence que
lorsque le parcours de lautre est termine
Il existe 3 types de parcours en profondeur : pre fixe, infixe ou
postfixe
Parcours en largeur
un parcours est dit en largeur lorsqua partir dun sommet S, les
fre res de S sont explore s avant les fils de S.

Parcours en profondeur
Parcours en profondeur de gauche a droite (le parcours droitegauche se de duit par syme trie)
Pre fixe (Racine / Gauche / Droit)
traitement de la racine
parcours pre fixe du sous-arbre gauche
parcours pre fixe du sous-arbre droit
Infixe ou syme trique (Gauche / Racine / Droit)
parcours infixe du sous-arbre gauche
traitement de la racine
parcours infixe du sous-arbre droit
Postfixe ou suffixe (Gauche / Droit / Racine)
parcours suffixe du sous-arbre gauche
parcours suffixe du sous-arbre droit
traitement de la racine

Parcours en profondeur
Pour larbre

Les ordres de traitement des noeuds sont, selon les parcours

Parcours prfixe
parcours Racine / Gauche / Droit : le nud racine est traite au premier
passage avant le parcours des sous-arbres
Algrithme :
Parcours(ARBRE A) DEBUT
Si non(ArbreVide(A)) ALORS
traitement(ValeurRacine(A))
Parcours(FilsGauche(A))
Parcours(FilsDroit(A))
FINSI
FIN

Parcours infixe
parcours Gauche / Racine / Droit : le nud racine est traite apre s le
parcours du sous-arbre gauche et avant le parcours du sous-arbre
droit
Algorithme :
Parcours(ARBRE A) DEBUT
Si non(ArbreVide(A)) ALORS
Parcours(FilsGauche(A))
traitement(ValeurRacine(A))
Parcours(FilsDroit(A))
FINSI
FIN

Parcours infixe et arbre binaire de recherche

Un arbre binaire est un arbre binaire de recherche si et seulement si la
liste des valeurs des nuds e tablie dans lordre infixe est croissante
Exemple
larbre suivant est un ABR. La liste des valeurs des nuds e tablie
dans lordre infixe est croissante : {2, 4, 7, 12, 20}

Parcours suffixe
parcours Gauche / Droit / Racine : le nud racine est traite apre s les
parcours des sous-arbre gauche et droit
Algorithme :
Parcours(ARBRE A) DEBUT
Si non(ArbreVide(A)) ALORS
Parcours(FilsGauche(A))
Parcours(FilsDroit(A))
traitement(ValeurRacine(A))
FINSI
FIN

Parcours en largeur
un parcours est dit en largeur lorsqua partir dun sommet S, les
fre res de S sont explore s avant les fils de S.

Ide e : utiliser une file pour enfiler les sommets a traiter

Parcours en largeur : algorithme

ParcoursLargeur(ARBRE A)
F: une file dattente
DEBUT
Cre er la file F
Si non(ArbreVide(A)) ALORS
Enfiler A dans F
TANT QUE non(FileVide(F)) FAIRE
A = Defiler(F)
traitement(ValeurRacine(A))
SI non(ArbreVide(FilsGauche(A)) ALORS
Enfiler FilsGauche(A) dans F
FINSI
SI non(ArbreVide(FilsDroit(A)) ALORS
Enfiler FilsDroit(A) dans F
FINSI
FINTANTQUE
FINSI
De truire F
FIN

Oprations sur les arbres

binaires de recherche

Oprations des arbres binaires de recherche

Recherche dun lment

Insertion dun lment

Suppression dun lment

Primitives des arbres binaires de recherche

ABRVide(ABR A)
indique si un ABR A est vide ou non
ABR ABG(ABR A)
renvoie le fils gauche de ABR A
ABR ABD(ABR A)
renvoie le fils droit de lABR A
ABR EstFeuille(ABR A)
indique si larbre A est une feuille
ABR ABRCreer()
cre e et renvoie un ABR

Primitives des arbres binaires de recherche

ELEMENT ValeurRacine(ABR A)
renvoie le tiquette de la racine de lABR A
ABRDetruire(ABR A)
de truit un ABR A

Recherche dun lment dan sun ABR

ABRRechercher(ELEMENT e, ABR A)
DEBUT
si ABRVide(A) alors
renvoyer FAUX
sinon si e = ValeurRacine(A) alors
renvoyer VRAI
sinon si e < ValeurRacine(A) alors
renvoyer (ABRRechercher(e, ABG(A))
sinon
renvoyer (ABRRechercher(e, ABD(A))
FIN
Complexite : O(Hauteur(A))

Construction dun arbre

Un arbre A se construit par insertions successives de le ments x

2 me thodes principales :
insertion aux feuilles
ajout de chaque e le ment e a une feuille de A
insertion a la racine
Le le ment e devient la nouvelle racine A

Insertion dune feuille

ABRInsererFeuille(ELEMENT X, ABR A)
DEBUT
Si ABRVide(A) Alors
e tiquette de A X
ABG(A) ABR_VIDE
ABD(A) ABR_VIDE
Sinon
Si X <= ValeurRacine(A) Alors
ArbreInsererFeuille(X, ABG(A))
Sinon
ArbreInsererFeuille(X, ABD(A))
FIN

Insertion la racine
Le le ment X a ajouter devient la nouvelle racine.

Il est ne cessaire de se parer lancien ABR en 2 sous-arbres

le sous-arbre gauche de la racine et qui contiendra des valeurs
infe rieures ou e gales a le le ment X
le sous-arbre droit de la racine qui contiendra des valeurs
strictement supe rieures a X

Insertion la racine
2 e tapes
couper larbre en 2 sous-arbres gauche et droit selon les re gles cidessus
G contient tous les e le ments de A X
D contient tous les e le ments de A > X
former un nouvel ABR A avec :
e tiquette de A : X
fils gauche de A : G
fils droit de A : D

Mthodes de coupure
Coupure dun e le ment X dans un ARBRE A
il nest pas ne cessaire de parcourir tous les nuds de A,
seulement les nuds N situe s sur le chemin de recherche de X
dans A
Si nud N X : on ajoute le nud N et ABG(N) dans G
Si nud N > X : on ajoute le nud N et ABD(N) dans D

Exemple de coupure
Soit larbre ci-dessous, on souhaite inse rer le le ment f a la racine de
larbre

Nuds parcourus (chemin de recherche de f) : q, d, i, e, g

Exemple de coupure
N vaut q et N > X car q > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut q et N > X car q > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut q et N > X car q > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut d et N <= X car d <= f : ajout de N et son fils gauche a G

Exemple de coupure
N vaut d et N <= X car d <= f : ajout de N et son fils gauche a G

Exemple de coupure
N vaut d et N <= X car d <= f : ajout de N et son fils gauche a G

Exemple de coupure
N vaut i et N > X car i > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut i et N > X car i > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut i et N > X car i > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut e et N <= X car e <= f : ajout de N et son fils gauche a G

Exemple de coupure
N vaut e et N <= X car e <= f : ajout de N et son fils gauche a G

Exemple de coupure
N vaut e et N > X car g > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut e et N > X car g > f : ajout de N et son fils droit a D

Exemple de coupure
N vaut e et N > X car g > f : ajout de N et son fils droit a D

Procdure de coupure
Coupure de A en 2 ABR G et D
Coupure (ELEMENT X, ABR A, ABR G , ABR D )
De but
Si ABRVide(A) ALORS
G ABR_VIDE
D ABR_VIDE
SINON
SI X <= ValeurRacine(A) ALORS
DA
Coupure ( X, ABG(A) , G, ABG(D) )
SINON
GA
Coupure ( X, ABD(A) , ABD(G) , D)
FSI
FSI
Fin

Insertion la racine
Ajout dun e le ment X a la racine de larbre A
ABRInsererRacine(ELEMENT X, ABR A)
ABR R
De but
e tiquette de R X
ABG(R) ABR_VIDE
ABD(R) ) ABR_VIDE
Coupure (X, A, ABG(R) , ABD(R) )
AR
Fin

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
1. N a 0 fils (X = ValeurRacine(N)) : suppression imme diate
2. N a 1 fils : on remplace N par ce fils
3. N a 2 fils : 2 solutions
remplacer X par le le ment qui lui est imme diatement infe rieur :
le MAX dans ABG(N)
remplacer X par le le ment qui lui est imme diatement supe rieur :
le MIN dans ABD(N)

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
1. N a 0 fils (X = ValeurRacine(N)) : suppression imme diate
2. N a 1 fils : on remplace N par ce fils
3. N a 2 fils : 2 solutions
remplacer X par le le ment qui lui est imme diatement infe rieur :
le MAX dans ABG(N)
remplacer X par le le ment qui lui est imme diatement supe rieur :
le MIN dans ABD(N)

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
1. N a 0 fils (X = ValeurRacine(N)) : suppression imme diate

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
2. N a 1 fils : on remplace X par ce fils

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
2. N a 1 fils : on remplace N par ce fils

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
2. N a 1 fils : on remplace N par ce fils

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
3. N a 2 fils : 2 solutions

remplacer X par le le ment qui lui est imme diatement infe rieur : le MAX
dans ABG(N)
remplacer X par le le ment qui lui est imme diatement supe rieur : le MIN
dans ABD(N)

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
3. N a 2 fils : 2 solutions
remplacer X par le le ment qui lui est immdiatement infe rieur : le
MAX dans ABG(N)

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
3. N a 2 fils : 2 solutions
remplacer X par le le ment qui lui est imme diatement infe rieur : le
MAX dans ABG(N)

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
3. N a 2 fils : 2 solutions
remplacer X par le le ment qui lui est imme diatement infe rieur : le
MAX dans ABG(N)

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :
3. N a 2 fils : 2 solutions
remplacer X par le le ment qui lui est imme diatement infe rieur : le
MAX dans ABG(N)

Suppression dun lment

Pour supprimer un e le ment X dans A, il faut :
de terminer la place de X dans A : nud N
supprimer X et re organiser les e le ments de A. 3 cas possibles :

3. N a 2 fils : 2 solutions
remplacer X par le le ment qui lui est imme diatement infe rieur : le MAX
dans ABG(N) :
on cre e une fonction qui renvoie et supprime le MAX dun ABR, cest-a -dire l
e le ment le plus a droite.
ELEMENT SupprimerMax (ABR A)
De but
SI ABRVide(ABD(A)) ALORS
ELEMENT racine ValeurRacine(A)
A ABG(A)
renvoyer racine
SINON
SupprimerMax (ABD(A) )
FINSI
Fin

Suppression dun lment

ABRSupprimer(ELEMENT X, ABR A)
De but
SI non ABRVide(A) ALORS
SI X < ValeurRacine(A) ALORS
ABRSupprimer(X, ABG(A) )
SINON
SI X > ValeurRacine(A) ALORS
ABRSupprimer (X, ABD(A) )
SINON /* On a trouve le le ment */
SI ABRVide(ABG(A)) ALORS
A ABD(A) /* 0 ou 1 fils : le fils droit*/
SINON
SI EstVide(ABD(A)) ALORS
A ABG(A) /* 1 fils : le fils gauche */
SINON /* 2 fils */
Etiquette de A SupprimerMax (ABG(A))
FSI
FSI
FSI
FSI
FSI
FIN

Proprits des arbres binaires

Proprits des arbres binaires

Proprie te s

un arbre binaire ayant n sommets a une hauteur h qui ve rifie

log2(n+1) 1 h(a) n 1

un arbre binaire de hauteur h a un nombre de sommets n qui ve rifie

h + 1 n 2h+1 -1

Mesure de complexite

parcours de chaque nud de larbre : en O(n)

parcours dune branche : complexite dans le pire des cas en O(h) = O(log
(n))

Objectif

avoir h minimum (arbre complet ou presque ou e quilibre )