1 of 51

LES ARBRES

CPGE - AGADIR MP-PSI-TSI

M.Gueroihi

2 of 51

ARBRES �TERMINOLOGIE DE BASE

Un arbre est un ensemble d'éléments appelés nœuds reliés par des arcs.

noeuds

arcs

3 of 51

ARBRES �TERMINOLOGIE DE BASE

Les arbres sont enracinés. Une fois la racine définie 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.

niveau 0

niveau 1

niveau 2

niveau 3

nœuds internes

feuilles

parent

fils

racine

4 of 51

ARBRES �EXEMPLES

La racine est le nœud 1.

Le père est placé au dessus des fils.

Le segment reliant un fils à son père est un arc

5 of 51

ARBRES �EXEMPLES

Arbre représentant une expression arithmétique

((a-b)*(c/d))+e

6 of 51

ARBRES �EXEMPLES

Arbre généalogique :

L’arbre généalogique suivant représente quelques descendants mâles de Noé

7 of 51

ARBRES �DÉFINITION RÉCURSIVE

Un nœud unique est un arbre. Dans ce cas il est aussi la racine de l’arbre

Si n est un nœud et A₁, A₂, …A_k sont des arbres de racines respectives n₁, n₂, …, n_k

n₁

n₂

n_k

A₁

A₂

A_k

8 of 51

ARBRES �DÉFINITION RÉCURSIVE

alors on peut construire un arbre en associant comme père unique aux nœuds n₁, n₂, …, n_k_,le nœud n. dans ce nouvel arbre, n est la racine et A₁, A₂, …A_k sont les sous arbres de cette racine. Les nœuds n₁, n₂, …, n_k_,sont appelés les fils du nœud n

n₁

n₂

n_k

A₁

A₂

A_k

9 of 51

ARBRES �chemins entre nœuds

Si n₁, n₂, …, n_j,est une suite de nœuds telle que n_i est le père de n_i+1 pour i allant de 1 à j-1, alors cette suite est appelée chemin entre le nœud n₁ et le nœud n_j

n₁, n₂ ,n₃et n₄: chemin entre le nœud n₁ et le nœud n₄

La longueur du chemin est le nombre de nœuds - 1 (=nombre d’arcs).

La longueur du chemin entre le nœud n₁ et le nœud n₄=

n₁

n₂

n₃

n₄

10 of 51

ARBRES�Ascendants et descendants�

S’il existe un chemin entre les nœuds a et b alors a est dit ascendant de b (ou ancêtre), b et dit descendant de a.

Tout nœud est un de ses descendants et un de ses ascendants .

Tout nœud ascendant ou descendant d’un nœud différent de lui-même est un ascendant ou descendant propre.

Dans un arbre seule la racine n’a pas d’ascendant propre.

Un nœud sans descendant propre est appelé

Des nœuds ayant le même père sont appelés

Un nœud qui n’est pas une feuille est un

Un arbre sans nœud est un

Frères.

nœud interne

arbre vide.

Feuille.

n₃

11 of 51

ARBRES�Ascendants et descendants�

1, 3, 7, 9 est un chemin de longueur :

1, 3, 6 n’est pas un chemin

Les descendants propres de 3 sont :

Les fils de 3 sont :

Le père de 3 est :

Les ascendants propres de 7 sont :

Les feuilles de l’arbre sont :

4, 5 et 6 sont

7, 8 et 9

7 et 8

1 et 3

4, 5, 6, 8 et 9

frères

12 of 51

ARBRES� Hauteur et profondeur �

La hauteur d’un nœud dans un arbre est la longueur du plus long chemin que l’on peut mener entre ce nœud et une feuille de l’arbre.

La hauteur de 3 est :

La hauteur de l’arbre est :

La hauteur d’un arbre est la hauteur de sa racine.

13 of 51

ARBRES�Hauteur et profondeur�

La profondeur de 3 est :

La profondeur d’un nœud est la longueur du chemin entre la racine et ce nœud

La hauteur de 3 est :

14 of 51

ARBRES�Ordre des nœuds �

Les fils d’un arbre sont habituellement ordonnés de gauche à droite

Les deux arbres ci-dessous sont différents

15 of 51

ARBRES�Ordre des nœuds �

L’ordre gauche-droit peut être prolongé pour comparer des nœuds qui ne sont ni ascendants ni descendants.
Si b et c sont deux frères, que b est à gauche de c, tout descendant de b est à gauche de tout descendant de c

2 est à gauche de 3

5 est à gauche de 7

4 est à gauche de 9

3 n’est ni à gauche ni à droite de 9.

16 of 51

ARBRES BINAIRES �(AB)

