Index
509
Oxford English Dictionnary, 76
paramètre, 61
additif, 39–40, 133–134, 141–143, 175,
217, 219, 355–359, 368
d’arbre, 36–40
parcours
d’arbre binaire, 400–403
dans un trie, 430–431
en largeur, 196, 402–403
en ordre hiérarchique, 402
en profondeur, 196, 400–402
postfixe, 402
préfixe, 401
suffixe, 402
symétrique, 23, 26, 401
partition, 273
péage, 40, 133, 141, 219, 355–356, 358, 370
peigne, 8
permutation, 54, 84, 341
évitant un motif, 99
pivot
pour tri rapide, 78–80, 273
plongement, 249, 384, 390
polynôme
Gamma, 278, 466
polynôme de niveau, 226, 269, 351, 364–369
préfixe, 5, 30, 112
Pringsheim
théorème, 136, 139, 453
probabilité
de partage, 351–356, 360, 366, 368, 370
processus
d’arbre, 52
de Yule, 242, 249
profil, 38, 217, 224–232
profondeur, 6, 9, 37, 125
d’insertion, 39, 65–67, 220–221, 227, 269
d’insertion dans un arbre quadrant de
recherche, 351, 360–364, 368–372
d’une feuille dans un arbre quadrant de
recherche, 364
propriété de branchement, 44, 45, 185, 187,
193, 206, 207
protocole en arbre, 107–108
QuickSelect, 439
quicksort
loi de, 239
racine, 4, 6, 9, 184
randomisation, 49, 260, 271
randomisé (abr), 260–267, 271–272, 415–416
rang, 47, 51, 148, 274, 340
recherche
avec succès dans un arbre binaire de
recherche, 64, 66
avec succès dans un arbre quadrant de
recherche, 369
dans un arbre binaire de recherche, 64–67,
269–270, 406
dans un trie, 430
de clé, 61, 63–78
par rang, 63, 90–91, 439–440
par valeur, 63
sans succès dans un arbre binaire de
recherche, 64, 66
sans succès dans un arbre quadrant de
recherche, 369
relèvement analytique, 318, 321
réordonnement, 14, 15, 25, 46, 51–53
résidu, 319, 321–324, 453, 454
rotation (dans un arbre binaire), 271, 404
sentinelle, 79, 272, 438–439
série
de Dirichlet, 313, 316, 317, 321, 322, 331,
463
de Laurent, 323, 452, 454, 461
de Poisson, 305, 306, 309, 317, 318, 320
singularité dominante, 136, 139, 453, 457, 459
singularité de type « racine carrée », 140, 169
source probabilisée, 55
sous-arbre
spécial, 148
droit, 10
gauche, 10
statistique d’ordre, 15
Stirling
formule, 381, 465
nombre, 226, 465
streaming, 108
suffixe, 5
suppression
dans un arbre binaire de recherche, 64–67,
261–267, 270–271, 406, 408–409
dans un tas, 92, 443–444
dans un trie, 431–432
par fusion dans un abr, 406, 414–415
randomisée, 262
symbole, 17
table
de routage, 112
509
Oxford English Dictionnary, 76
paramètre, 61
additif, 39–40, 133–134, 141–143, 175,
217, 219, 355–359, 368
d’arbre, 36–40
parcours
d’arbre binaire, 400–403
dans un trie, 430–431
en largeur, 196, 402–403
en ordre hiérarchique, 402
en profondeur, 196, 400–402
postfixe, 402
préfixe, 401
suffixe, 402
symétrique, 23, 26, 401
partition, 273
péage, 40, 133, 141, 219, 355–356, 358, 370
peigne, 8
permutation, 54, 84, 341
évitant un motif, 99
pivot
pour tri rapide, 78–80, 273
plongement, 249, 384, 390
polynôme
Gamma, 278, 466
polynôme de niveau, 226, 269, 351, 364–369
préfixe, 5, 30, 112
Pringsheim
théorème, 136, 139, 453
probabilité
de partage, 351–356, 360, 366, 368, 370
processus
d’arbre, 52
de Yule, 242, 249
profil, 38, 217, 224–232
profondeur, 6, 9, 37, 125
d’insertion, 39, 65–67, 220–221, 227, 269
d’insertion dans un arbre quadrant de
recherche, 351, 360–364, 368–372
d’une feuille dans un arbre quadrant de
recherche, 364
propriété de branchement, 44, 45, 185, 187,
193, 206, 207
protocole en arbre, 107–108
QuickSelect, 439
quicksort
loi de, 239
racine, 4, 6, 9, 184
randomisation, 49, 260, 271
randomisé (abr), 260–267, 271–272, 415–416
rang, 47, 51, 148, 274, 340
recherche
avec succès dans un arbre binaire de
recherche, 64, 66
avec succès dans un arbre quadrant de
recherche, 369
dans un arbre binaire de recherche, 64–67,
269–270, 406
dans un trie, 430
de clé, 61, 63–78
par rang, 63, 90–91, 439–440
par valeur, 63
sans succès dans un arbre binaire de
recherche, 64, 66
sans succès dans un arbre quadrant de
recherche, 369
relèvement analytique, 318, 321
réordonnement, 14, 15, 25, 46, 51–53
résidu, 319, 321–324, 453, 454
rotation (dans un arbre binaire), 271, 404
sentinelle, 79, 272, 438–439
série
de Dirichlet, 313, 316, 317, 321, 322, 331,
463
de Laurent, 323, 452, 454, 461
de Poisson, 305, 306, 309, 317, 318, 320
singularité dominante, 136, 139, 453, 457, 459
singularité de type « racine carrée », 140, 169
source probabilisée, 55
sous-arbre
spécial, 148
droit, 10
gauche, 10
statistique d’ordre, 15
Stirling
formule, 381, 465
nombre, 226, 465
streaming, 108
suffixe, 5
suppression
dans un arbre binaire de recherche, 64–67,
261–267, 270–271, 406, 408–409
dans un tas, 92, 443–444
dans un trie, 431–432
par fusion dans un abr, 406, 414–415
randomisée, 262
symbole, 17
table
de routage, 112