Les arbres 2-3
Laurent Chéno∗
Luminy, - mai
http://lcheno.free.fr/arbres23/
Résumé
Nous décrivons ici les arbres 2-3, structure (décrite pour la première fois en ) d’arbres de
recherche qui maintiennent un équilibrage suffisant pour garantir par exemple un tri en O(n lg n).
Nous présentons le code Caml correspondant aux fonctions de base sur une telle structure (recherche,
insertion, suppression, et donc tri). Nous donnons également les éléments théoriques qui permettraient
une généralisation aux arbres a-b sous la condition b (cid:1) 2a − 1 (cid:1) 3. Enfin, nous tentons une approche
combinatoire de la structure présentée.
∗lycée Louis-le-Grand, Paris ; mailto:[email protected]
Table des matières
1 Les arbres 2-3
1.1 Arbres de recherche
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Arbres bi- ou ter- naires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Équilibrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Un petit point historique
1.5 Recherche d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6
Insertion d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 Suppression d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Généralisation : les arbres a-b
2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Insertion et suppression d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
3 Implantation en Caml des arbres 2-3
3.1 Le typage des arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 La recherche d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 L’insertion d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 La suppression d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Application : un algorithme de tri
3.5.1 Quelques applications directes des algorithmes précédents . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.2 Le tri proprement dit
4 Quelques éléments pour une combinatoire des arbres 2-3
4.1 Fonctions génératrices associées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Pour une analyse plus fine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Table des figures
1
2
3
4
5
6
7
8
9
10
11
12
les deux types de nœuds utilisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
un arbre 2-3 avant insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
après insertion de la clé 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
après insertion de la clé 21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
après recomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
après insertion de la clé 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
après insertion de la clé 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
un cas simple de résolution d’un fils unique . . . . . . . . . . . . . . . . . . . . . . . . . .
un autre cas simple de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
une résolution d’un fils unique un peu plus difficile . . . . . . . . . . . . . . . . . . . . . .
une résolution qui répercute un nouveau fils unique . . . . . . . . . . . . . . . . . . . . . .
répartition k3/k pour p = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Table des programmes
1
2
3
4
5
6
le typage des arbres 2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
la recherche d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
l’insertion d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
la suppression d’une clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
quelques applications immédiates
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
le tri d’une liste grâce aux arbres 2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3
3
4
4
4
4
7
9
9
9
10
10
10
10
12
12
12
12
15
15
16
4
5
5
5
6
6
7
7
8
8
8
17
10
10
11
13
14
14
2
1 Les arbres 2-3
1.1 Arbres de recherche
Considérons un ensemble de clés d’un certain type α. Nous supposerons qu’il existe une application que
nous nommerons valuation v : a (cid:1)→ v(a) qui associe un entier naturel à chaque clé, permettant ainsi de
munir leur ensemble d’un ordre1 ≺ défini par a (cid:4) b ⇐⇒ v(a) (cid:2) v(b).
Nous cherchons à définir une structure sur l’ensemble de ces clés qui permettent les opérations de base
suivantes :
(i) l’insertion d’une nouvelle clé dans la structure ;
(ii) la recherche d’une clé particulière ;
(iii) la suppression d’une clé présente dans la structure ;
(iv) l’extraction de la clé de valuation minimale (resp. minimale).
Une méthode habituelle consiste à utiliser une structure d’arbre binaire : les feuilles de l’arbre contiendront
les clés de la structure, les nœuds une fonction de sélection qui pourra décider, la valuation d’une clé
étant donnée, s’il convient de descendre a gauche ou a droite dans l’arbre.
Les types Caml génériques correspondant seraient donc les suivants :
type descente = Gauche | Droite ;;
type ’a valuation == ’a -> int ;;
type ’a arbre_de_recherche =
| Feuille of ’a
| Nœud of (int -> descente)
- (’a arbre_de_recherche)
- (’a arbre_de_recherche) ;;
La généralisation à un arbre n-aire se ferait aisément.
En pratique, on choisit pour la fonction de sélection de fixer (dans le cas d’un arbre binaire) une valeur
v0 telle que si la valuation d’une clé lui est inférieure, on s’orientera vers la gauche, et vers la droite
dans le cas contraire. Pour le cas d’un nœud d’arité n, il conviendra de choisir n − 1 valeurs entières qui
permettront de sélectionner la branche descendante à parcourir.
L’un des intérêts de ce choix est de résoudre facilement le problème de l’extraction de la clé de valeur
minimale (ou maximale) : il suffira de descendre systématiquement a gauche (ou a droite) pour atteindre
à coup sûr la clé recherchée.
Bien entendu, tout le problème est dans la nécessité d’éviter qu’on se retrouve avec des arbres dont
la profondeur soit linéaire en leur taille. On sait bien que la profondeur d’un arbre est comprise entre
un logarithme de sa taille et cette taille : le probleme de l’équilibrage consiste a garantir qu’elle reste
logarithmique.
1.2 Arbres bi- ou ter- naires
Soit donc un ensemble (infini) de clés A pour lequel existe une valuation v : A −→ N.
On leur associe l’ensemble B2,3 des arbres dont les feuilles portent des valeurs de l’ensemble A ; qui
vérifient la propriété tout nœud est d’arité 2 ou 3 ; et dont les nœuds d’arité 2 portent un entier quand
les nœuds d’arité 3 en portent deux. De tels arbres seront appelés arbres 2-3 généraux.
A un nœud d’arité 2 qui porte l’entier r est associée la fonction de sélection qui fait descendre a gauche
(resp. à droite) toute clé x telle que v(x) (cid:2) r (resp. v(x) > r).
À un nœud d’arité 3 qui porte le couple d’entiers (r, s) avec r < s est associée la fonction de sélection qui
fait descendre a gauche (resp. au milieu) (resp. a droite) toute clé x telle que v(x) (cid:2) r (resp. r < v(x) (cid:2) s)
(resp. s < v(x)).
Nous utiliserons la représentation graphique de la figure 1 page suivante pour les deux types de nœuds.
Une telle structure conserve l’information dans ses feuilles, et les clés sont triées en ordre croissant dans
le parcours préfixe, infixe ou suffixe, de ses feuilles.
1tout bon ordre suffirait, valuation ou pas
3
r
r
s
v(x) < r
r < v(x)
v(x) < r
r<v(x)
v(x)<s
s < v(x)
Fig. 1: les deux types de nœuds utilisés
La clé de valeur minimale (resp. maximale) se trouvera alors naturellement en premier (resp. en dernier)
dans tout parcours préfixe, infixe ou suffixe des feuilles.
1.3
Équilibrage
Soit n le nombre de feuilles d’un arbre dont tous les nœuds sont d’arité 2 ou 3, et p sa profondeur,
c’est-a-dire le nombre maximal d’arêtes qu’il faut traverser dans un parcours depuis la racine jusqu’a une
des feuilles.
On dispose alors d’un résultat (classiquement démontré dans le cas d’arbres strictement binaires) qui
énonce que (cid:10)log3 n(cid:11) (cid:2) p (cid:2) n − 1.
Si l’on garantit que toutes les feuilles étaient de même profondeur p, on dispose d’un résultat plus fort
qu’on peut énoncer ainsi :
Théorème 1
Si un arbre 2-3 général comporte n feuilles qui sont toutes à profondeur p, alors on dispose de la relation :
2p (cid:2) n (cid:2) 3p,
ou encore
lg3 n (cid:2) p (cid:2) lg2 n.
1.4 Un petit point historique
Dans la suite, nous ne considérerons que des arbres 2-3 généraux dont toutes les feuilles sont à la même
profondeur, que nous appellerons simplement arbres 2-3.
Ces arbres, qu’on appelle parfois aussi des arbres B+, ont été imaginés — ainsi que les algorithmes que
nous allons décrire ci-dessous — pour la première fois en par D. Comer dans [1].
1.5 Recherche d’une clé
La recherche d’une clé dans un arbre 2-3 ne pose pas de problème particulier : l’information incluse dans
chaque nœud permet de choisir la branche de descente.
D’apres le théoreme précédent, il est clair que la recherche d’une feuille d’un arbre 2-3 qui en possède n
a un coût logarithmique c(recherche) = Ω(lg n). Notons qu’il s’agit d’une évaluation qui vaut dans tous
les cas, et pas seulement dans le meilleur.
1.6 Insertion d’une clé
L’insertion d’une clé se fait classiquement comme toute insertion aux feuilles dans un arbre de recherche.
Considérons l’exemple de l’arbre 2-3 de la figure 2 page suivante.
L’insertion d’une nouvelle clé de valeur 3 se fait en remplaçant simplement un nœud binaire par un nœud
ternaire, et on obtient l’arbre de la figure 3 page suivante.
4
7
4
10 16
2
6
9
15
18
Fig. 2: un arbre 2-3 avant insertion
7
2 4
10 16
2
3
6
9
15
18
Fig. 3: après insertion de la clé 3
La difficulté a résoudre se présente évidemment quand on se retrouve avec un nœud a 4 feuilles : la clé
insérée s’est installée comme fille d’un nœud qui avait déjà trois feuilles.
C’est ce qui se passe (voir la figure 4) lorsque par exemple on insère la clé 21 dans l’arbre de la figure 2.
7
4
10 16 ?
2
6
9
15
18
21
Fig. 4: après insertion de la clé 21
Il s’agit alors de recomposer l’arbre, en éclatant le nouveau nœud à 4 feuilles formé en deux nœuds
binaires.
Ainsi, l’arbre précédent de la figure 4, qui n’est pas 2-3, devient-il celui de la figure 5 page suivante.
5
7 16
Publicité
4
10
18
2
6
9
15
18
21
Fig. 5: après recomposition
Bien entendu, il se peut que l’arbre pere du nœud 4 temporaire soit déja ternaire, et il faudra dans ce cas
recommencer en éclatant le pere en deux nœuds binaires : on peut ainsi être amené a remonter tout en
haut de l’arbre, ce qui est le seul cas où la profondeur totale augmente au cours de l’insertion d’une clé.
Par exemple, on vérifiera facilement que les insertions successives des clés 11 et 13 dans l’arbre de la
figure 5 conduisent aux arbres des figures 6 et 7 page suivante.
7 16
4
10 11
18
2
6
9
11
15
18
21
Fig. 6: après insertion de la clé 11
6
11
7
16
4
10
13
18
2
6
9
11
13
15
18
21
Fig. 7: après insertion de la clé 13
Finalement, on a un algorithme qui descend tout en bas de l’arbre avant (dans le pire des cas) de remonter
tout en haut, et le coût de l’insertion est encore c(insertion) = Ω(lg n).
1.7 Suppression d’une clé
De la même façon, pour supprimer une clé, on commence par descendre dans l’arbre jusqu’à trouver la
feuille concernée.
Si son père est un nœud 3, il n’y a pas de difficulté : on remplace ce nœud ternaire par un nœud binaire,
et la feuille est supprimée.
Si, en revanche, on trouve un nœud binaire, la suppression conduit à un nœud unaire qui ne respecte pas
les contraintes de définition d’un arbre 2-3.
Il s’agit donc de gérer le cas ou la suppression dans une branche de l’arbre conduit a un nœud unaire.
On considere alors le pere.
Ou bien il s’agit d’un nœud ternaire : par exemple, un nœud de sous-arbres g, m et d, et tel que g
soit unaire. On distinguera les manipulations nécessaires selon que m est binaire ou ternaire. La figure 8
explicite le premier cas, la figure 9 page suivante le deuxième.
r s
t
devient
r t
D
s
D
A
B
C
A
B
C
Fig. 8: un cas simple de résolution d’un fils unique
7
r s
t u
devient
r
E
t s
u
E
A
B
C
D
A
B
C
D
Fig. 9: un autre cas simple de résolution
Dans le cas ou le pere est un nœud binaire, par exemple de sous-arbres g unaire et d, la figure 10 montre
comment terminer si d est ternaire. Si en revanche d est aussi binaire, on procède comme le montre la
figure 11, et on doit remonter encore plus haut dans l’arbre.
r
s
s t
devient
r
t
A
B
C
D
A
B
C
D
Fig. 10: une résolution d’un fils unique un peu plus difficile
r
s
devient
r s
qu il faut encore remonter
A
B
C
A
B
C
Fig. 11: une résolution qui répercute un nouveau fils unique
Finalement, on a un algorithme qui descend tout en bas de l’arbre avant (dans le pire des cas) de remonter
tout en haut, et le coût de l’insertion est encore c(suppression) = Ω(lg n).
8
2 Généralisation : les arbres a-b
2.1 Définitions
Soit a (cid:1) 2 et b (cid:1) 2a − 1. Un arbre a-b est un arbre tel que
— toutes les feuilles sont à la même profondeur ;
— la racine est de degré compris entre 2 et b (au sens large) ;
— tous les autres nœuds sont de degré compris entre a et b (au sens large).
Chaque nœud de degré k (avec donc a (cid:2) k (cid:2) b et 2 (cid:2) k (cid:2) b pour la racine) contient un aiguillage formé
d’un (k − 1)-uplet d’entiers, qui permet de choisir la branche où descendre dans la recherche d’une clé de
valuation donnée.
Bien entendu, on dispose, comme à la section 1.3 page 4, du
Théorème 2
Si un arbre a-b comporte n feuilles qui sont toutes à profondeur p, alors on dispose de la relation :
2ap−1 (cid:2) n (cid:2) bp,
ou encore
lgb n (cid:2) p (cid:2) 1 + lga(n/2).
2.2 Insertion et suppression d’une clé
Les algorithmes d’insertion et de suppression sont tout a fait analogues a ceux qu’on a décrit plus haut
dans le cas où a = 2 et b = 3.
Pour l’insertion, il conviendra d’éclater un nœud de degré b + 1 en deux nœuds de degrés respectifs
(cid:12)(b + 1)/2(cid:13) et (cid:10)(b + 1)/2(cid:11). On constate que la condition b (cid:1) 2a − 1 entraˆıne (cid:10)(b + 1)/2(cid:11) (cid:1) (cid:12)(b + 1)/2(cid:13) (cid:1) a,
et il est alors facile de généraliser l’algorithme d’insertion déjà écrit.
De la même façon, on réécrira l’algorithme de suppression, en remontant au père d’un nœud qui n’aurait
plus que a − 1 fils, ce que nous laissons faire au lecteur de ces lignes. . .
9
3 Implantation en Caml des arbres 2-3
3.1 Le typage des arbres
Le typage correspond naturellement à la définition qu’on a donnée des arbres 2-3 : pour faciliter la
lecture des structures, il nous a paru plus agréable d’écrire un Nœud3 de branches g, m et d et de sélecteur
(r,s) sous la forme Nœud3(g,r,m,s,d), de sorte que chaque entier se positionne entre les branches qu’il
discrimine. Nous avons choisi des étiquettes entières pour cet article, et la valuation est donc simplement
la fonction identité.
Programme 1 le typage des arbres 2-3
type type_des_clés == int ;;
( par exemple )
let valuation x = x ;;
type arbre23 =
| Feuille of type_des_clés
| Nœud2 of arbre23 int arbre23
| Nœud3 of arbre23 int arbre23 int arbre23 ;;
3.2 La recherche d’une clé
La recherche d’une clé est une simple adaptation du programme classique de recherche dans un arbre
binaire de recherche et n’a pas besoin de davantage de commentaires.
Programme 2 la recherche d’une clé
let recherche v a x =
let vx = v x
in
let rec cherche = function
| Feuille y -> x = y
| Nœud2(g,r,d) -> cherche (if vx <= r then g else d)
| Nœud3(g,r,m,s,d) -> cherche (if vx <= r then g else if vx <= s then m else d)
in
cherche a ;;
3.3 L’insertion d’une clé
L’insertion d’une clé, qui fait l’objet du programme 3 page suivante, est beaucoup plus intéressante.
La clef du programme est dans l’utilisation d’une exception : la description de l’algorithme que nous
avons proposé a la sous-section 1.6 page 4 prévoyait, dans le cas ou l’insertion se faisait à un niveau
ou se trouvaient déja 3 clés, d’éclater l’arbre obtenu, et de remonter dans l’arbre, où pouvaient encore
se produire des éclatements supplémentaires. La difficulté est donc de remonter dans un arbre dont la
structure ne prévoit a priori que le moyen d’y descendre. . . C’est la qu’intervient d’une maniere qui me
semble très élégante l’utilisation d’une exception.
Notons que l’éclatement peut se propager jusqu’à la racine de l’arbre (rappelons au passage que c’est
d’ailleurs le seul cas ou l’arbre voit sa profondeur augmenter d’une unité), et c’est la qu’intervient la
structure try ... with ... de la ligne .
10
Programme 3 l’insertion d’une clé
exception Éclaté of arbre23 int arbre23 ;;
let insertion23 v a x =
let vx = v x
in
let rec insère a = match a with
| Feuille y when x = y -> a
| Feuille y when vx < (v y)
-> raise (Éclaté (Feuille x, vx, Feuille y))
| Feuille y ( when vx > (v y) )
-> raise (Éclaté (Feuille y,v y,Feuille x))
| Nœud2(g,r,d) when vx <= r
-> (try Nœud2(insère g,r,d)
with Éclaté(g’,r’,d’) -> Nœud3(g’,r’,d’,r,d))
| Nœud2(g,r,d) ( when vx > r )
-> (try Nœud2(g,r,insère d)
with Éclaté(g’,r’,d’) -> Nœud3(g,r,g’,r’,d’))
| Nœud3(g,r,m,s,d) when vx <= r
-> (try Nœud3(insère g,r,m,s,d)
with Éclaté(g’,r’,d’) -> raise (Éclaté(Nœud2(g’,r’,d’),r,Nœud2(m,s,d))))
| Nœud3(g,r,m,s,d) when vx <= s ( and vx > r )
-> (try Nœud3(g,r,insère m,s,d)
with Éclaté(g’,r’,d’) -> raise (Éclaté(Nœud2(g,r,g’),r’,Nœud2(d’,s,d))))
| Nœud3(g,r,m,s,d) ( when vx > s )
-> (try Nœud3(g,r,m,s,insère d)
with Éclaté(g’,s’,d’) -> raise (Éclaté(Nœud2(g,r,m),s,Nœud2(g’,s’,d’))))
in
match a with
( les cas particuliers du départ )
| Feuille y
->
if x = y then a
else if vx < (v y) then Nœud2( Feuille x,vx, Feuille y)
else Nœud2( Feuille y,v y, Feuille x)
try insère a with Éclaté(g,r,d) -> Nœud2(g,r,d) ;;
| _ ->
Publicité
11
3.4 La suppression d’une clé
On écrit l’algorithme de suppression d’une façon similaire : pour remonter dans la structure, on définit
une exception, qui s’appelle cette fois FilsUnique, et qui est déclenchée quand la suppression normale
d’une clé produit un nœud unaire, qu’il est alors nécessaire de remonter.
On obtient le programme 4 page suivante.
On notera l’utilisation de cas de filtrage du genre Feuille _ -> raise Unexpected qui n’ont d’autre
fonction que satisfaire le parseur de Caml, et éviter des messages d’avertissement de filtrages non exhaus-
tifs. C’est toujours de bonne politique que d’éviter ce genre de messages, et cela garantit une program-
mation plus sûre.
3.5 Application : un algorithme de tri
3.5.1 Quelques applications directes des algorithmes précédents
On écrit très facilement la recherche de la clé de valuation minimale (resp. maximale) d’un arbre 2-3 : il
suffit de descendre systematiquement a droite (resp. à gauche) dans la structure.
De même, à l’aide de la fonction d’insertion, peut-on écrire une fonction qui transforme une liste en
arbre 2-3.
Ces fonctions font l’objet du programme 5 page 14.
3.5.2 Le tri proprement dit
Le tri n’est alors qu’une suite d’extractions des maximas successifs de l’arbre 2-3 construit à partir de la
liste argument, ce que réalise facilement le programme 6 page 14.
12
Programme 4 la suppression d’une clé
exception Unexpected ;; ( bug du programme )
exception FilsUnique of arbre23 ;;
let suppression23 v a x =
let vx = v x
in
let rec supprime a
= match a with
| Feuille y when x = y -> raise Unexpected
| Feuille _ -> a
| Nœud2(Feuille y,_,d) when vx = (v y) -> raise (FilsUnique d)
| Nœud2(g,_,Feuille y) when vx = (v y) -> raise (FilsUnique g)
| Nœud3(Feuille y,_,m,s,d) when vx = (v y) -> Nœud2(m,s,d)
| Nœud3(g,_,Feuille y,s,d) when vx = (v y) -> Nœud2(g,s,d)
| Nœud3(g,s,m,_,Feuille y) when vx = (v y) -> Nœud2(g,s,m)
| Nœud2(g,r,d) when vx <= r
->
( try
Nœud2(supprime g,r,d)
with FilsUnique g’
-> match d with
| Nœud3(gd,rd,md,sd,dd) -> Nœud2(Nœud2(g’,r,gd),rd,Nœud2(md,sd,dd))
| Nœud2(gd,rd,dd) -> raise (FilsUnique (Nœud3(g’,r,gd,rd,dd)))
| Feuille _ -> raise Unexpected ( pour que le filtrage soit exhaustif )
| Nœud2(g,r,d) ( when vx > r )
->
( try
Nœud2(g,r,supprime d)
with FilsUnique d’
-> match g with
| Nœud3(gg,rg,mg,sg,dg) -> Nœud2(Nœud2(gg,rg,mg),sg,Nœud2(dg,r,d’))
| Nœud2(gg,rg,dg) -> raise (FilsUnique (Nœud3(gg,rg,dg,r,d’)))
| Feuille _ -> raise Unexpected ( pour que le filtrage soit exhaustif )
| Nœud3(g,r,m,s,d) when vx <= r
->
( try
Nœud3(supprime g,r,m,s,d)
with FilsUnique g’
-> match m with
| Nœud3(gm,rm,mm,sm,dm) -> Nœud3(Nœud2(g’,r,gm),rm,Nœud2(mm,sm,dm),s,d)
| Nœud2(gm,rm,dm) -> Nœud2(Nœud3(g’,r,gm,rm,dm),s,d)
| Feuille _ -> raise Unexpected ( pour que le filtrage soit exhaustif )
| Nœud3(g,r,m,s,d) when vx <= s
->
( try
Nœud3(g,r,supprime m,s,d)
with FilsUnique m’
-> match g with
| Nœud3(gg,rg,mg,sg,dg) -> Nœud3(Nœud2(gg,rg,mg),sg,Nœud2(dg,r,m’),s,d)
| Nœud2(gg,rg,dg) -> Nœud2(Nœud3(gg,rg,dg,r,m’),s,d)
| Feuille _ -> raise Unexpected ( pour que le filtrage soit exhaustif )
| Nœud3(g,r,m,s,d) ( when vx > s )
->
( try
Nœud3(g,r,m,s,supprime d)
with FilsUnique d’
-> match m with
| Nœud3(gm,rm,mm,sm,dm) -> Nœud3(g,r,Nœud2(gm,rm,mm),sm,Nœud2(dm,s,d’))
| Nœud2(gm,rm,dm) -> Nœud2(g,r,Nœud3(gm,rm,dm,s,d’))
| Feuille _ -> raise Unexpected ( pour que le filtrage soit exhaustif )
in
match a with
| Feuille y when vx = (v y) -> failwith "je ne veux pas d’arbre 2-3 vide"
| Feuille _ -> a
| _ -> try supprime a with FilsUnique u -> u ;;
)
)
)
)
)
13
Programme 5 quelques applications immédiates
let rec min23 = function
| Feuille x -> x
| Nœud2(g,_,_) -> min23 g
| Nœud3(g,_,_,_,_) -> min23 g
and max23 = function
| Feuille x -> x
| Nœud2(_,_,d) -> max23 d
| Nœud3(_,_,_,_,d) -> max23 d ;;
let rec arbre23_of_list v = function
| [] -> failwith "un arbre 2-3 ne peut être vide"
| [ t ] -> Feuille t
| t :: q -> insertion23 v (arbre23_of_list v q) t ;;
Programme 6 le tri d’une liste grâce aux arbres 2-3
let tri23 v l =
let a = arbre23_of_list v l
in
let rec recompose tampon = function
| Feuille x -> x :: tampon
| a -> let x = max23 a in recompose (x :: tampon) (suppression23 v a x)
in
recompose [] a ;;
14
4 Quelques éléments pour une combinatoire des arbres 2-3
4.1 Fonctions génératrices associées
Nous noterons, pour une profondeur p ∈ N et n ∈ N, Bp,n le nombre d’arbres 2-3 de profondeur p qui
si n = 1 ;
sinon.
1,
possèdent n feuilles. Par exemple : B0,n =
0,
Les fonctions génératrices associées sont les séries formelles, éléments de N[[z]], définies par :
(cid:2)
Bp(z) =
+∞(cid:3)
n=0
Bp,nzn.
On a donc en particulier B0(z) = z.
Soit maintenant p (cid:1) 1. La racine d’un arbre 2-3 de taille n et de profondeur p possède deux ou trois fils
qui sont chacun des arbres 2-3 de profondeurs p − 1 et dont la somme des tailles vaut n.
On peut donc écrire :
∀p (cid:1) 1, ∀n, Bp,n =
(cid:3)
(cid:3)
Bp−1,n1Bp−1,n2 +
Bp−1,n1Bp−1,n2Bp−1,n3.
n1+n2=n
n1+n2+n3=n
La traduction en termes de fonctions génératrices est directe, et on obtient :
(cid:2)
Bp(z) =
z,
Bp−1(z)2 + Bp−1(z)3,
si p = 0 ;
si p (cid:1) 1.
Dans [3][page 292], Flajolet et Sedgewick proposent la récurrence fonctionnelle suivante :
(cid:2)
Bp(z) =
z,
Bp−1(z2 + z3),
Publicité
si p = 0 ;
si p (cid:1) 1.
Le point de vue utilisé est totalement différent : cette fois, on passe d’une profondeur p−1 à une profondeur
p en remplaçant chaque feuille par, au choix, un arbre de profondeur 1 qui est soit binaire soit ternaire,
ce qui correspond à la substitution z ← z2 + z3.
Remarquons qu’une démonstration directe de l’équivalence des deux récurrences fonctionnelles écrites
n’aurait vraiment rien d’évident2.
On obtient les valeurs suivantes, pour 0 (cid:2) n (cid:2) 20 :
p
n
B0,n
B1,n
B2,n
B3,n
B4,n
p Bp,n
(cid:4)
5
6
7
2 ou 3
9
8
3
10
11
12
13
14
15
3 ou 4
16
17
18
19
20
2
4
0
1
1
1
2
1
3
1
1
2
2
3
1
1
1
1
2
2
3
3
1
4
1
4
5
8
8
14
23
32
43
63
14
23
32
43
63
96
1
97
141
8
149
192
32
224
240
92
332
267
222
489
En sommant à profondeur fixée, on obtient :
(cid:4)
n Bp,n = Bp(1) d’où le tableau de valeurs suivant :
(cid:4)
p
n Bp,n = Bp(1)
0
1
1
2
2
12
3
1872
4
6563711232
5
282779810171805015122254036992
2mais m’intéresserait quand même beaucoup !
15
Si l’on s’intéresse au nombre moyen de feuilles d’un arbre 2-3 de profondeur p, il suffit d’évaluer la quantité
¯n = B(cid:3)
p(1)/Bp(1), et Maple nous aide à trouver les valeurs suivantes :
2
6,667
5
175,353
3
19,487
4
58,451
1
2,5
p
¯n
0
1
6
526,060
Il n’est pas beaucoup plus difficile d’évaluer la variance de ce nombre de feuilles, puisque la moyenne du
carré de n s’écrit (B(cid:3)
p (1))/Bp(1), et là encore Maple nous fournit les résultats demandés :
p(1) + B(cid:3)(cid:3)
p
V (n)
V (n)
(cid:5)
0
0
0
1
0,25
0,5
2
2,056
1,434
3
9,164
3,027
4
27,691
5,262
5
83,073
9,114
6
249,218
15,787
4.2 Pour une analyse plus fine
Pour raffiner notre analyse de la combinatoire des arbres 2-3, nous pouvons nous intéresser au nombre k
de nœuds (binaires ou ternaires) d’un arbre 2-3 de profondeur p et de taille n, que nous noterons B(k)
p,n.
Pour un arbre binaire, on sait que le nombre de feuilles est égal au nombre de nœuds plus un.
Dans le cas de nos arbres 2-3, nous disposons de l’encadrement analogue : k + 1 (cid:2) n (cid:2) 2k + 1. En outre,
k et p vérifient la relation : 2p − 1 (cid:2) k (cid:2) 3p−1
ce qui donne encore : 2p (cid:2) n (cid:2) 3p comme on pouvait s’y
attendre.
Pour montrer que l’information décrite par le triplet (n, p, k) est plus riche que prévue, montrons le
2
Théorème 3
Soient k2 (resp. k3) le nombre de nœuds binaires (resp. ternaires) d’un arbre 2-3 possédant k nœuds et n
feuilles. Alors : k2 = 2k − n + 1 et k3 = n − k − 1.
Observons tout d’abord que l’on dispose bien sûr de k2 + k3 = k.
Une deuxième équation s’obtient facilement, en considérant que tout nœud/feuille sauf la racine a un
père et qu’on a donc : 2k2 + 3k3 = k + n − 1.
Il suffit alors de résoudre le système de nos deux équations.
(cid:3)
(cid:3)
Introduisons la fonction génératrice à deux variables Bp(z, u) =
B(k)
p,nznuk.
n
k
Bien sûr, on aura Bp(z) = Bp(z, 1) et B0(z, u) = z.
Essayons d’établir des récurrences sur ces entiers B(k)
p,n.
Partant de la racine, on construit un arbre de profondeur p (cid:1) 1 depuis une racine binaire ou ternaire, ce
qui fournit :
∀p (cid:1) 1, ∀k (cid:1) 1, B(k)
p,n =
(cid:3)
n1+n2=n
k1+k2=k−1
B(k1)
p−1,n1
B(k2)
p−1,n2
+
(cid:3)
n1+n2+n3=n
k1+k2+k3=k−1
B(k1)
p−1,n1
B(k2)
p−1,n2
B(k3)
p−1,n3
.
Traduisant ceci en termes de fonctions génératrices, on obtient :
(cid:2)
Bp(z, u) =
z,
u(Bp−1(z, u)2 + Bp−1(z, u)3),
si p = 0 ;
si p (cid:1) 1.
Transformant les n feuilles d’un arbre de profondeur p − 1 contenant k nœuds en arbres de profondeur
1, on passe à un arbre de profondeur p, possédant k + n nœuds et entre 2n et 3n feuilles. Chaque feuille
donne donc naissance soit a un nœud et deux feuilles, soit a un nœud et trois feuilles, ce qui se traduit
par la substitution z ← u(z2 + z3), et on obtient une nouvelle récurrence fonctionnelle :
(cid:2)
Bp(z, u) =
z,
Bp−1(u(z2 + z3), u),
si p = 0 ;
si p (cid:1) 1.
16
C’est cette deuxième récurrence que nous avons utilisée pour écrire en Caml le calcul de la fonction
génératrice. On trouvera le listing correspondant dans le dossier complet lié à cet article, mais nous ne le
reproduisons pas ici.
La figure 12 (qui est une copie d’écran, bien entendu) présente la répartition des nœuds binaires/ternaires
pour les arbres 2-3 de profondeur p = 4 : on lit en abscisses le rapport k3/k ∈ [0, 1] (graduation tous les
dixièmes), et en ordonnées les fréquences relatives (normalisées par la fréquence maximale). On aurait
aimé présenter des statistiques pour des profondeurs plus importantes, mais Caml déclenche trop vite
l’exception Out of memory. . .
Fig. 12: répartition k3/k pour p = 4
17
Références
[1] D. Comer. The ubiquitous b-tree. Computing Surveys, 11 :121–137, 1979.
[2] Danièle Beauquier, Jean Berstel et Philippe Chrétienne. Éléments d’algorithmique. Masson, Paris,
1992.
[3] Philippe Flajolet and Robert Sedgewick. An Introduction to the Analysis of Algorithms. Addison-
Wesley, Reading, Massachussets, 1996.
[4] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics : A Foundation
for Computer Science. Addison-Wesley, Reading, Massachussets, 2nd edition, 1994.
[5] Derick Wood. Data structures, algorithms, and performance. Addison-Wesley, Reading, Massachus-
sets, 1993.
18