14/04/2019
LES ARBRES Algorithme et structure de
données
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 1
INTRODUCTION
Certain données en informatique ont besoin d’être représentées par des arbres (disque dur)
Graphiquement: un élément stocké dans un arbre a des relations avec 1 ou plusieurs autres éléments de
l’arbre: s’il n’existe qu’une relation, nous revenons alors à une structure linéaire.
Domaine d’application: Base de données, système d’exploitation…etc
Représentation: hiérarchique ou imbriquée ( dictionnaires, questionnaire, [Link]étique, arbres
généalogiques…
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 2
14/04/2019
EXEMPLE
Expression arithmétique Dictionnaire Arbre généalogique
/ I
* + A R adem
e
a b * * I
S Mohamed haikel
c + a b i A
A
a b N
I Ali kacem Mounir
A
t
(a*b)/(c*(a+b)+(a*b))
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 3
DÉFINITION
un arbre est composé par un ensemble de nœuds N, une ensemble d’arcs A, et un
nœud particulier appelé racine. Les éléments de A sont des couples (n1,n2)
appartenant à N. n1 est le père de n2 le fils ou l’enfant de n1. A définit une relation
telle que chaque nœud sauf la racine doit avoir un père.
Racine
branche
Nœud Nœud interne
Nœud externe
Arc
Sous arbre
feuilles
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 4
14/04/2019
ARBRE
un arbre est une collection hiérarchique de nœud.
Les nœud comportent une information, est sont liés à autres nœud.
Les règles suivantes doivent cependant être respectées:
Les descendants ne sont pas partagés par différents nœuds, ce qui veut
dire qu’un nœud doit avoir un et un seul père
Un nœud ne peut pas être son propre père
La racine de l’arbre n’a pas de père.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 5
RACINE
La racine représente le nœud de départ de l’arbre,
Elle donne naissance à d’autre nœuds, chacun de ces nœuds engendra à son tour
des nœuds.
Un arbre possède une seule racine, mais chaque sous arbre doit avoir sa propre
racine.
Remarque:
Contrairement aux arbres dans la nature, les arbres en informatiques sont
schématisés la racine en haut, et les feuilles en bas.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 6
14/04/2019
RACINE
Racine A
Arbre A
Racine B
Sous arbre B
Comme l’illustre la figure ci-dessus, l’arbre principal A possède une racine A, le sous
arbre B est identifié par sa propre racine B.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 7
NŒUD
Comme la cellule d’une liste, le nœud est le composant de base dans un arbre.
C’est le nœud qui contient l’élément.
Tous les éléments de l’arbre sont représentés par des nœuds, qu’ils contiennent une
référence à un autre éléments ou non.
Les nœuds peuvent être:
internes: un nœud interne n’a pas la racine et n’est pas une feuille.
externes: un nœud externe est un nœud terminal ou feuille, c’est-à-dire, qu’il ne donne
naissance à aucun autre nœud.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 8
14/04/2019
NŒUD
Le nœud est caractérisé par:
Une étiquette: c’est la valeur associée à l’élément.
Fils ou descendants immédiats: ce sont les nœuds qu’il engendre directement,
Degré ou degré sortant: le nombre de fils immédiats du nœud.
Il existe deux nœuds particuliers:
La racine: parce qu’elle n’a pas de père
La feuille: parce qu’elle n’a pas de fils.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 9
ARC
C’est la relation de filiation qui existe entre un nœud et ses fils.
Si un arc démarre d’un nœud N1pour atteindre un nœud N2 : on dit alors que N1
est le père de N2, et que N2 est le fils de N1.
la sémantique de l’arc dépend de la relation qui existe entre les nœuds de l’arbre.
Exemple:
La relation de filiation peut être une relation d’appartenance, ou de contenance ( cela dépend du sens
dans lequel on considère l’arc)
La planète Terre contient les continents Afrique, Europe, Asie,…
L’Afrique appartient à la planète Terre.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 10
14/04/2019
CHEMIN
C’est l’ensemble des arcs qui mène d’un nœud N1 vers un autre nœud N2.
Remarque:
Dans un arbre il existe un seul chemin qui mène d’un nœud vers un autre.
N1
N2 N3 Chemin de N1 vers N8 (arc N1-N3, N3-N5, N5-N8)
N4 N5 N6 Chemin de N1 vers N4 (arc N1-N2, N2-N4)
N7 N8
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 11
BRANCHE
Une branche est le chemin (succession des arcs) qui mène de la racine vers une
feuille.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 12
14/04/2019
NIVEAU
Soit A un arbre, x un nœud de A.
( ) = distance (nombre d’arcs) qui sépare x de la racine
( ) = 0 si X = Racine(A)
1+ ( ( )) sinon
Exemple
=2
= 1+
= 1+ 1+
= 1+1+ ( ( ))
= 1+1+0
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 13
HAUTEUR
Soit A un arbre, x un nœud de A.
= distance de x à son plus lointain descendant, qui être un nœud
externe (une feuille).
= 0 si x est un nœud externe de A
1+ Max( ) avec e descendant de x sinon
-1 si l’arbre est vide
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 14
14/04/2019
HAUTEUR
1
2 3 4
= 8 est une feuille, donc elle a une hauteur de 0
5 6 7 8 = 1: c’est la distance qui sépare le nœud 7 de son fils le plus lointain, 10 et 11
=2
9 10 11
= 2 : c’est la plus grande distance qui sépare le nœud 2 de l’un de ces descendants,
ici en l’occurrence le noeud 9
= = 3 : la hauteur d’un arbre, c’est la hauteur de sa racine,
ici c’est le chemin le plus long de la racine à une feuille, 9,10,11
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 15
SOUS ARBRE 2 3 4
5 6 7 8
cv
Soit A un arbre, x un nœud de A. 9 10 11
= sous arbre de A qui a pour racine x.
= = ce qui veut dire que la hauteur d’un nœud x
est équivalente à la hauteur du sous arbre qui a pour racine x.
A= ( ) : A est le sous arbre qui a pour racine, la racine de A.
Remarque:
en effet, chaque nœud de l’arbre peut donner naissance à un sous arbre, même si ce
sous arbre ne contient qu’un seul nœud: ex. ou
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 16
14/04/2019
FRÈRE
Le frère d’un nœud N1 est un nœud N2 qui à le même père que N1.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 17
ASCENDANT
On dit qui N1 est un ascendant de N2:
si N1 est le père de N2
Ou si N1 est un ascendant du père de N2.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 18
14/04/2019
DESCENDANT
On dit que N1 est le descendant de N2:
Si N1 est le fils de N2
Ou si N1 est un descendant du fils de N2
Remarque:
si N1 est un descendant de N2 alors forcement N2 est un ascendant e N1.
14/04/2019 EMNA KRAIEM BEN AFIA -------------- L2 INFOS 19
