Les structures arborescentes : Arbres

Arbres
 Un arbre est une structure de données organisées de façon
hiérarchique, à partir d’un nœud distingué appelé racine.
 Très importante en informatique : Arbre de jeux (i.e., Echecs ),
système de fichiers UNIX/Windows, Arbres de tri
 Expressions Arithmétiques
 L’expression A - (B + C * (D - E)) * F
se représente facilement par un arbre où apparaît
clairement la priorité des opérations:

A. Naceur Turki Algorithmique et structures de données 2

 Arbres
 Nous étudierons :
1. Arbres Binaires et Arbres Binaires de Recherche (ABR)
2. Arbres Binaires de Equilibrés (AVL & TAS)
3. Arbres M-aire de Recherche (AMR)
4. Arbres M-aire de Recherche Equilibrés (B-Arbres)

A. Naceur Turki Algorithmique et structures de données 3

 Arbres: définitions
 Un arbre est un ensemble de Nœuds, reliés par
des Arêtes. Entre deux nœuds il existe toujours
un seul chemin.

noeuds

arêtes
A. Naceur Turki Algorithmique et structures de données 4
 Arbres: définitions
 Les arbres sont enracinés. Une fois la racine définit tous les
nœuds admettent un niveau.
 Les arbres ont des nœuds internes et des feuilles (nœuds
externes). Chaque nœud (à l’exception de la racine) a un parent
et admet zéro ou plusieurs fils.
racine
niveau 0
niveau 1 nœuds internes
niveau 2
parent
niveau 3 et
A. Naceur Turki Algorithmique et structures de données
feuilles fils 5
 Arbres: définitions
 Taille de l’arbre: est le nombre de nœuds qu’il possède.
 Degré d’un nœud: est le nombre de ses fils.
 Degré d’un arbre: est le degré maximum de ses nœuds.
 Hauteur d’un nœud: est la longueur du plus long chemin de ce
nœud aux feuilles qui en dépendent plus 1.
 C’est le nombre de nœuds du chemin.
 La hauteur d’un arbre est la hauteur de sa racine.
 L’arbre vide a une hauteur 0.
 L’arbre réduit à une racine étiqueté a une hauteur 1.
 Profondeur d’un nœud: est le nombre de nœuds du chemin qui
va de la racine à ce nœud
A. Naceur Turki Algorithmique et structures de données 6
 Arbres: typologie
 Les arbres sont classifiés selon:
 leur degré m≥2: On trouve les arbres binaires (m = 2), ternaires
(m=3), quaternaires (m = 4) ,…….., m-aire (m>2).
 la priorité d’ordre: entre le nœud père et ses fils, où :
 le nœud père possède au moins une clé, les valeurs de sous
arbre gauche (droit resp.) de la clé sont strictement inferieures
(supérieures ou égales resp.) à la valeur de la clé. On parle ici
des arbres binaires de recherche (où chaque nœud possède une
clé) et des arbres m-aire de recherche (où chaque nœud possède
(m-1) clé),
 la valeur du nœud père est supérieure (inferieure resp.) à la
valeur de ses fils. On parle ici du TASmax (TASmin)
 La propriété
A. Naceur Turki d’équilibrage:
Algorithmique etoù lesdefeuilles
structures données se situent aux derniers
7

niveaux. On trouve AVL, TAS, B-arbres …

 Arbres Binaires
 Un Arbre Binaire est un ensemble de nœuds qui
est soit vide, soit composé d’une racine et de deux
arbres disjoints appelés sous-arbre droit et sous-
arbre gauche.
 un arbre où chaque nœud admet au plus 2 fils.

A. Naceur Turki Algorithmique et structures de données 8

Arbres Binaires: Représentation par
tableaux
 Un arbre binaire peut être représenté par un tableau A :

 Mémoriser les nœuds séquentiellement de la racine

aux feuilles et de gauche vers la droite.
 Fils gauche de A[i] est en A[2i]
 Fils droit de A[i] est en A[2i + 1]
 Parent de A[i] est en A[i/2]

A. Naceur Turki Algorithmique et structures de données 9

Arbres Binaires: Représentation par
tableaux
1 • Fils gauche de A[i] est en A[2i]
14 • Fils droit de A[i] est en A[2i + 1]
• Parent de A[i] est en A[i/2]
2 3
10 16
4 5 6 7
8 12 15 18
8 9 10 11
7 9 11 13

1 2 3 4 5 6 7 8 9 10 11
tab A: 14 10 16 8 12 15 18 7 9 11 13
A. Naceur Turki Algorithmique et structures de données 10
Arbres Binaires: Représentation par
pointeurs
Nœud= enregistrement
val : entier
FG : ^ Nœud
FD : ^ Nœud
Fin enregistrement

Arbre : ^ Nœud