Un arbre binaire est un arbre dont chaque nœud a au maximum deux fils.
Les arbres binaires distinguent le fils gauche du fils droit.
Ces deux arbres binaires sont différents :

Définition

17 of 51

ARBRES BINAIRES �(AB)

Dans un arbre binaire dégénéré ou filiforme chaque nœud a un seul fils

Un arbre binaire complet est un arbre binaire dont chaque nœud a deux fils ou est une feuille

Arbre binaire Complet

Arbre binaire pas complet

Définition

18 of 51

ARBRES BINAIRES �Parcours d’un arbre binaire

Parcours en profondeur d’bord

Parcours préfixe.

Le parcours préfixe est décrit récursivement :

Visiter la racine
Visiter le sous-arbre gauche en parcours préfixe
Visiter le sous-arbre droit en parcours préfixe

Un affichage préfixe donnerait :

19 of 51

ARBRES BINAIRES �Parcours prefixe

Algorithme

affichagePrefixe(a) :

Si non vide(a) :

afficher(val(a))

affichagePrefixe(filsGauche(a))

affichagePrefixe(filsDroit(a))

def prefixe(a):

if not vide(a):

print (val(a), end=' ')

prefixe(filsGauche(a))

prefixe(filsDroit(a))

Fonction Python

20 of 51

ARBRES BINAIRES �Parcours d’un arbre binaire

Parcours en profondeur d’bord

Parcours infixe.

Le parcours infixe est décrit récursivement :

Visiter le sous-arbre gauche en parcours infixe
Visiter la racine
Visiter le sous-arbre droit en parcours infixe

Un affichage infixe donnerait :

21 of 51

ARBRES BINAIRES �Parcours infixe

Algorithme

affichageInfixe(a) :

Si non vide(a) :

affichageInfixe(filsGauche(a))

afficher(val(a))

affichageInfixe(filsDroit(a))

def infixe(a):

if not vide(a):

infixe (filsGauche(a))

print (val(a), end=' ')

infixe (filsDroit(a))

Fonction Python

22 of 51

ARBRES BINAIRES �Parcours d’un arbre binaire

Parcours en profondeur d’bord

Parcours postfixe.

Le parcours postfixe est décrit récursivement :

Visiter le sous-arbre gauche en parcours postfixe
Visiter le sous-arbre droit en parcours postfixe
Visiter la racine

Un affichage infixe donnerait :

23 of 51

ARBRES BINAIRES �Parcours postfixe

Algorithme

affichagepostfixe(a) :

Si non vide(a) :

affichagePostfixe(filsGauche(a))

affichagePostfixe(filsDroit(a))

afficher(val(a))

def postFixe(a):

if not vide(a):

postFixe(filsGauche(a))

postFixe(filsDroit(a))

print (val(a), end=' ')

Fonction Python

24 of 51

ARBRES BINAIRES �Parcours d’un arbre binaire

Parcours en largeur

Visiter les nœuds niveau par niveau depuis la racine:
Peut être décrit facilement en utilisant une File

Un affichage en largeur donnerait :

25 of 51

ARBRES BINAIRES �Parcours en largeur

Algorithme

affichageLargeur(a):

F : File #File FIFO

Enfiler(a,F) #enfiler la racine a dans la file F

tantque non vide(F):

n=Défiler(F)

Afficher(val(n))

si non vide(filsGauche(n)):

Enfiler(filsGauche(n),F) #enfiler le fils gauche de n dans F

si non vide(filsDroit(n)):

Enfiler(filsDroit(n),F) #enfiler le fils droit de n dans F

26 of 51

affichageLargeur(a):

F : File #File FIFO

Enfiler(a,F) #enfiler la racine a dans la file F

tantque non vide(F):

n=Défiler(F)

Afficher(val(n))

si non vide(filsGauche(n)): Enfiler(filsGauche(n),F)

si non vide(filsDroit(n)): Enfiler(filsDroit(n),F)

27 of 51

ARBRES BINAIRES �Parcours en largeur

def parcoursLargeur(a):

F=[] #File FIFO

F.append(a) #enfiler la racine a dans la file F

while not vide(F):

n=F.pop(0) #défiler F (récupérer la tète)

print(val(n),end=' ')

if not vide(filsGauche(n)):

F.append(filsGauche(n)) #enfiler le fils gauche de n dans F

if not vide(filsDroit(n)):

F.append(filsDroit(n)) #enfiler le fils droit de n dans F

print()

Fonction Python

28 of 51

ARBRES BINAIRES�Mise en œuvre des arbres binaires.

En Python, on peut représenter :

- un arbre vide par une liste vide [ ] .

- un arbre non vide par une liste comprenant 3 éléments :

[clé , filsGauche , filsDroit].

Exemple

