Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
Arbres binaires de recherche
Judicaël Courant
25 août 2017
1 Rappels
1.1 Arbres binaires
Appelés aussi arbres binaires-unaires.
Un arbre binaire (non-vide) est formé de nœuds.
Soit un arbre est vide soit possède un nœud racine, qui a lui-même un fils-gauche et un fils-droit
qui sont deux arbres.
Les nœuds dont les deux fils sont vides sont appelés nœuds externes (ou feuilles). Les autres sont
appelés nœuds internes.
b c
d f g
Notons qu’un nœud peut posséder 0, 1 ou 2 nœuds fils.
1.2 Arbres étiquetés
Étant donné un ensemble α, on peut étiqueter les nœuds par des éléments de α.
Dans la suite, on ne s’intéressera qu’à des arbres binaires étiquetés.
Judicaël Courant- 25 août 2017 1/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
1.3 Définition formelle
Définition 1 L’ensemble A(α) des arbres binaires étiquetés par α est le plus petit ensemble A(α)
possédant un élément particulier qu’on notera ∅ (représentant l’arbre vide) et tel que si g et d sont
deux éléments de A(α) et n ∈ α, alors (n, g, d) est un arbre. 1
type ’ a arbre_bin =
| Vide
| N of ’ a ∗ ( ’ a arbre_bin ) ∗ ( ’ a arbre_bin ) ; ;
1.4 Hauteur
Définition 2 La hauteur de l’arbre vide est 0 et tout arbre (n, g, d) où g (resp. d) est de hauteur hg
(resp. hd ) est de hauteur 1 + max(hg , hd ) :
l e t rec h a u t e u r a = match a with
| Vide −> 0
| N(_, g , d ) −> 1 + max ( h a u t e u r g ) ( h a u t e u r d ) ; ;
1.5 Profondeur
Définition 3 La profondeur du nœud d’un arbre est le nombre d’arêtes du plus court chemin reliant
ce nœud à la racine.
1.6 Vrai ou faux ?
La hauteur d’un arbre est :
A la profondeur maximum de ses nœuds ;
B le nombre maximum de nœuds se trouvant sur un chemin partant de la racine de l’arbre ;
C les deux ;
D ni l’un, ni l’autre.
1.7 Taille d’un arbre
Définition 4 La taille de l’arbre vide est son nombre de nœuds, soit 0 pour l’arbre vide et 1 + tg + td
pour un arbre (n, g, d) où d et d sont respectivement de tailles tg et td .
l e t rec t a i l l e a = match a with
| Vide −> 0
| N(_, g , d ) −> 1 + ( t a i l l e g ) + ( t a i l l e d ) ; ;
1.8 Relation entre taille et hauteur
Théorème 1 Pour tout arbre de taille n et de hauteur h, on a
h ≤ n ≤ 2h − 1
ou, si l’on préfère :
n ∈ [[h, 2h [[
1. On supposera de plus que l’arbre vide n’est pas un triplet de façon à éviter toute ambiguïté.
Judicaël Courant- 25 août 2017 2/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
1.9 Arbre parfait
Définition 5 Un arbre est parfait (on dit parfois aussi complet) si tous les nœuds internes ont deux
fils et les nœuds externes sont tous à la même profondeur.
Théorème 2 Un arbre binaire est parfait si et seulement si n = 2h − 1 où h est sa hauteur et n son
nombre de nœuds.
1.10 Arbre quasi-complet
Définition 6 Un arbre (quasi-)complet (ou tas) est un arbre de hauteur h où toutes les feuilles sont
à profondeur h − 1 ou h, les feuilles de profondeur h étant bien tassées sur la gauche.
a a
b c b c
d e f g d e f g
h i j k l h i j k l
Exemple d’arbre quasi-complet Exemple d’arbre non quasi-complet
1.11 Relation taille/hauteur
Théorème 3 Pour tout arbre (quasi-)complet de hauteur h et de taille n, on a
2h−1 ≤ n ≤ 2h − 1
où, si l’on préfère :
n ∈ [[2h−1 , 2h [[
1.12 Arbres binaires entiers
Appelés aussi arbres strictement binaires ou arbres hétérogènes.
Ils peuvent être vus comme des arbres binaires non-vides dans lesquels tout nœud a soit deux fils
vides soit deux fils non-vides.
Donc soit un arbre binaire entier est réduit à une feuille soit sa racine possède un fils-gauche et un
fils-droit qui sont deux arbres binaires entiers non-vides.
Judicaël Courant- 25 août 2017 3/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
1.13 Exemples
a
a
b c b c
d e f g
d e
h i
f g
Exemple d’arbre binaire entier.
Exemple d’arbre binaire entier.
1.14 Arbres binaires entiers étiquetés
Étant donné un ensemble α et un ensemble β, on peut étiqueter les nœuds (internes) par des
éléments de α et les feuilles par des éléments de β (d’où le nom hétérogène).
Dans la suite, les arbres strictement binaires que nous considérerons seront étiquetés.
1.15 Définition formelle
Définition 7 L’ensemble A(α, β) des arbres binaires étiquetés par α comme le plus petit ensemble
A(α, β) tel que β ⊂ A(α, β) et tel que si g et d sont deux éléments de A(α, β) et n ∈ α, alors (n, g, d)
est un arbre. 2
type ( ’ a , ’ b ) abin_ent =
| F e u i l l e of ’ b
| NS of ’ a ∗ ( ’ a , ’ b ) abin_ent ∗ ( ’ a , ’ b ) abin_ent
;;
1.16 Hauteur
Définition 8 La hauteur d’un arbre hétérogène est 0 si c’est une feuille et 1 + max(hg , hd ) pour les
arbres (n, g, d) où g et d sont respectivement de hauteur hg et hd .
Attention, les deux arbres suivants n’ont pas la même hauteur !
2. On supposera que β ne contient aucun triplet de façon à éviter toute ambiguïté ; dans le cas contraire, on peut
encore construire un ensemble représentant les arbres strictement binaires, au prix de petites complications.
Judicaël Courant- 25 août 2017 4/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
a b
Arbre binaire-unaire. Arbre binaire entier.
1.17 Profondeur d’un nœud
Comme pour les arbres homogènes :
Définition 9 La profondeur du nœud ou d’une feuille d’un arbre hétérogène est le nombre d’arêtes
du plus court chemin reliant ce nœud ou cette feuille à la racine.
1.18 Vrai ou faux ?
La hauteur d’un arbre hétérogène est :
A la profondeur maximum de ses feuilles ;
B le nombre maximum de nœuds se trouvant sur un chemin partant de la racine de l’arbre ;
C les deux ;
D ni l’un, ni l’autre.
1.19 Taille
La taille est définie comme 0 pour les feuilles et 1 + tg + td pour les arbres (n, g, d) où g et d sont
respectivement de tailles g et d. Autrement dit, c’est le nombre de nœuds internes.
Théorème 4 Un arbre strictement binaire de taille n possède n + 1 feuilles.
Démonstrations :
1. Par induction.
2. Voir l’arbre comme représentant un tournoi (les nœuds représentent les vainqueurs des différents
matchs, les feuilles les compétiteurs). Chaque match permet d’éliminer un compétiteur. À la
fin, seul un compétiteur n’est pas éliminé. Dont s’il y a n matchs, il y a n + 1 compétiteurs.
3. Considérer la fonction qui associe son père à chaque feuille ou nœud (interne) différent de la
racine. Elle réalise une surjection sur l’ensemble des nœud internes. De plus chaque nœud interne
possède exactement 2 antécédents. En notant f le nombre de feuilles, on a donc f +n−1 = 2×n,
d’où f = n + 1.
2 Arbres binaires de recherche
2.1 Contexte
Soit E et F deux ensembles, et c : E → F une fonction appelée (fonction) clé de recherche. On
veut définir une structure de données permettant de représenter un ensemble A d’éléments de E et
écrire une fonction recherche prenant en argument A et une clé k ∈ F et retournant un élément x de
E tel que c(x) = k.
Judicaël Courant- 25 août 2017 5/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
value v i d e : ( ’ e −> ’ f ) −> ( ’ e , ’ f ) t ; ;
value a j o u t e : ’ e −> ( ’ e , ’ f ) t −> ( ’ e , ’ f ) t ; ;
value r e c h e r c h e : ’ f −> ( ’ e , ’ f ) t −> ’ e ; ;
value supprime : ’ f −> ( ’ e , ’ f ) t −> ( ’ e , ’ f ) t ; ;
On peut évidemment réaliser cette structure avec une liste :
type ( ’ e , ’ f ) = {
donnees : ’ e l i s t ; (∗ l e s é l é ments s t o c k é s ∗)
f o n c t i o n _ c l e : ’ e −> ’ f ;
};;
let recherche k a =
l e t c = a . f o n c t i o n _ c l e in
l e t d = a . donnees in
l e t rec r e c h d =
match d with
| [ ] −> r a i s e Not_found
| x : : d ’ −> i f c x = k then x e l s e r e c h d ’
in r e c h d
;;
2.2 Complexité de la recherche séquentielle
On cherche les complexités de la recherche d’un élément x dans une liste ` de longueur n, d’une
part en supposant x ∈ `, d’autre part en supposant x ∈
/ `, dans le cas le pire, le cas le meilleur et en
moyenne (6 possibilités).
A Une de ces complexités est en O(1), les cinq autres sont en O(n).
B Deux de ces complexités sont en O(1), les quatre autres en O(n).
C Trois de ces complexités sont en O(1), les trois autres en O(n).
D Toutes ces complexités sont en O(n).
2.3 Une tentative d’amélioration
Supposons que F est muni d’un ordre total ≤.
On peut alors munir E d’une relation en posant pour tout (x, y) ∈ E 2 :
x y ⇐⇒ c(x) ≤ c(y)
La relation est un préordre sur E (relation réflexive et transitive) et même un préordre total.
2.4 Questions
Peut-on améliorer la complexité des fonctions usuelles de la structure précédentes en ne conservant
que des listes triées pour ?
Peut-on améliorer la complexité de la fonction recherche en utilisant des tableaux triés plutôt
que des listes ?
A Oui et oui.
B Non et oui (respectivement).
C Oui et non (respectivement).
D Non et non.
Judicaël Courant- 25 août 2017 6/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
2.5 Définition
On appelle arbre binaire de recherche un arbre binaire dont les nœuds sont étiquetés par des
éléments de E tels que pour tout nœud n :
— l’étiquette de n majore l’ensemble des étiquettes du fils gauche de n
— et l’étiquette de n minore l’ensemble des étiquettes du fils droit de n.
25
17 42
12 33 56
14
2.6 Vrai ou faux ?
Un arbre est un arbre binaire de recherche si et seulement si la valeur de chaque fils-gauche est
plus petite que celle de son père et celle de chaque fils-droit plus grande que celle de son père.
A Vrai
B Faux
Judicaël Courant- 25 août 2017 7/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
2.7 Un exemple intéressant
25
14 42
12 33 56
17
2.8 Remarque
Un arbre est un abr si un seulement si en projetant les nœuds sur une droite horizontale, on obtient
une liste triée par ordre croissant. Autrement dit :
Théorème 5 Un arbre est un abr si et seulement si la liste obtenue par un parcours infixe de l’arbre
est triée par ordre croissant.
2.9 Fonctions usuelles
type ( ’ e , ’ f ) abr = {
donnees : ’ e arbre_bin ;
f o n c t i o n _ c l e : ’ e −> ’ f ;
}
l e t v i d e c = { donnees = Vide ; f o n c t i o n _ c l e = c } ; ;
On suppose que l’ordre sur l’ensemble désigné par ’f est celui de Caml.
Judicaël Courant- 25 août 2017 8/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
l e t r e c h e r c h e k abr =
l e t c = abr . f o n c t i o n _ c l e in
l e t rec r e c h a =
match a with
| Vide −> r a i s e Not_found
| N( x , g , d ) −>
i f c x = k then x
e l s e i f c x < k then r e c h g
else rech d
in r e c h abr . donnees
;;
l e t a j o u t e y abr =
l e t c = abr . f o n c t i o n _ c l e in
l e t rec a j a =
match a with
| Vide −> N( y , Vide , Vide )
| N( x , g , d ) −> i f c y <= c x then N( x , a j g , d )
e l s e N( x , g , a j d )
in a j abr . donnees
;;
Pour la suppression, on a deux choix à faire sur la spécification :
1. Que faire si la clé qu’on veut enlever n’est pas là ? Échouer ou rendre l’arbre inchangé ? (on
choisit arbitrairement la deuxième possibilité)
2. Que faire si la clé qu’on veut enlever apparaît plusieurs fois : enlever toutes les occurrences ou
une seule ? (on choisit la deuxième possibilité, plus simple)
Une fois ces deux choix faits, la suppression s’écrit assez naturellement... sauf dans le cas où la
valeur à enlever est sur un nœud ayant deux fils.
l e t supprime k abr =
l e t c = abr . f o n c t i o n _ c l e in
l e t rec suppr a =
match a with
| Vide −> Vide (∗ conforme au p r e m i e r c h o i x ∗)
| N( x , g , d ) −>
i f k < c x then N( x , suppr g , d )
e l s e i f k > c x then N( x , g , suppr d )
e l s e i f g = Vide then d (∗ c a s f a c i l e ∗)
e l s e (∗ g <> Vide e t c x = k ∗)
l e t y , g ’ = e n l e v e _ n o e u d _ d r o i t e g in
N( y , g ’ , d )
in suppr abr . donnees
;;
(∗ e n l e v e l e nœud l e p l u s à d r o i t e de l ’ a r b r e ∗)
l e t rec e n l e v e _ n o e u d _ d r o i t e a =
match a with
| Vide −> f a i l w i t h " e n l e v e _ n o e u d _ d r o i t e ␣ : ␣ a r b r e ␣ v i d e "
| N( x , g , Vide ) −> x , g
| N( x , g , d ) −>
Judicaël Courant- 25 août 2017 9/10 Document sous licence Art Libre ([Link]
Lycée La Martinière Monplaisir Année 2016-2017
Option Informatique 2e année Option Informatique 2e année
l e t y , d ’ = e n l e v e _ n o e u d _ d r o i t e d in
y , N( x , g , d ’ )
;;
Complexité de toutes ces fonctions : O(h) où h est la hauteur de l’arbre.
Est-ce mieux que l’utilisation d’une liste ?
Pas significativement si h est de l’ordre de n. Oui si on peut faire en sorte que h soit un O(log n).
Pour ça on peut :
— Essayer de faire en sorte que les arbres soient plus équilibrés, typiquement on les rééquilibre si
nécessaire à chaque fois qu’on ajoute ou retire un élément (AVL, arbres rouge-noir) voire quand
on accède à un élément (splay tree).
— Compter sur la chance...
Compter sur la chance :
Théorème 6 On considère une liste de n valeurs x0 , . . . , xn−1 toutes distinctes. On tire au hasard
de façon uniforme une permutation σ dans S[[0,n[[ . Considérons alors la variable aléatoire H désignant
la hauteur de l’arbre de recherche obtenu en ajoutant successivement xσ(0) , . . . , xσ(n−1) à l’arbre vide.
Alors E(H) = O(log n).
On pourra consulter [Link] 3 pour une démonstration longue et délicate
mais n’utilisant que des outils mathématiques vus en MPSI.
3 Retour sur les dictionnaires
3.1 Rappel (version persistante)
type ( ’ k , ’ v ) d i c t ; ;
value v i d e : ( ’ k , ’ v ) d i c t ; ;
value a j o u t e : ’ k −> ’ v −> ( ’ k , ’ v ) d i c t −> ( ’ k , ’ v ) d i c t ; ;
value r e c h e r c h e : ’ k −> ( ’ k , ’ v ) d i c t −> ’ v ; ;
value supprime : ’ k −> ( ’ k , ’ v ) d i c t −> ( ’ k , ’ v ) d i c t ; ;
3.2 Réalisation par un abr
type ( ’ k , ’ v ) d i c t = ( ’ k ∗ ’ v , ’ k ) abr ; ;
l e t v i d e = abr__vide ( fun ( k , v ) −> k ) ; ;
l e t a j o u t e k v d = abr__ajoute ( k , v ) d ; ;
l e t r e c h e r c h e k d = snd ( abr__recherche k d ) ; ;
l e t supprime k d = abr__supprime k d ; ;
3.3 Complexité
3. Redirigeant sur [Link]
Judicaël Courant- 25 août 2017 10/10 Document sous licence Art Libre ([Link]