A. Naceur Turki Algorithmique et structures de données 11

 Arbres Binaires : Création
 Cette primitive retourne un arbre vide. Il suffit de déclarer un
pointeur sur un arbre binaire et de l’initialiser à Nil.

Fonction Créer_arbre_vide () : Arbre

Var
A : Arbre
Début
A←Nil
Retourner (A)
Fin

A. Naceur Turki Algorithmique et structures de données 12

 Arbres Binaires : Création
 Tester la vacuité d’un arbre
Fonction est_arbre_vide (A: arbre) : booléen
Début
Retourner (A =Nil)
Fin
 Tester si la racine est une feuille
Fonction est_Feuille (A: arbre) : booléen
Début
Si (A^.FG = nil) et (A^.FD = nil)) alors
Retourner vrai
Sinon
Retourner faux
Finsi
A. Naceur Turki Algorithmique et structures de données 13
Fin
 Parcours
 Le parcours d’un arbre consiste à passer par tous ses nœuds.
 On distingue deux types de parcours:
Des parcours en profondeur explorent l’arbre branche par branche
où on descend le plus profondément possible dans l’arbre puis une
fois qu’une feuille a été atteinte, on remonte pour explorer les autres
branches en commençant par la branche « la plus basse » parmi celles
non encore parcourues.
Des parcours en largeur explorent l’arbre niveau par niveau.

A. Naceur Turki Algorithmique et structures de données 14

 Parcours : InOrdre
InOrdre est décrit réursivement :

• Visiter le sous-arbre gauche en InOrdre

• Visiter la racine
• Visiter le sous-arbre droit en InOrdre

A. Naceur Turki Algorithmique et structures de données 15

 Parcours : InOrdre
Procédure Infixe(A: arbre)
Début
Si (NON est_arbre_vide (A)) alors
Infixe (A^.FG)
Ecrire (A^.val)
Infixe (A^.FD)
Finsi
Fin

A. Naceur Turki Algorithmique et structures de données 16

 Parcours : PréOrdre
PréOrdre est décrit réursivement :

• Visiter la racine
• Visiter le sous-arbre gauche en PréOrdre
• Visiter le sous-arbre droit en PréOrdre

A. Naceur Turki Algorithmique et structures de données 17

 Parcours : PréOrdre
Procédure Préfixe(A: arbre)
Début
Si (NON est_arbre_vide (A)) alors
Ecrire (A^.val)
Préfixe (A^.FG)
Préfixe (A^.FD)
Finsi
Fin

A. Naceur Turki Algorithmique et structures de données 18

 Parcours: PostOrdre
PostOrdre est décrit réursivement :

• Visiter le sous-arbre gauche en PostOrdre

• Visiter le sous-arbre droit en PostOrdre
• Visiter la racine

A. Naceur Turki Algorithmique et structures de données 19

 Parcours: PostOrdre
Procédure Postfixe(A: arbre)
Début
Si (NON est_arbre_vide (A)) alors
Postfixe (A^.FG)
Postfixe (A^.FD)
Ecrire (A^.val)
Finsi
Fin

A. Naceur Turki Algorithmique et structures de données 20

 Parcours: Exemple
Parcours des arbres binaires  Préordre :
a, b, c, i, j, e, f, g, h.

 Inordre :
i, c, j, b, e, a, g, f, h

 Postordre:
i, j, c, e, b, g, h, f, a.

A. Naceur Turki Algorithmique et structures de données 21

 Parcours: LevelOrdre
LevelOrdre visite les noeuds niveau par niveau depuis la racine:
• Peut être décrit facilement en utilisant une File (Comment??)
• Parcours appelé “Breadth First Search” (parcours en largeur)
dans les graphes

A. Naceur Turki Algorithmique et structures de données 22

 Arbre Binaire de Recherche
 Un Arbre Binaire de Recherche (ABR) est un arbre binaire
avec les propriétés suivantes :

 La clé associée à un nœud est supérieur aux clés des

nœuds de son sous-arbre gauche

 La clé associée à un nœud est inférieur aux clés des

nœuds de son sous-arbre droit
 Généralement, les valeurs dans un ABR sont uniques; on
n’admet pas de répétition de valeur pour éviter les confusion.
Mais si jamais ceci arrive : par exemple si un arbre contient
deux fois la valeur 4, par convention, la deuxième valeur est
A. Naceur Turki Algorithmique et structures de données 23
stockée dans le sous-arbre droit ayant pour racine 4.
 Arbre Binaire de Recherche:
Exemples
racine
racine
14
C
10 16
A D racine
8 11 15 18
14

10 16

8 11 15
A. Naceur Turki Algorithmique et structures de données 24
 ABR: InOrdre
Exemple:

