Index
algorithme
d’ajout d’une clé à un tas, 442–443
d’insertion à la racine dans un arbre binaire
de recherche, 409–411
d’insertion à la racine dans un arbre
randomisé, 415
d’insertion aux feuilles dans un arbre
binaire de recherche, 407
d’insertion dans un arbre–B prudent,
419–424
d’insertion dans un trie, 429
de construction d’un tas, 441–442
de Floyd, 48, 155, 177, 441–442
de fusion de deux arbres binaires de
recherche, 411–415
de recherche dans un arbre binaire de
recherche, 406
de recherche dans un arbre–B, 419
de recherche dans un trie, 430–431
de recherche par rang, 439–440
de suppression dans un arbre binaire de
recherche, 408–409
de suppression dans un trie, 431–432
de suppression du minimum d’un tas,
443–444
de suppression dans un arbre randomisé,
415–416
de tri par tas, 445
de tri radix, 433–437
de tri rapide, 437–439
de Williams, 48, 176, 442–443
des buveurs de bière, 106–107
Aloha, 107
alphabet, 17
ancêtre, 6, 184, 205, 206
arbre
–B, 28, 67–71, 164–167
–B de recherche, 67–70
–B optimiste, 67–70, 165
–B prudent, 67–70, 164, 271, 417–424
–B prudent (implémentation), 417
–B prudent (insertion), 419–424
–B prudent (recherche), 419
2-3, 28, 67, 158–164, 178–180
2-3 de recherche, 28–30
2-3-4, 67, 271
AVL, 179, 271, 404
biaisé, 184, 189, 190, 200, 208, 209, 218,
256–260
bicolore, 271
binaire, 8–13, 121–204
binaire (implémentation), 400
binaire complet, 8–11, 38, 43, 338
binaire croissant, 253
binaire de recherche, 22–26, 49–54, 64–67,
79–81, 104–105, 217–279
bourgeonnant, 43, 52, 218, 255, 257, 261,
263
complété, 23, 218
croissant, 18–22, 146, 149
d’expression, 61–63
de branchement, 44–46
de Catalan, 11, 44, 121, 135, 196, 198
de Cayley, 17–18, 22, 168–169, 198
de décision, 82–88
de Galton-Watson, 41, 44–46, 183, 196,
208
de génération, 99–101
de Pólya, 13–14, 169, 172–174, 181
de Pólya binaire, 169–172, 180–181
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
505
algorithme
d’ajout d’une clé à un tas, 442–443
d’insertion à la racine dans un arbre binaire
de recherche, 409–411
d’insertion à la racine dans un arbre
randomisé, 415
d’insertion aux feuilles dans un arbre
binaire de recherche, 407
d’insertion dans un arbre–B prudent,
419–424
d’insertion dans un trie, 429
de construction d’un tas, 441–442
de Floyd, 48, 155, 177, 441–442
de fusion de deux arbres binaires de
recherche, 411–415
de recherche dans un arbre binaire de
recherche, 406
de recherche dans un arbre–B, 419
de recherche dans un trie, 430–431
de recherche par rang, 439–440
de suppression dans un arbre binaire de
recherche, 408–409
de suppression dans un trie, 431–432
de suppression du minimum d’un tas,
443–444
de suppression dans un arbre randomisé,
415–416
de tri par tas, 445
de tri radix, 433–437
de tri rapide, 437–439
de Williams, 48, 176, 442–443
des buveurs de bière, 106–107
Aloha, 107
alphabet, 17
ancêtre, 6, 184, 205, 206
arbre
–B, 28, 67–71, 164–167
–B de recherche, 67–70
–B optimiste, 67–70, 165
–B prudent, 67–70, 164, 271, 417–424
–B prudent (implémentation), 417
–B prudent (insertion), 419–424
–B prudent (recherche), 419
2-3, 28, 67, 158–164, 178–180
2-3 de recherche, 28–30
2-3-4, 67, 271
AVL, 179, 271, 404
biaisé, 184, 189, 190, 200, 208, 209, 218,
256–260
bicolore, 271
binaire, 8–13, 121–204
binaire (implémentation), 400
binaire complet, 8–11, 38, 43, 338
binaire croissant, 253
binaire de recherche, 22–26, 49–54, 64–67,
79–81, 104–105, 217–279
bourgeonnant, 43, 52, 218, 255, 257, 261,
263
complété, 23, 218
croissant, 18–22, 146, 149
d’expression, 61–63
de branchement, 44–46
de Catalan, 11, 44, 121, 135, 196, 198
de Cayley, 17–18, 22, 168–169, 198
de décision, 82–88
de Galton-Watson, 41, 44–46, 183, 196,
208
de génération, 99–101
de Pólya, 13–14, 169, 172–174, 181
de Pólya binaire, 169–172, 180–181
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
505