A = [ ] #A est un arbre vide

A = [12, [ ], [ ] ] #A est un arbre qui contient un seul nœud (12)

A=[12, [ 1, [ ], [ ] ] , [ 7, [ ], [ ] ] ]

29 of 51

ARBRES�Mise en œuvre des arbres binaires.

A=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

A=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ 82,[ ], [ ] ] ] ]

30 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

#Fonction qui détermine si un arbre a est vide ou non.

def vide(a):

return a==[]

#Fonction qui retourne la valeur de la racine d’un arbre (étiquette).

def val(a):

if not vide(a):

return a[0]

else:

return None

>>> a=[12, [ 1, [ ], [ ] ] , [ 7, [ ], [ ] ] ]

>>>val(a)

31 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

#Fonction qui retourne le fils gauche de l’arbre a.

def filsGauche(a):

if not vide(a):

return a[1]

else:

return []

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>filsGauche(a)

[ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ]

32 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

#Fonction qui retourne le fils droit de l’arbre a.

def filsDroit(a):

if not vide(a):

return a[2]

else:

return []

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>filsDroit(a)

[ 7, [ ], [ ] ]

33 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

Fonctions de parcours.

#Affichage préfixe d’un arbre binaire (fonction récursive)

def prefixe(a):

if not vide(a):

print (val(a), end=' ')

prefixe(filsGauche(a))

prefixe(filsDroit(a))

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>prefixe(a)

12 1 91 67 7

34 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

Fonctions de parcours.

#Affichage préfixe en utilisant un traitement itératif (en utilisant une Pile)

def prefixeIter(a):

P=[] # Pile vide

P.append(a) # empiler la racine dans la pile P

while not vide(P):

n=P.pop() # dépiler p et récupérer la tète (nœud n)

print(val(n),end=' ')

if not vide(filsDroit(n)):

P.append(filsDroit(n)) # empiler le fils droit de n dans P

if not vide(filsGauche(n)):

P.append(filsGauche(n)) # empiler le fils gauche de n dans P

print()

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

>>> prefixeIter(a)

12 1 91 67 7

35 of 51

def prefixeIter(a):

P=[] # Pile vide

P.append(a) # empiler la racine dans la pile P

while not vide(P):

n=P.pop() # dépiler p et récupérer la tète (nœud n)

print(val(n),end=' ')

if not vide(filsDroit(n)) : P.append(filsDroit(n))

if not vide(filsGauche(n)) : P.append(filsGauche(n))

print()

36 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

Fonctions de parcours.

#Affichage infixe d’un arbre binaire (fonction récursive)

def infixe(a):

if not vide(a):

prefixe(filsGauche(a))

print (val(a), end=' ')

prefixe(filsDroit(a))

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>infixe(a)

91 1 67 12 7

37 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

Fonctions de parcours.

#Affichage postfixe d’un arbre binaire (fonction récursive)

def postfixe(a):

if not Vide(a):

postfixe(filsGauche(a))

postfixe(filsDroit(a))

print (val(a), end=' ')

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>postfixe(a)

91 67 1 7 12

38 of 51

ARBRES BINAIRES �FONCTIONS DE BASE�

Fonctions de parcours.

#Affichage en largeur d’un arbre binaire - traitement itératif (en utilisant une File)

def parcoursLargeur(a):

F=[] #File FIFO

F.append(a) #enfiler la racine a dans la file F

while not vide(F):

n=F[0] ; F=F[1:] #défiler F (récupérer la tète)

print(val(n),end=' ')

if not vide(filsGauche(n):

F.append(filsGauche(n)) #enfiler le fils gauche de n dans F

if not vide(filsDroit(n):

F.append(filsDroit(n)) #enfiler le fils droit de n dans F

print()

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ ],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>parcoursLargeur(a)

12 1 7 91 67

39 of 51

def parcoursLargeur(a):

F=[] #File FIFO

F.append(a) #enfiler la racine a dans la file F

while not vide(F):

n=F[0] ; F=F[1:] #défiler F (récupérer la tète)

print(val(n),end=' ')

if not vide(filsGauche(n): F.append(filsGauche(n))

if not vide(filsDroit(n) : F.append(filsDroit(n))

print()

40 of 51

ARBRES BINAIRES �fonctions de base

# déterminer si un nœud est une feuille

def estFeuille(a):

if vide(a) : return False

return a[1]==[] and a[2]==[]

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ 80,[ ],[ ]],[ ]] ] , [ 7, [ ], [ ] ] ]

>>> estFeuille(a)

False

>>> a=filsGauche(a)

>>> estFeuille(a)

False

>>> a=filsGauche(a)

>>> val(a) , estFeuille(a)

91 , True

41 of 51

