Arbres

Algorithmique 1

Stéphane Grandcolas

Aix-Marseille Université

2023-2024

S. Grandcolas, 2024
Arbres

Arbre : structure très utilisée en informatique

▶ hiérarchique
▶ récursive
▶ dynamique

Programme
▶ définitions, vocabulaire,
▶ arbres binaires,
▶ arbres binaires de recherche (dictionnaire),

S. Grandcolas, 2024
Arbres

Arborescence des répertoires et fichiers (système Unix)

S. Grandcolas, 2024
Arbres

Arbre syntaxique représentant une expression arithmétique

x / +
× (78 + y )
(x − 1)
x − 78 y

x 1

S. Grandcolas, 2024
Arbres

Arbre min-max pour le calcul du meilleur coup

2-3-Game tree-1 [Link]

1 sur 1 14/09/2022 12:07

S. Grandcolas, 2024
Arbres

Un arbre lexicographique, ou arbre de préfixes ou trie

main
male
mie
m p
mite
pic
a i i o
pile
i l e t c l s r pis
port
n e e e t
porte
e

S. Grandcolas, 2024
Arbres : définition 1
Un arbre est un ensemble organisé de noeuds :
▶ chaque noeud a un père et un seul,
▶ excepté un noeud, la racine, qui n’a pas de père.

racine
Les fils d’un noeud p sont les noeuds
dont le père est p

Les feuilles d’un arbre sont

les noeuds qui n’ont pas de fils

traditionellement on représente le père au-dessus

de ses fils, et donc la racine tout en haut
feuilles

S. Grandcolas, 2024
Arbres : définition 2 (récursive)
Un arbre (non vide) est constitué
▶ d’un noeud p, sa racine,
▶ d’une suite de sous-arbres (a1 , a2 , . . . , ak ).

Les racines des arbres

a1 , a2 , . . . , ak sont les fils de p
....
a1 a2 ak

S. Grandcolas, 2024
Arbres : définition 3 (graphes)

Un arbre est un graphe connexe et sans cycle.

S. Grandcolas, 2024
Arbres : définition 3 (graphes)

Un graphe avec des cycles

S. Grandcolas, 2024
Arbres : définition 3 (graphes)

Un graphe non connexe

S. Grandcolas, 2024
Arbres : définition 3 (graphes)

Un graphe non connexe

S. Grandcolas, 2024
Arbres : définition 3 (graphes)

Graphe connexe et sans cycle : nb arêtes = nb sommets−1

S. Grandcolas, 2024
Arbres : vocabulaire

racine
niveaux
branche : chemin à la racine

ancetre

profondeur=2 hauteur=5

descendant frère

S. Grandcolas, 2024
Arbres binaires

Chaque noeud a potentiellement un fils gauche et un fils droit

sous−arbre gauche noeud

sous−arbre droit
(sa racine est )

fils gauche

fils droit

S. Grandcolas, 2024
Arbres binaires racine
1

nombre de noeuds
2

Arbre binaire parfait : 8

16
▶ à la profondeur p : 2p noeuds
h−1
X
▶ nombre total de noeuds : 2i = 2h − 1
i=0

Un arbre binaire de hauteur h contient au plus 2h − 1 noeuds

(avec la convention : hauteur = nombre de niveaux)

S. Grandcolas, 2024
Arbres binaires : représentation

Arbre vide : □

Arbre non vide : p = ⟨ x, G , D ⟩

▶ x = val(p) : élément, information, label, valeur,
▶ G = filsG (p) : sous-arbre gauche de p,
▶ D = filsD(p) : sous-arbre droit de p,
×

78 +

⟨×, ⟨78, □, □⟩, ⟨+, ⟨x, □, □⟩, ⟨6, □, □⟩⟩⟩ x 6

S. Grandcolas, 2024
Arbres binaires : implémentation
public class Node <T> {
T element;
Node filsG;
Node filsD;

// constructeurs, getters, setters

...
}

On utilisera null pour représenter l’arbre vide

S. Grandcolas, 2024
Arbres binaires : implémentation
public class Arbre <T> {
private Node racine;

public Arbre() {
this . racine = null;
}

boolean estVide() {
return ( this . racine == null);
}
...
}

Encapsulation : un Arbre a en attribut le noeud racine

