TD d’algorithmique avanc´ee
TD 8 : D´enombrement sur les arbres binaires
Jean-Michel Dischler et Fr´ed´eric Vivien
D´enombrement sur les arbres binaires
Dans cet exercice on notera n le nombre de nœuds d’un arbre binaire, f son nombre de feuilles et h sa
hauteur. Tous les arbres consid´er´es seront suppos´es non vides.
1. Quelle est la hauteur maximale d’un arbre `a n nœuds ?
2. Quel est le nombre maximal de feuilles d’un arbre de hauteur h ?
3. Quel est le nombre maximal de nœuds d’un arbre de hauteur h ?
4. Quelle est la hauteur minimale d’un arbre de n nœuds ?
5. Montrez que le nombre de branches vides — nombre de fils gauches et de fils droits vides — d’un arbre
a n nœuds est ´egal a n + 1.
Indication : on distinguera les nœuds ayant z´ero, un et deux fils.
6. Montrez que le nombre de feuilles est inf´erieur ou ´egal `a n+1
Publicité
2
seulement si chaque nœud de l’arbre est soit une feuille, soit a deux fils.
Indication : se servir du raisonnement utilis´e `a la question pr´ec´edente.
(f ≤ n+1
2 ) et qu’il y a ´egalit´e si et
7. Montrez que le nombre de feuilles d’un arbre est ´egal au nombre de nœuds de degr´e deux, plus un.
Complexit´e du tri
Les algorithmes de tris par comparaison peuvent ˆetre consid´er´es de fa¸con abstraite en termes d’arbres de
d´ecision. Un arbre de d´ecision repr´esente les comparaisons (`a l’exclusion de toute autre op´eration) effectu´ees
par un algorithme de tri lorsqu’il traite une entr´ee de taille donn´ee. La figure 1 pr´esente l’arbre de d´ecision
correspondant `a l’algorithme de tri par insertion s’ex´ecutant sur une liste de trois ´el´ements.
Soient (cid:104)a1, a2, ..., an(cid:105) les n valeurs `a trier. Dans un arbre de d´ecision chaque nœud interne est ´etiquet´e
par une expression ai ≤ aj, pour certaines valeurs de i et de j, 1 ≤ i, j ≤ n. L’ex´ecution de l’algorithme
de tri suit un chemin qui part de la racine de l’arbre de d´ecision pour aboutir a une feuille. A chaque
Publicité
nœud interne, on effectue une comparaison ai ≤ aj et les comparaisons suivantes auront lieu dans le sous-
arbre gauche si ai ≤ aj et dans le sous-arbre droit sinon. Chaque feuille est d´esign´ee par une permutation
(cid:104)π(1), π(2), ..., π(n)(cid:105) : si l’algorithme de tri aboutit en la feuille (cid:104)π(1), π(2), ..., π(n)(cid:105), les valeurs `a trier
v´erifient : aπ(1) ≤ aπ(2) ≤ ... ≤ aπ(n).
a2 ≤ a3
≤
(cid:104)1, 2, 3(cid:105)
≤
a1 ≤ a2
≤
>
>
≤
a1 ≤ a3
Publicité
>
a1 ≤ a3
(cid:104)2, 1, 3(cid:105)
a2 ≤ a3
(cid:104)1, 3, 2(cid:105)
>
(cid:104)3, 1, 2(cid:105)
≤
(cid:104)2, 3, 1(cid:105)
>
(cid:104)3, 2, 1(cid:105)
Fig. 1 – Arbre de d´ecision correspondant au traitement de trois ´el´ements au moyen du tri par insertion.
1. Quel est le nombre de feuilles d’un tel arbre de d´ecisions ?
2. En d´eduire une borne inf´erieure sur la hauteur de l’arbre de d´ecision.
Publicité
3. En d´eduire une borne inf´erieure sur la complexit´e du tri de n ´el´ements.
Indication : d’apr`es la formule de Stirling, on a n! >
n
.
n
e (cid:1)
(cid:0)
Arbres binaires de recherche
1. Montrez que le temps de cr´eation d’un arbre binaire de recherche `a partir d’une liste quelconque de n
´el´ements est Ω(n log n).
2. ´Ecrivez un algorithme qui teste si un arbre binaire est un arbre binaire de recherche.