ARBRES BINAIRES �fonctions de base

#hauteur d’un arbre

La hauteur d’un arbre est la longueur du plus long chemin que l’on peut mener entre la racine et une feuille de l’arbre.

La hauteur d'un arbre est très importante. En effet, c'est un repère de performance. La plupart des algorithmes que nous verrons dans la suite ont une complexité qui dépend de la hauteur de l'arbre. Ainsi plus l'arbre aura une hauteur élevée, plus l'algorithme mettra de temps à s'exécuter.

un arbre vide est de hauteur : 0
un arbre qui ne contient qu’un seul nœud (racine) est de hauteur : 0
un arbre non vide et qui contient plus qu’un nœud a pour hauteur :

1 + la hauteur maximale entre ses fils.

def hauteur(a):

if vide(a) or estFeuille(a):

return 0

else:

return 1 + max(hauteur(filsGauche(a)),hauteur(filsDroit(a)))

42 of 51

ARBRES BINAIRES �fonctions de base

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ 80,[ ],[ ]],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>hauteur(a)

#hauteur d’un arbre

43 of 51

ARBRES BINAIRES �fonctions de base

#calculer le nombre de nœuds d’un arbre

def nombreNoeuds(a):

if vide(a):

return 0

else:

return 1+nombreNoeuds(filsGauche(a))+ nombreNoeuds(filsDroit(a))

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ 80,[ ],[ ]],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>nombreNoeuds(a)

44 of 51

ARBRES BINAIRES �fonctions de base

#calculer le nombre de feuilles dans un arbre

def nombreFeuilles(a):

if vide(a):

return 0

elif estFeuille(a):

return 1

else:

return nombreFeuilles(filsGauche(a))+ nombreFeuilles(filsDroit(a))

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ 80,[ ],[ ]],[ ]] ] , [ 7, [ ], [ ] ] ]

>>>nombreFeuilles(a)

45 of 51

ARBRES BINAIRES �fonctions de base

# déterminer si un nœud est un nœud interne

def estNoeudInterne(a):

if vide(a) : return False

return not estFeuille(a)

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ 80,[ ],[ ]],[ ]] ] , [ 7, [ ], [ ] ] ]

>>> estNoeudInterne(a)

True

>>> a=filsGauche(a)

>>> estNoeudInterne(a)

True

>>> a=filsGauche(a)

>>> val(a) , estNoeudInterne(a)

91 , False

46 of 51

ARBRES BINAIRES �fonctions de base

#calculer le nombre de nœuds internes dans un arbre

def nombreNoeudInternes(a):

if vide(a):

return 0

elif estFeuille(a):

return 0

else:

return 1+ nombreFeuilles(filsGauche(a))+ nombreFeuilles(filsDroit(a))

>>>a=[12, [ 1, [91,[ ],[ ] ], [67,[ 80,[ ],[ ]],[ ]] ] , [ 7, [ ], [ ] ] ]

>>> nombreNoeudInternes(a))

47 of 51

ARBRES BINAIRES �fonctions de base

#fonction de recherche d’une valeur x dans un arbre binaire quelconque

def existe(a, x):

if vide(a):

return False

else:

if val(a) ==x:

return True

else:

return existe(filsGauche(a),x) or existe(filsDroit(a), x)

48 of 51

ARBRES BINAIRES DE RECHERCHE�(ABR)

Un arbre binaire de recherche (ABR) est un arbre étiqueté tel que pour tout nœud n :
Tout nœud du sous arbre gauche a une valeur inférieure ou égale à la valeur de n.
Tout nœud du sous arbre droit a une valeur supérieure à la valeur de n.

Définition

49 of 51

ARBRES BINAIRES DE RECHERCHE�(ABR)

Exemple

Si on fait un parcours infixe de l’arbre, on obtient la liste des valeurs des nœuds triée en ordre croissant :

Dans l’exemple : 3 – 4 – 5 – 9 – 12 – 18 – 19 – 20

50 of 51

ARBRES BINAIRES DE RECHERCHE�(ABR)

Exemple

Il existe plusieurs représentations du même ensemble d’éléments par des arbres binaires de recherche.
Par exemple, les 2 arbres suivants représentent le même ensemble de chiffres :

51 of 51

ARBRES BINAIRES DE RECHERCHE�(ABR)

Intérêt

Maintenant que nous connaissons la compléxité de searchABR que peut-on dire des autres opérations?

Insertion ………… O(log N)

Suppression ………… O(log N)

Trouver le Min ………… O(log N)

Trouver le Max ………… O(log N)

Tri ABR = ………… O(N log N)

Idée: ABR tri = (Construction de l’ABR : N insertions)

+ (Parcourir ABR)

Pourquoi?