S. Grandcolas, 2024
Arbres binaires : implémentation

12 racine
12

1 7

1 7
91 67 82
82
14 11 67
91

14
11

⟨12, ⟨1, ⟨91, □, ⟨14, □, □⟩⟩, ⟨67, □, □⟩⟩, ⟨7, □, ⟨82, ⟨11, □, □⟩, □⟩⟩⟩

S. Grandcolas, 2024
Arbres binaires : implémentation

12
racine
12
1 7 p
[Link]
91 67 82 1 7

82
14 11 67
91

14
11

[Link]

S. Grandcolas, 2024
Arbres binaires : parcours en profondeur

Principe : explorer le sous-arbre gauche, puis explorer le

sous-arbre droit

fonction EXPLORE(p),
si p ̸= □ alors
→ ici traitement avant
EXPLORE(filsG (p)),
→ traitement après l’exploration du fils gauche
EXPLORE(filsD(p)),
→ ici traitement après l’exploration du fil droit
finsi
fin fonction

S. Grandcolas, 2024
Arbres binaires : parcours préfixe
1

fonction PARCOURS-PREFIXE(p), 12
si p ̸= □ alors 2 5
1 7
Afficher(val(p)),
3 4 6
PARCOURS-PREFIXE(filsG (p)), 91 67 82
PARCOURS-PREFIXE(filsD(p)), 7
finsi 61
fin fonction
12 1 91 67 7 82 61

Parcours infixe : 91, 1, 67, 12, 7, 61, 82.

Parcours postfixe : 91, 67, 1, 61, 82, 7, 12.

S. Grandcolas, 2024
Arbres binaires : hauteur minimale
Propriété. Pour tout arbre A de taille n, n > 0,

h(A) ≥ ⌊log2 n⌋ + 1

taille : nombre de noeuds, h(A) : hauteur de l’arbre A

a1 a2

n1 noeuds n2 noeuds

S. Grandcolas, 2024
Arbres binaires : hauteur minimale
Propriété. Pour tout arbre A de taille n, n > 0,

h(A) ≥ ⌊log2 n⌋ + 1

taille : nombre de noeuds, h(A) : hauteur de l’arbre A

Preuve. Si n = 1 alors h(A) = 1, sinon
a
h(A) = 1 + max(h(A1 ), h(A2 ))

a1 a2

n1 noeuds n2 noeuds

S. Grandcolas, 2024
Arbres binaires : hauteur minimale
Propriété. Pour tout arbre A de taille n, n > 0,

h(A) ≥ ⌊log2 n⌋ + 1

taille : nombre de noeuds, h(A) : hauteur de l’arbre A

Preuve. Si n = 1 alors h(A) = 1, sinon
a
h(A) = 1 + max(h(A1 ), h(A2 ))
On suppose n1 ≥ n2 , et donc n1 ≥ n/2
Induction : h(A1 ) ≥ 1 + ⌊log2 n1 ⌋
donc h(A1 ) ≥ 1 + ⌊log2 n/2⌋ = ⌊log2 n⌋,
et puisque h(A) ≥ 1 + h(A1 ), a1 a2
on en déduit h(A) ≥ 1 + ⌊log2 n⌋.
n1 noeuds n2 noeuds

S. Grandcolas, 2024
Arbres binaires : hauteur minimale
Propriété. Pour tout arbre A de taille n, n > 0,

h(A) ≥ ⌊log2 n⌋ + 1

taille : nombre de noeuds, h(A) : hauteur de l’arbre A

Preuve. Si n = 1 alors h(A) = 1, sinon
a
h(A) = 1 + max(h(A1 ), h(A2 ))
On suppose n1 ≥ n2 , et donc n1 ≥ n/2
Induction : h(A1 ) ≥ 1 + ⌊log2 n1 ⌋
donc h(A1 ) ≥ 1 + ⌊log2 n/2⌋ = ⌊log2 n⌋,
et puisque h(A) ≥ 1 + h(A1 ), a1 a2
on en déduit h(A) ≥ 1 + ⌊log2 n⌋.
n1 noeuds n2 noeuds

⌈log2 nf ⌉ + 1 si nf est le nombre de feuilles.

