28
1 Botanique
Fig. 1.27 Un arbre 2-3 de
hauteur 3 et de taille 32 : il a
12 nœuds internes, dont 8
terminaux, et 20 feuilles
nœud à avoir plus d’une clé et l’arité des nœuds internes est variable. 12 Les arbres
non marqués correspondant aux arbres 2-3 sont définis ci-après.
Définition 1.36 Un arbre 2-3 est un arbre planaire dans lequel chaque nœud
interne a soit deux, soit trois enfants, et qui a toutes ses feuilles au même niveau
(figure 1.27).
Les arbres 2-3 s’étendent au cas où les nœuds internes peuvent avoir une
arité supérieure à 3 ; ce sont les arbres-B, dont il existe de multiples variantes.
Nous détaillerons deux types d’arbres-B avec leur intérêt algorithmique dans la
section 3.2.2 et en ferons l’analyse au chapitre 9. Disons pour l’instant qu’un arbreB de paramètre m, pour m ≥ 2, est un arbre dans lequel la racine a entre 2 et m
enfants et les autres nœuds ont entre m/2 et m enfants.
Définition 1.37 Un arbre 2-3 de recherche est un arbre de recherche non vide (cf.
définition 1.34) dont toutes les clés sont distinctes et dont la forme est un arbre 2-3
(cf. définition 1.36).
En conséquence, chaque nœud interne contient soit une, soit deux clés, et a donc
deux ou trois fils ; de plus toutes les feuilles sont au même niveau (figure 1.28).
Il est encore possible de définir un marquage canonique de ces arbres.
Remarquons par ailleurs que, s’il existait des clés répétées dans un arbre 2-3
de recherche (ou dans les arbres-B que nous verrons dans les chapitres 3 et 9),
certains sous-arbres seraient toujours vides, et il ne serait pas possible d’équilibrer
ces arbres : la condition que les clés soient distinctes ne peut donc pas être affaiblie.
Le qualificatif « de recherche » est la plupart du temps omis, et le terme d’« arbre
2-3 » est généralement utilisé dans le sens de la définition 1.37.
Comme dans la version dynamique des arbres binaires de recherche, l’insertion
dans un arbre 2-3 se fait « aux feuilles », dans le sens où les feuilles de l’arbre
complété représentent les possibilités d’insertion dans l’arbre. Comme un nœud
interne peut contenir une ou deux clés, et que toutes les feuilles doivent être au même
niveau, l’algorithme d’insertion d’une clé x diffère de celui des arbres binaires ou
m-aires de recherche, et son principe est le suivant :
– Si la recherche de la place où insérer conduit à un nœud interne terminal
qui contient une seule clé (et a donc deux enfants, qui sont deux possibilités
12 Il existe d’autres types d’arbres de recherche utilisés en informatique, par exemple les arbres
k-d ; nous définissons ici uniquement les classes d’arbres que nous étudions dans ce livre.
1 Botanique
Fig. 1.27 Un arbre 2-3 de
hauteur 3 et de taille 32 : il a
12 nœuds internes, dont 8
terminaux, et 20 feuilles
nœud à avoir plus d’une clé et l’arité des nœuds internes est variable. 12 Les arbres
non marqués correspondant aux arbres 2-3 sont définis ci-après.
Définition 1.36 Un arbre 2-3 est un arbre planaire dans lequel chaque nœud
interne a soit deux, soit trois enfants, et qui a toutes ses feuilles au même niveau
(figure 1.27).
Les arbres 2-3 s’étendent au cas où les nœuds internes peuvent avoir une
arité supérieure à 3 ; ce sont les arbres-B, dont il existe de multiples variantes.
Nous détaillerons deux types d’arbres-B avec leur intérêt algorithmique dans la
section 3.2.2 et en ferons l’analyse au chapitre 9. Disons pour l’instant qu’un arbreB de paramètre m, pour m ≥ 2, est un arbre dans lequel la racine a entre 2 et m
enfants et les autres nœuds ont entre m/2 et m enfants.
Définition 1.37 Un arbre 2-3 de recherche est un arbre de recherche non vide (cf.
définition 1.34) dont toutes les clés sont distinctes et dont la forme est un arbre 2-3
(cf. définition 1.36).
En conséquence, chaque nœud interne contient soit une, soit deux clés, et a donc
deux ou trois fils ; de plus toutes les feuilles sont au même niveau (figure 1.28).
Il est encore possible de définir un marquage canonique de ces arbres.
Remarquons par ailleurs que, s’il existait des clés répétées dans un arbre 2-3
de recherche (ou dans les arbres-B que nous verrons dans les chapitres 3 et 9),
certains sous-arbres seraient toujours vides, et il ne serait pas possible d’équilibrer
ces arbres : la condition que les clés soient distinctes ne peut donc pas être affaiblie.
Le qualificatif « de recherche » est la plupart du temps omis, et le terme d’« arbre
2-3 » est généralement utilisé dans le sens de la définition 1.37.
Comme dans la version dynamique des arbres binaires de recherche, l’insertion
dans un arbre 2-3 se fait « aux feuilles », dans le sens où les feuilles de l’arbre
complété représentent les possibilités d’insertion dans l’arbre. Comme un nœud
interne peut contenir une ou deux clés, et que toutes les feuilles doivent être au même
niveau, l’algorithme d’insertion d’une clé x diffère de celui des arbres binaires ou
m-aires de recherche, et son principe est le suivant :
– Si la recherche de la place où insérer conduit à un nœud interne terminal
qui contient une seule clé (et a donc deux enfants, qui sont deux possibilités
12 Il existe d’autres types d’arbres de recherche utilisés en informatique, par exemple les arbres
k-d ; nous définissons ici uniquement les classes d’arbres que nous étudions dans ce livre.