Algorithmes et structures des données
Les structures arborescentes
Un arbre est un ensemble d’éléments appelés nœuds
ou sommets organisés de manière hiérarchique à partir d’un nœud
distingué appelé racine. On repère les nœuds de l’arbre en leur donnant
des noms différents.
Arbres binaires
Un
arbre binaire est soit vide, noté Ø, soit de la forme < r, B1,
B2 > où r est la racine et où B1 et B2 sont
des arbres binaires.
On définit intuitivement les notions de sous-arbre, de
sous-arbre gauche, de fils gauche, de lien gauche et réciproquement à
droite. On définit encore les notions de père, de frère, d’ascendant
et de descendant. Les nœuds d’un arbre binaire ont au plus deux fils. Un
nœud interne ou double a 2 fils. Un point simple à gauche a
seulement un fils à gauche, et réciproquement à droite. Un nœud externe ou
feuille n’a pas de fils. De façon généralisé, on qualifie de nœud
interne, tout nœud qui n’est pas externe. On appelle les branches de
l’arbre tout chemin (suite consécutive de nœuds) allant de la racine à
une feuille. Il y a autant de branches que de feuilles. Le bord gauche
est le chemin issu de la racine en suivant les liens gauches, et réciproquement
à droite.
Les caractéristiques d’un arbre sont :
-
la taille de l’arbre
est le nombre total de nœuds.
-
la hauteur
ou niveau d’un nœud x est le nombre de lien sur l’unique chemin allant
de la racine à x, notée h(x).
-
la hauteur ou profondeur
de l’arbre A, 
.
.
-
la longueur de
cheminement de l’arbre A, 
avec LCE la longueur de cheminement
extérieure 
et LCI la
longueur de cheminement intérieure 
.
avec LCE la longueur de cheminement
extérieure et LCI la
longueur de cheminement intérieure .
-
la profondeur moyenne
externe de A est 
.
.
On donne la signature du type abstrait arbre binaire :
sorte
arbre
utilise
nœud
opérations
Ø :
à arbre
<
– , – , – > : nœud x arbre x arbre à
arbre
racine :
arbre à nœud
gauche :
arbre à arbre
droit :
arbre à arbre.
Proposition : Soit un arbre binaire de taille n,
de profondeur p et possédant f
feuilles. Si on examine les cas extrêmes, on obtient que 
; par ailleurs 
d’où 
.
; par ailleurs d’où .
Représentation des arbres en machines : On
utilise la structure récursive des arbres.
1)
Dans cette première
représentation, le chaînage est symbolisé par des pointeurs.
type arbre = adresse de nœud ;
type nœud = structure
val : élément ;
g, d : arbre ;
fin ;
L’arbre est déterminé par l’adresse de la racine. On
gère la mémoire dynamiquement pour les opérations de suppression /
insertion.
2)
Dans la représentation
contiguë, on simule les chaînages par des indices dans un tableau.
type arbre = tableau de 1 à N
de
structure
val : élément ;
g, d : entier ;
fin ;
On utilise l’indice 0 pour indiquer qu’il n’y a pas de
fils. L’arbre est déterminé par une variable entière contenant l’indice de la
racine. On va gérer les cases libres pour des insertions / suppressions. On
chaîne les cases libres comme une pile, en utilisant le chaînage g et on
utilise une variable entière libre pour indiquer l’indice du
« sommet de pile ».
Arbres binaires complets
Un arbre binaire est complet si tous les nœuds qui ne
sont pas des feuilles ont 2 fils.
Propositions : Un arbre binaire complet ayant n
nœuds internes possède en tout n+1 feuilles. La démonstration se fait
simplement par récurrence. Par ailleurs, on montre qu’il existe une bijection
entre l’ensemble des arbres binaires de tailles n, Bn, et
l’ensemble des arbres binaires complets de taille 2n+1, BC2n+1.
Principe : on ajoute des feuilles de sorte que tout nœud de l’arbre ait
deux fils. De plus on établit que 
.
.Arbres binaires parfaits, ordre hiérarchique
On dit qu’un arbre binaire est parfait si toutes ses
feuilles sont situées sur les deux derniers niveau, l’avant dernier étant
complet, et les feuilles du dernier sont le plus à gauche possible.
Attention ! un arbre binaire parfait n’est pas forcément complet, mais il
a toujours au plus un nœud simple (le père de la feuille la plus à droite).
On peut représenter un arbre binaire parfait de taille n de
manière compacte par un tableau à n cases. Ceci se fait en numérotant les nœuds
de 1 à n en partant de la racine, niveau par niveau de gauche à droite (ordre
hièrarchique). On a les relation générales suivantes :
-
le père du nœud d’indice i
est à l’indice i / 2 (division entière) ;
-
le fils gauche d’un nœud i
est, s’il existe, à l’indice 2i ;
-
le fils droit d’un nœud i
est, s’il existe, à l’indice 2i+1 ;
-
les feuilles sont aux
indices > n / 2.
Parcours en profondeur d’un arbre binaire
On considère l’opération de parcours qui consiste à
examiner systématiquement dans un certain ordre tous les nœuds de l’arbres pour
effectuer un traitement de données. Le
parcours en profondeur à gauche consiste à partir de la racine et à tourner
autour de l’arbre en allant toujours le plus à gauche possible.
Procédure Parcours(A : arbre) ;
début
Si A
= Ø
Alors T0
Sinon
début
T1 ;
Parcours(g(A)) ;
T2 ;
Parcours(d(A)) ;
T3 ;
fin ;
fin ;
Chaque nœud est visité trois fois. à chaque visite correspond un traitement Ti et un
ordre de parcours. T1 s’effectue avant la descente gauche et décrit l’ordre
préfixe ou pré-ordre. T2 s’effectue après la remontée
gauche et avant la remontée droite, l’ordre associé est l’ordre infixe
ou symétrique. Le traitement T3 est réalisé après la remontée
droite ; les nœuds sont parcourus dans l’ordre suffixe ou post-fixe.
On ajoute un traitement particulier T0 pour les nœuds vides.
Arbres généraux
Un arbre général, ou simplement arbre, est une
structure arborescente où le nombre de fils n’est plus limité à 2.
Un arbre A = < r, A1, A2, …, An
> est la donnée d’une racine r et d’une suite éventuellement vide de sous-arbres
disjoints. Cette suite est une forêt. Un arbre est obtenu en
rajoutant un nœud racine à la forêt.
On donne la signature des arbres généraux :
sorte
arbre, forêt
utilise
nœud
opérations
cons :
nœud x forêt à arbre
racine :
arbre à nœud
sous-arbre :
arbre à forêt
Ø :
à forêt
ième :
forêt x entier à arbre
longueur :
forêt à entier
insérer :
forêt x entier x arbre à forêt
Il n’y a plus de notion de fils gauche ou de fils droit. On
parle du ième fils d’un nœud.
Dans un parcours à gauche, chaque nœud est rencontré une
fois de plus que son nombre de fils.
Procédure Parcours(A :
arbre) ;
début
Si
sous-arbre(A) = Ø
Alors
T0
Sinon
début
i
ß 1 ;
Répéter
Ti ;
Parcours(ième(sous-arbre(A),
i)) ;
i++ ;
Jusqu’à
ce que i > longueur(sous-arbre(A)) ;
Ti ;
fin ;
fin ;
L’ordre préfixe sur les nœuds est obtenu en ne
faisant qu’intervenir que T1. L’ordre suffixe est obtenu en
ne faisant intervenir que Ti à l’extérieur de la boucle. Il n’y a
pas d’ordre infixe.
Représentation des arbres : On représente un
arbre général par des listes chaînées dynamiques.
type arbre = adresse de
nœud ;
type nœud = structure
val : élément ;
premier_fils, frère : arbre ;
fin ;
Propositions : Le nombre d’arbres généraux de
taille n+1 est 
. Par ailleurs, il existe des bijections entre les forêts de
taille n, les arbres généraux de taille n+1, et les arbres binaires de taille
n, avec des propriétés intéressantes sur les parcours.
. Par ailleurs, il existe des bijections entre les forêts de
taille n, les arbres généraux de taille n+1, et les arbres binaires de taille
n, avec des propriétés intéressantes sur les parcours.
0 commentaires:
Enregistrer un commentaire