S. Grandcolas, 2024
Arbres binaires : hauteur
Propriété. Pour tout arbre A constitué de n noeuds

⌊log2 n⌋ + 1 ≤ h(A) ≤ n

12 12
7
1 7
82
91 67 82 22
11
14 14 53 38 11 12 98 23 12

15 noeuds, h = 4 5 noeuds, h = 5

S. Grandcolas, 2024
Structure de données dictionnaire

Ensemble dynamique d’objets comparables qui supporte les

opérations suivantes :
estvide() : détermine si le dictionnaire est vide
ajouter(e) : ajout d’un élément
supprimer(e) : suppression d’un élément
rechercher(e) : recherche d’un élément

Implémentation : liste, tableau, arbre binaire de recherche,

table de hashage,. . .

Objectifs : être efficace, utiliser peu d’espace.

S. Grandcolas, 2024
Arbres binaires de recherche

Soit E un ensemble muni d’une relation d’ordre ≺ (ordre total)

Un arbre binaire A étiqueté avec des éléments de E est un
arbre binaire de recherche s’il satisfait l’ordre infixe, c’est à
dire, pour tous noeuds p, q ∈ A
▶ si q ∈ filsG (p) alors val(q) ≺ val(p),
▶ si q ∈ filsD(p) alors val(q) ≻ val(p).

Il n’y a pas dans l’arbre deux éléments avec la même clé.

(i.e. si x ⪯ y et y ⪯ x alors x et y sont le même élément)

S. Grandcolas, 2024
Arbres binaires de recherche

p
34

22 66

7 29 50 71

17 25 32 37 56 70 81

9 21 23 28 30 36 44 55 68 80 97

8 16 27 35 52 67 69 94

26 51 88

< 66 > 66

éléments pris dans (N, <)

S. Grandcolas, 2024
Arbres binaires de recherche : parcours infixé

Le parcours infixe de l’arbre produit la suite ordonnée des

éléments
16
34
7
22 66
1 13
7 29 50 71
5 9 15
17 25 32 37 56 70 81
3 6 8 12
9 21 23 28 30 14 36 44 55 68 80 97
2 4 17
11
8 16 27 35 52 67 69 94
10
26 51 88

7 8 9 16 17 21 22 23 25 26 27 28 29 30 32 34 35 36 37 ...

S. Grandcolas, 2024
ABR : Recherche d’un élément
Soit e un élément qui apparaît dans l’arbre de racine p. Si
e ̸= val(p) alors :
▶ soit e ≺ val(p) et e ∈ filsG (p),
▶ soit e ≻ val(p) et e ∈ filsD(p).

34
< 34

22 66
> 22
7 29 50 74
< 29

17 25 32 37 56 73 81
> 25
9 21 23 28 30 36 44 55 68 80 97
< 28
8 16 27 35 52 67 72 94

26 51 88

recherche de la valeur 27

S. Grandcolas, 2024
ABR : Recherche d’un élément

fonction RECHERCHE(x, p)
out : □ si x n’apparaît pas dans le sous-arbre enraciné en p,
le noeud de valeur x sinon,
si p = □ alors renvoyer □,
si val(p) = x alors renvoyer p,
si val(p) > x alors renvoyer RECHERCHE(x, filsG (p)),
renvoyer RECHERCHE(x, filsD(p)),
fin fonction

Parcours d’une branche : O(h(A))

S. Grandcolas, 2024
ABR : ajout d’un élément (insertion)

Ajout de la valeur 31

34

22 66

7 29 50 74

17 25 32 37 56 73 81

9 21 23 28 30 36 44 55 69 80 97

8 16 27 35 52 67 72 94

26 51 88

Même principe que la recherche : parcours d’une branche

S. Grandcolas, 2024
ABR : ajout d’un élément (insertion)

Ajout de la valeur 31

34

22 66

7 29 50 74

17 25 32 37 56 73 81

9 21 23 28 30 36 44 55 69 80 97

8 16 27 31 35 52 67 72 94

26 51 88

Ajout au bout de la branche

S. Grandcolas, 2024
ABR : ajout d’un élément (insertion)

fonction INSERER(x, p)
insère la valeur x dans l’arbre p, renvoie l’arbre résultant,
si p = □ alors renvoyer ⟨x, □, □⟩,
si val(p) > x alors filsG(p) :=INSERER(x,filsG(p)),
si val(p) < x alors filsD(p) :=INSERER(x,filsD(p)),
renvoyer p,
fin fonction

