3.2 Recherche de clés
67
ces arbres, sont étudiées en chapitre 6 ; la section 6.6 en particulier détaille les
conséquences algorithmiques des résultats théoriques.
Remarque 3.1 Nous laissons à la lectrice ou au lecteur le soin d’adapter ce que
nous venons de dire sur les coûts des diverses opérations, au cas où la mesure de
coût retenue n’est plus le nombre de comparaisons de clés, mais le nombre de liens
suivis pour passer d’un nœud à un autre ou à l’arbre vide, i.e., le nombre d’accès
mémoire.
3.2.2 Autres arbres de recherche
Nous nous intéressons maintenant, après les arbres binaires de recherche, à des
structures arborescentes qui les généralisent, dans le cas où les opérations permises
sont toujours les comparaisons de clés pour une recherche par valeur.
Arbres 2–3 et arbres-B de recherche
Certaines variantes visent à borner le coût de recherche d’une clé dans le pire des
cas, en assurant que toutes les feuilles se trouvent au même niveau (on évite ainsi
les arbres « filiformes ») ; ce sont par exemple les arbres 2–3 déjà rencontrés en
section 1.2.6, et plus généralement les arbres-B que nous définissons ci-dessous.
Il s’agit d’une structure fondamentale en informatique, utilisée depuis des
décennies pour stocker efficacement de grandes quantités de données. Il en existe
un certain nombre de variantes, et nous avons choisi de présenter deux d’entre elles,
correspondant à deux algorithmes de construction, respectivement appelés (dans ce
livre) algorithme prudent et algorithme optimiste. La variante optimiste permet de
voir les arbres 2–3 comme une classe particulière d’arbre-B. Au chapitre 9, nous
analyserons la loi des différents types de feuilles dans les arbres 2–3 et les arbres-B.
Définition 3.2 Soit m ≥ 1 un entier. Un arbre-B de recherche prudent de
paramètre m est un arbre de recherche (cf. définition 1.34) planaire non vide dans
lequel la racine a entre 2 et 2m enfants, chaque autre nœud interne a entre m et 2m
enfants, et toutes les feuilles sont au même niveau.
Un arbre-B de recherche optimiste de paramètre m est un arbre de recherche
planaire non vide dans lequel la racine a entre 2 et 2m + 1 enfants, chaque autre
nœud interne a entre m + 1 et 2m + 1 enfants, et toutes les feuilles sont au même
niveau.
Le terme « de recherche » est couramment omis.
Remarque 3.3 Un arbre-B prudent pour m = 2 est un arbre 2–3–4 (cf. par exemple
Sedgewick [231] pour une définition de ces arbres). Un arbre-B optimiste pour m =
1 est un arbre 2–3.
67
ces arbres, sont étudiées en chapitre 6 ; la section 6.6 en particulier détaille les
conséquences algorithmiques des résultats théoriques.
Remarque 3.1 Nous laissons à la lectrice ou au lecteur le soin d’adapter ce que
nous venons de dire sur les coûts des diverses opérations, au cas où la mesure de
coût retenue n’est plus le nombre de comparaisons de clés, mais le nombre de liens
suivis pour passer d’un nœud à un autre ou à l’arbre vide, i.e., le nombre d’accès
mémoire.
3.2.2 Autres arbres de recherche
Nous nous intéressons maintenant, après les arbres binaires de recherche, à des
structures arborescentes qui les généralisent, dans le cas où les opérations permises
sont toujours les comparaisons de clés pour une recherche par valeur.
Arbres 2–3 et arbres-B de recherche
Certaines variantes visent à borner le coût de recherche d’une clé dans le pire des
cas, en assurant que toutes les feuilles se trouvent au même niveau (on évite ainsi
les arbres « filiformes ») ; ce sont par exemple les arbres 2–3 déjà rencontrés en
section 1.2.6, et plus généralement les arbres-B que nous définissons ci-dessous.
Il s’agit d’une structure fondamentale en informatique, utilisée depuis des
décennies pour stocker efficacement de grandes quantités de données. Il en existe
un certain nombre de variantes, et nous avons choisi de présenter deux d’entre elles,
correspondant à deux algorithmes de construction, respectivement appelés (dans ce
livre) algorithme prudent et algorithme optimiste. La variante optimiste permet de
voir les arbres 2–3 comme une classe particulière d’arbre-B. Au chapitre 9, nous
analyserons la loi des différents types de feuilles dans les arbres 2–3 et les arbres-B.
Définition 3.2 Soit m ≥ 1 un entier. Un arbre-B de recherche prudent de
paramètre m est un arbre de recherche (cf. définition 1.34) planaire non vide dans
lequel la racine a entre 2 et 2m enfants, chaque autre nœud interne a entre m et 2m
enfants, et toutes les feuilles sont au même niveau.
Un arbre-B de recherche optimiste de paramètre m est un arbre de recherche
planaire non vide dans lequel la racine a entre 2 et 2m + 1 enfants, chaque autre
nœud interne a entre m + 1 et 2m + 1 enfants, et toutes les feuilles sont au même
niveau.
Le terme « de recherche » est couramment omis.
Remarque 3.3 Un arbre-B prudent pour m = 2 est un arbre 2–3–4 (cf. par exemple
Sedgewick [231] pour une définition de ces arbres). Un arbre-B optimiste pour m =
1 est un arbre 2–3.