A Rappels algorithmiques
417
Contrairement à l’insertion, aucun choix pour q(A) ne permet de retrouver une
procédure classique d’insertion (section A.2.3). En effet le cas des nœuds doubles
impose, dans la procédure classique de suppression à la racine, de mettre à la racine
la plus grande clé du sous-arbre gauche, ce que ne peut garantir la suppression
randomisée.
Enfin, notons qu’afin de garantir la loi induite par les permutations uniformes sur
les ABR, et les bonnes propriétés algorithmiques qui en découlent, on choisit
p(A) = q(A) =
A g
|A| − 1
,
où
A g
et |A| désignent respectivement le nombre de nœuds du sous-arbre gauche
A g et l’arbre A en entier.
A.3 Arbres-B
Nous présentons ici uniquement la structure de données et les algorithmes de
recherche et d’insertion pour les arbres-B prudents, 1 et renvoyons par exemple
au livre de Cormen et al. [50] pour plus de détails et pour des indications sur la
suppression. Pour les algorithmes sur les arbres-B optimistes, nous renvoyons au
livre de Kruse et Ryba [162].
Nous définissons d’abord le type de données puis donnons l’algorithme de
recherche, relativement simple. Nous avons décomposé l’algorithme d’insertion en
plusieurs fonctions, pour des raisons de clarté de la présentation.
A.3.1 Le type de données Arbre-B (prudent)
Rappelons que, à la différence d’un arbre binaire de recherche, toutes les clés d’un
arbre-B sont distinctes. Soit m ≥ 2 un entier. Nous traitons ici, parmi les différentes
variantes d’arbre-B, de celle où les nœuds ont entre m − 1 et 2m − 1 clés, et qui a
une approche préventive lors de l’insertion d’une clé.
Struct ArbreB
Booléen feuille
entier nombreClés
élément clés[1 . . 2m − 1]
ArbreB fils[1 . . 2m]
1 Les arbres-B de cette section sont ce que nous avons appelé arbres-B de recherche au chapitre 1.
417
Contrairement à l’insertion, aucun choix pour q(A) ne permet de retrouver une
procédure classique d’insertion (section A.2.3). En effet le cas des nœuds doubles
impose, dans la procédure classique de suppression à la racine, de mettre à la racine
la plus grande clé du sous-arbre gauche, ce que ne peut garantir la suppression
randomisée.
Enfin, notons qu’afin de garantir la loi induite par les permutations uniformes sur
les ABR, et les bonnes propriétés algorithmiques qui en découlent, on choisit
p(A) = q(A) =
A g
|A| − 1
,
où
A g
et |A| désignent respectivement le nombre de nœuds du sous-arbre gauche
A g et l’arbre A en entier.
A.3 Arbres-B
Nous présentons ici uniquement la structure de données et les algorithmes de
recherche et d’insertion pour les arbres-B prudents, 1 et renvoyons par exemple
au livre de Cormen et al. [50] pour plus de détails et pour des indications sur la
suppression. Pour les algorithmes sur les arbres-B optimistes, nous renvoyons au
livre de Kruse et Ryba [162].
Nous définissons d’abord le type de données puis donnons l’algorithme de
recherche, relativement simple. Nous avons décomposé l’algorithme d’insertion en
plusieurs fonctions, pour des raisons de clarté de la présentation.
A.3.1 Le type de données Arbre-B (prudent)
Rappelons que, à la différence d’un arbre binaire de recherche, toutes les clés d’un
arbre-B sont distinctes. Soit m ≥ 2 un entier. Nous traitons ici, parmi les différentes
variantes d’arbre-B, de celle où les nœuds ont entre m − 1 et 2m − 1 clés, et qui a
une approche préventive lors de l’insertion d’une clé.
Struct ArbreB
Booléen feuille
entier nombreClés
élément clés[1 . . 2m − 1]
ArbreB fils[1 . . 2m]
1 Les arbres-B de cette section sont ce que nous avons appelé arbres-B de recherche au chapitre 1.