Parcours d’une branche : O(h(A))

S. Grandcolas, 2024
ABR : successeur
le noeud de valeur 66 a un fils droit,
son successeur est 67,
dernier fils gauche de
son sous−arbre gauche
34

22 66

7 29 50 71

17 25 32 37 56 70 81

9 21 23 28 30 36 44 55 68 80 97

8 16 27 31 35 52 67 69 94

26 51 88

S. Grandcolas, 2024
ABR : successeur
le noeud de valeur 32 n’a pas de fils droit :
son successeur est 34, premier ascendant de 32
tel que 32 figure dans son sous−arbre gauche

34

22 66

7 29 50 71

17 25 32 37 56 70 81

9 21 23 28 30 36 44 55 68 80 97

8 16 27 31 35 52 67 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 1 : le noeud n’a pas de fils : décrochage

34

22 66

7 29 50 71

17 25 32 37 56 70 81

9 21 23 28 30 36 44 55 68 80 97

8 16 27 31 35 52 67 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 1 : le noeud n’a pas de fils : décrochage

34

22 66

7 29 50 71

17 25 32 37 56 70 81

9 21 23 28 30 36 44 55 68 80 97

8 16 27 31 35 52 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 2 : le noeud a un seul fils : décrochage

34

22 66

7 29 50 71

17 25 32 37 56 70 81

9 21 23 28 30 36 44 55 68 80 97

8 16 27 31 35 52 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 2 : le noeud a un seul fils : décrochage

34

22 66

7 29 50 71

17 25 32 37 56 70 81

9 21 23 28 30 36 44 55 68 80 97

8 16 27 31 35 52 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 2 : le noeud a un seul fils : décrochage

34

22 66

17 29 50 71

9 21 25 32 37 56 70 81

8 16 23 28 30 36 44 55 68 80 97

27 31 35 52 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 3 : le noeud a deux fils

34 a supprimer

22 57

17 29 50 71

9 21 25 32 37 56 70 81

8 16 23 28 30 36 44 55 68 80 97

27 31 35 52 69 94

26 51 88

plus petit
des plus grands

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 3 (deux fils) : copie du plus petit des plus grands

34

22 57

17 29 50 71

9 21 25 32 37 56 70 81

8 16 23 28 30 36 44 55 68 80 97

27 31 35 52 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 3 (deux fils) : copie du plus petit des plus grands

34

22 68

17 29 50 71

9 21 25 32 37 56 70 81

8 16 23 28 30 36 44 55 68 80 97

27 31 35 52 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 3 (deux fils) : décrochage

34

22 68

17 29 50 71

9 21 25 32 37 56 70 81

8 16 23 28 30 36 44 55 68 80 97

27 31 35 52 69 94

26 51 88

S. Grandcolas, 2024
Arbres binaires de recherche : suppression

Cas 3 (deux fils) : décrochage

34

22 68

17 29 50 71

9 21 25 32 37 56 70 81

8 16 23 28 30 36 44 55 69 80 97

27 31 35 52 94

26 51 88

S. Grandcolas, 2024
ABR : suppression d’un élément
fonction SUPPRIMER(x, p)
si val(p) > x alors
filsG(p) :=SUPPRIMER(x,filsG(p)),
sinon si val(p) < x alors
filsD(p) :=SUPPRIMER(x,filsD(p)),
sinon si filsG(p) = □ alors
renvoyer filsD(p),
sinon si filsD(p) = □ alors
renvoyer filsG(p),
sinon
val(p) := GETMIN(filsD(p)),
filsD(p)) :=SUPPRIMER(val(p),filsD(p)),
renvoyer p,
fin fonction

Supprime la valeur x de l’arbre p, renvoie l’arbre résultant.

Suppose que l’élément est présent dans l’arbre.
S. Grandcolas, 2024
ABR : suppression d’un élément
fonction SUPPRIMER(x, p)
si val(p) > x alors x est dans le sous-arbre gauche
filsG(p) :=SUPPRIMER(x,filsG(p)),
sinon si val(p) < x alors
filsD(p) :=SUPPRIMER(x,filsD(p)),
sinon si filsG(p) = □ alors
renvoyer filsD(p),
sinon si filsD(p) = □ alors
renvoyer filsG(p),
sinon
val(p) := GETMIN(filsD(p)),
filsD(p)) :=SUPPRIMER(val(p),filsD(p)),
renvoyer p,
fin fonction