InOrdre visites :
14
(8)
(10)
10 16 (11)
(14)
8 11 15 18
(15)
(16)
(18)
NOTER ! Le parcours InOrdre visite les clés dans l’ordre croissant.
A. Naceur Turki Algorithmique et structures de données 25
 ABR : Rechercher un élément
Soit un ABR :

G D

Problème: rechercher un nœud avec une clé x ?

A. Naceur Turki Algorithmique et structures de données 26

 ABR : Rechercher un élément
rechercher(racine, x) Exemple:
comparer x à la clé de racine:
- si x = clé return
- si x < clé => chercher dans G 14
- si x > clé => chercher dans D
10 16
chercher de la même manière
dans G ou D 8 11 15

x=8 (oui) x=17 (non)

A. Naceur Turki Algorithmique et structures de données 27
 ABR : Ajout d’un élément

Comment ajouter une clé? Exemple:

La même procédure que
Recherche_rec s’applique: 10
Déterminer la position
d’insertion par Recherche_rec. 8 ajout 4?
Ajouter la nouvelle clé si la
recherche échoue. 3 9 4

2 5

A. Naceur Turki Algorithmique et structures de données 28

 ABR : Ajout d’un élément
Exemple: ajouter C A B L M (dans l’ordre!)

1) Ajouter C 2) ajouter A 3) ajouter B C

C
C A
A
B
4) Ajouter L C 5) Ajouter M C
A L
A L
A. Naceur Turki B Algorithmique et structures de données 29
B M
 Construction d’un ABR
 L’ABR est-il unique pour une séquence de lettres A B C
LM?
NON! différentes séquences donnent différents ABR

Ajout de : A B C L M Ajout de : C A B L M
A
C
B
A L
C
L B M
A. Naceur Turki Algorithmique et structures de données 30
M
 ABR : Supprimer un élément
 Pour supprimer un nœud dans un ABR, plusieurs cas de figure
peuvent se présenter. Il est toutefois nécessaire d’obtenir un ABR à
l’issue de la suppression.
 D’abord il faut chercher l’élément à supprimer, une fois trouvé on
se trouve dans l’une des situations suivantes, soit « x » le nœud à
supprimer:
 1er cas : x est une feuille : on la supprime et on la remplace par Nil.
 2eme cas : x est un nœud qui a un seul fils : on supprime x et on le
remplace par ce fils.
 3eme cas : x est un nœud qui a deux fils : on supprime x et on le
remplace par l’élément minimum se trouvant dans son sous arbre droit
(le nœud le plus à gauche du sous arbre droit)ou par l’élément
A.maximum
Naceur Turki se trouvant Algorithmique
dans son données gauche (le nœud le plus
sousde arbre
et structures 31 à
droite du sous arbre gauche).
 ABR : Supprimer un élément
 Cas 1 : Suppression d'une feuille
 Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
 Exemple: supprimer le nœud i qui contient la valeur 8
1. Rechercher(8)
20
2. Libérer le nœud «i»
15 59

5 27 71

3 10 33

«i » 12 55
8
A. Naceur Turki Algorithmique et structures de données 32
52
 ABR : Supprimer un élément
 Cas 2: Suppression d'un nœud avec un fils
 Il suffit de l'enlever de l'arbre en liant son père avec son fils.
 Exemple: supprimer le nœud « i » qui contient la valeur 10
1. Rechercher(10)
20
2. Chainer le père de iavec le FD(i)
3. Libérer le nœud «i» 15 59

5 27 71

3 10 33
«i »

12 55

A. Naceur Turki Algorithmique et structures de données 33

52
 ABR : Supprimer un élément
 Cas 2: Suppression d'un nœud avec un fils
 Il suffit de l'enlever de l'arbre en liant son père avec son fils.
 Exemple: supprimer le nœud i qui contient la valeur 27
1. Rechercher(27)
2. Chainer le père de i avec le FG(i)« i » 20
3. Libérer le nœud «i» 59
15

5 71

3 10 33

55
8
A. Naceur Turki Algorithmique et structures de données 34

52
 ABR : Supprimer un élément
Cas 3: suppression d’un nœud avec 2 fils

A. Naceur Turki Algorithmique et structures de données 35

 ABR : Supprimer un élément
En conclusion, pour supprimer le nœud « i » d’un ARB, on rencontre
une des situations suivantes :
Cas FG (i) FD (i) Action
Feuille Nil Nil Libérer le nœud «i»
Avec un Nil ≠Nil Chaîner le père au fils de « i » (FG(i) ou FD(i))
fils ≠Nil Nil ensuite libérer le nœud « i »

1. Rechercher le plus proche prédécesseur

Avec deux ou
≠Nil ≠Nil
fils successeur de « i », soit « P ».

A. Naceur Turki 2. Remplacer Info(i) par Info(P)

Algorithmique et structures de données 36

3. Supprimer le nœud « P »