Chapitre 5 : Arbres Binaires
Pr. ADDOU Mohammed
[Link]@[Link]
Master Intelligence Artificielle et Sciences des Données
Module: Complexité algorithmique et Théorie des graphes
1
Les arbres
Un arbre est une structure de données (souvent
dynamique) représentant un ensemble de valeurs
organisées hiérarchiquement (non linéaire).
Chaque valeur est stockée dans un nœud.
Les nœuds sont connectés entre eux par des
arêtes qui représentent la relation parents/fils.
2
Les arbres
Racine: c’est le nœud qui n’a pas de prédécesseur
(parents) et possède 0 ou plusieurs fils.
Feuille: c’est un nœud qui n’a pas de successeurs
(fils). Une feuille est aussi appelée nœud externe.
Nœud interne: Les nœuds autre que la racine et
les feuilles sont appelés nœuds internes.
Une branche: Une branche est une suite de
nœuds consécutifs de la racine vers une feuille.
3
Les arbres
Sous-arbre: est une portion de l’arbre. Dans
l’exemple, le nœud F avec ses deux fils G et Z
constituent un sous-arbre.
Descendants d’un Nœud: sont tous les nœuds
du sous-arbre de racine ce nœud.
Exemple : les descendants de D sont ………….
Ascendants d’un nœud: sont tous les nœuds se
trouvant sur la branche de la racine vers ce nœud.
Exemple : les ascendants de F sont …………
4
Les arbres
profondeur d’un nœud: Longueur du chemin
entre la racine et ce nœud.
Le degré d'un nœud est égal au nombre de ses
fils
Le degré d'un arbre est égal au plus grand des
degrés de ses nœuds
5
Les arbres
Le niveau d’un nœud: est la distance qui le sépare de la racine.
• Niveau de la racine = 0
• Le niveau de chaque nœud est égal au niveau de son père plus 1
Le niveau du nœud contenant G est égal à 2.
6
Arbres binaires
Un arbre binaire est un cas particulier des arbres. Un arbre binaire est
un arbre ou chaque nœud possède au plus deux fils : le fils droit et le fils
gauche.
Un arbre binaire est :
• Soit vide.
• Soit compose d’une racine portant une valeur et d’une paire d’arbres
binaires, appelés fils gauche et fils droit.
7
Implémentation :
Un arbre peut être implémenté de plusieurs façons, dans ce qui suit on va
adopter l’implémentation suivante :
• Un nœud est une liste qui contient trois champs : un champ contenant
l'élément du nœud (peut être un entier, une chaîne de caractère ou tout
autre chose que l'on désire stocker). Les deux autres champs sont le fils
gauche et le fils droit du nœud.
• Chaque nœud possède la représentation de la figure :
Valeur arbreGauche arbreDroit
8
Implémentation :
Exemple: la représentation de l’arbre suivant en python est comme suit:
>>> arbre = [10, [8, [3, [], []], [15, [20, [], []], []]], [5, [4, [], []], []]]
Un arbre vide sera représenté par une liste vide.
9
Mesures sur les arbres binaires
La taille d'un arbre binaire B correspond au nombre de ses nœuds, elle est
définie par :
0
Taille(B)= …….. si B est un arbre vide
1+Taille(arbreGauche(B)) + Taille(arbreDroit(B)) sinon
Taille(B)= …………………………………………………..
10
Mesures sur les arbres binaires
La hauteur d'un arbre binaire B correspond au nombre de niveaux entre la
racine et la feuille la plus éloignée : elle est définie par :
0
Hauteur(B) = ……… si B est un arbre vide
Hauteur(B) = 1+Max( Huteur(arbreGauche(B) , Hauteur(arbreDroit(B)) ) sinon.
………………………………………………….
11
Parcours d'arbres binaires
Un parcours d’arbres est un algorithme qui permet de visiter chacun des
nœuds de cet arbre. Nous distinguerons deux types de parcours : le
parcours en profondeur et le parcours en largeur
12
Parcoure en profondeur:
Le principe est simple : pour parcourir l'arbre a, on parcourt
récursivement dans un ordre prédéfinie son sous-arbre gauche et son sous-
arbre droit. Ainsi chaque sous-arbre sera exploré dans sa totalité.
13
Parcours préfixe : [r,g,d]
la valeur du noeud courant est traitée avant les valeurs figurant dans ses
sous-arbres.
Si le traitement consiste simplement à afficher la valeur du nœud, le
parcours préfixe du l'arbre ci-dessous produirait l'affichage :
12 1 91 67 7 82 61
14
Parcours infixe : [g,r,d]
la valeur du noeud courant est traitée après les valeurs figurant dans son
sous-arbre gauche et avant les valeurs figurant dans son sous-arbre droit.
Le parcours infixe du l'arbre ci-dessous produirait l'affichage :
91 1 67 12 7 61 82
15
Parcours postfixe : [g,d,r]
la valeur du noeud courant est traitée après les valeurs de ses sous-arbres.
Le parcours postfixe du l'arbre ci-dessous produirait l'affichage :
91 67 1 61 82 7 12
16
Parcours en largeur
Le parcours en largeur consiste à parcourir l'arbre niveau par niveau. Les
nœuds de niveau 0 sont d'abord parcourus puis les nœuds de niveau 1 et
ainsi de suite. Dans chaque niveau, les nœuds sont parcourus de la gauche
vers la droite. Le parcours en largeur de l'arbre ci-dessus parcours les
12 1 7 91 67 82 61
nœuds dans l'ordre : …………………………………
17
Arbre binaire complet
Un arbre binaire est complet si toutes ses branches ont la même longueur
et tous ses noeuds qui ne sont pas des feuilles ont deux fils.
Soit A un arbre binaire complet. Le
nombre de noeuds au niveau p est 2𝑝 . En
particulier le nombre de feuilles est donc
2ℎ−1 si ℎ est la hauteur= nombre de
niveaux.
Le nombre total de noeuds d'un arbre
binaire complet de h niveaux est :
𝒉−𝟏 𝒊 𝒉−𝟏
𝒊=𝟎 𝟐 = 𝟐
18
Arbres binaires de recherche.
Arbres binaires de recherche (ABR)
19
Arbres binaires de recherche.
Introduction
Un arbre binaire de recherche (ou ABR) est une structure de donnée qui
permet de représenter un ensemble de valeurs si l'on dispose d'une
relation d'ordre sur ces valeurs. Les opérations caractéristiques sur les
arbres binaires de recherche sont l'insertion, la suppression, et la
recherche d'une valeur.
20
Arbres binaires de recherche.
Définition
Soit E un ensemble muni d'une relation d'ordre, et soit A un arbre
binaire portant des valeurs de E. L'arbre A est un arbre binaire de
recherche si pour tout noeud p de A, la valeur de p est plus grande que
les valeurs figurant dans son sous-arbre gauche et plus petite que les
valeurs figurant dans son sous-arbre droit.
21
Arbres binaires de recherche.
Caractéristiques
Pour accéder à la clé la plus petite (resp. la plus grande) dans un ABR
il sufit de descendre sur le fils gauche (resp. sur le fils droit) autant
que possible. Le dernier noeud visité, qui n'a pas de fils gauche (resp.
droit), porte la valeur la plus petite (resp. la plus grande) de l'arbre.
Remarque
Le parcours infixe de l'arbre produit une suite croissante des clés
22
Arbres binaires de recherche.
Recherche d'une valeur
La recherche d'une valeur dans un ABR consiste à parcourir une branche en partant
de la racine, en descendant chaque fois sur le fils gauche ou sur le fils droit suivant
que la clé portée par le noeud est plus grande ou plus petite que la valeur cherchée.
La recherche s'arrête dès que la valeur est rencontrée ou que l'on a atteint
l'extrémité d'une branche (le fils sur lequel il aurait fallu descendre n'existe pas).
23
Arbres binaires de recherche.
Insertion d'une nouvelle valeur
Insertion d'une nouvelle valeur. Le principe est le même que pour la
recherche. Un nouveau noeud est crée avec la nouvelle valeur et inséré à
l'endroit où la recherche s'est arrêtée.
24
Arbres binaires de recherche.
Recherche du successeur d'un noeud
Étant donné un noeud p d'un arbre A, le successeur de p, s'il existe, est le
noeud de A qui porte la plus petite des valeurs qui figurent dans A et qui
sont plus grandes que la valeur de p.
• Si p possède un fils droit, son successeur est le noeud le plus à gauche
dans son sous-arbre droit (on y accède en descendant sur le fils gauche
autant que possible).
• Si p n'a pas de fils droit alors son successeur est le premier de ses
ascendants tel que p apparaît dans son sous-arbre gauche.
• Si cet ascendant n'existe pas c'est que p portait la valeur la plus grande
dans l'arbre
25
Arbres binaires de recherche.
Recherche du successeur d'un noeud
26
Arbres binaires de recherche.
Suppression d'un noeud
L'opération dépend du nombre de fils du noeud à supprimer :
Cas 1 : le noeud à supprimer n'a pas de fils, c'est une feuille. Il sufit
d'enlever en modifiant le lien du père, si il existe, vers ce fils. Si le père
n'existe pas l'arbre devient l'arbre vide.
27
Arbres binaires de recherche.
Suppression d'un noeud
Cas 2 : le noeud à supprimer a un fils et un seul. Le noeud est décroché
de l'arbre comme dans le cas 1. Il est remplacé par son fils unique dans le
noeud père, si ce père existe. Sinon l'arbre est réduit au fils unique du
noeud supprimé.
28
Arbres binaires de recherche.
Suppression d'un noeud
Cas 3 : le noeud à supprimer p a deux fils. Il doit prendre comme valeur celle de son
successeur ou celle de son prédécesseur. Soit q le noeud de son sous-arbre gauche qui a
la valeur la plus grande (on peut prendre indifféremment le noeud de son sous-arbre
droit de valeur la plus petite). Il sufit de recopier la valeur de q dans le noeud p et de
décrocher le noeud q. Puisque le noeud q a la valeur la plus grande dans le fils gauche, il
n'a donc pas de fils droit, et peut être décroché comme on l'a fait dans les cas 1 et 2.
29