Supprime la valeur x de l’arbre p, renvoie l’arbre résultant.

Suppose que l’élément est dans le dictionnaire.
S. Grandcolas, 2024
ABR : suppression d’un élément
fonction SUPPRIMER(x, p)
si val(p) > x alors
filsG(p) :=SUPPRIMER(x,filsG(p)),
sinon si val(p) < x alors x est dans le sous-arbre droit
filsD(p) :=SUPPRIMER(x,filsD(p)),
sinon si filsG(p) = □ alors
renvoyer filsD(p),
sinon si filsD(p) = □ alors
renvoyer filsG(p),
sinon
val(p) := GETMIN(filsD(p)),
filsD(p)) :=SUPPRIMER(val(p),filsD(p)),
renvoyer p,
fin fonction

Supprime la valeur x de l’arbre p, renvoie l’arbre résultant.

Suppose que l’élément est dans le dictionnaire.
S. Grandcolas, 2024
ABR : suppression d’un élément
fonction SUPPRIMER(x, p)
si val(p) > x alors
filsG(p) :=SUPPRIMER(x,filsG(p)),
sinon si val(p) < x alors
filsD(p) :=SUPPRIMER(x,filsD(p)),
sinon si filsG(p) = □ alors val(p) = x, pas de fils gauche
renvoyer filsD(p),
sinon si filsD(p) = □ alors
renvoyer filsG(p),
sinon
val(p) := GETMIN(filsD(p)),
filsD(p)) :=SUPPRIMER(val(p),filsD(p)),
renvoyer p,
fin fonction

Supprime la valeur x de l’arbre p, renvoie l’arbre résultant.

Suppose que l’élément est dans le dictionnaire.
S. Grandcolas, 2024
ABR : suppression d’un élément
fonction SUPPRIMER(x, p)
si val(p) > x alors
filsG(p) :=SUPPRIMER(x,filsG(p)),
sinon si val(p) < x alors
filsD(p) :=SUPPRIMER(x,filsD(p)),
sinon si filsG(p) = □ alors
renvoyer filsD(p),
sinon si filsD(p) = □ alors val(p) = x, pas de fils droit
renvoyer filsG(p),
sinon
val(p) := GETMIN(filsD(p)),
filsD(p)) :=SUPPRIMER(val(p),filsD(p)),
renvoyer p,
fin fonction

Supprime la valeur x de l’arbre p, renvoie l’arbre résultant.

Suppose que l’élément est dans le dictionnaire.
S. Grandcolas, 2024
ABR : suppression d’un élément
fonction SUPPRIMER(x, p)
si val(p) > x alors
filsG(p) :=SUPPRIMER(x,filsG(p)),
sinon si val(p) < x alors
filsD(p) :=SUPPRIMER(x,filsD(p)),
sinon si filsG(p) = □ alors
renvoyer filsD(p),
sinon si filsD(p) = □ alors
renvoyer filsG(p),
sinon val(p) = x, deux fils,
val(p) := GETMIN(filsD(p)),
filsD(p)) :=SUPPRIMER(val(p),filsD(p)),
renvoyer p,
fin fonction

Supprime la valeur x de l’arbre p, renvoie l’arbre résultant.

Suppose que l’élément est dans le dictionnaire.
S. Grandcolas, 2024
Arbres binaires de recherche : suppression

fonction GETMIN(p)
si p = □ alors
renvoyer □,
si filsG(p) = □ alors
renvoyer p,
renvoyer GETMIN(filsG(p)),
fin fonction

S. Grandcolas, 2024
Arbres binaires de recherche : coûts

Structure insertion recherche suppression

tableau O(1) O(n) O(n)
tableau trié O(n) O(log n) O(n)
liste O(1) O(n) O(n)
ABR O(h) O(h) O(h)

où h est la hauteur de l’arbre :

1 + ⌊log2 n⌋ ≤ h ≤ n

S. Grandcolas, 2024