Index
507
des opérations dans un arbre binaire de
recherche randomisé, 271–272
des opérations dans un arbre quadrant de
recherche, 369
du tri par tas, 92
du tri rapide, 80
descendant, 6
différentiation (complexité), 143–146, 175
distribution
de type double exponentielle, 329, 332
diviser pour régner, 52–54, 220, 222, 226, 233,
234, 242, 244, 267, 337, 341, 351,
356
drapeau hollandais, 89
Dyck
chemin, 202, 208
échantillonnage adaptatif, 108–110
élection de leader, 106–107
enraciné, 4
épine dorsale, 192, 256
Ethernet, 107
Euler
constante, 221, 275
excursion, 197
brownienne, 202, 204
expression
bien parenthésée, 176
mathématique, 135–137, 139
famille simple, 16–17, 135–146, 175
feuille, 6, 9
file de priorité, 21, 91
fonction
analytique, 136
Beta, 465, 472, 491
caractéristique, 468
Gamma, 460, 465, 472, 491
génératrice, 122, 128, 133, 219–223
génératrice bivariée, 129, 221
génératrice cumulée, 141
génératrice de probabilité, 129
génératrice des moments, 361, 469
génératrice exponentielle, 169
implicite (théorème), 139
méromorphe, 452, 461
forêt, 7
forme d’arbre, 3, 14, 15, 26, 51, 217, 261, 338
formule
d’équerre, 18, 48, 126, 146, 149, 151
de Lagrange, 138–139, 168, 457
de Nörlund-Rice, 318, 320
de Stirling, 125, 153, 169
forward, 45, 185, 187, 207
Fourier
transformée de, 468
fusion (de deux abr), 262, 264, 272, 406,
411–416
Galton-Watson
arbre, 41, 44, 208, 256, 258
processus, 184, 209, 248
Gamma
fonction, 460, 465, 472, 491
loi, 472
polynôme, 278, 466
génération, 37, 45–46
grandes déviations, 231, 248
hachage
dynamique, 111
extensible, 111
virtuel, 111
harmonique
nombre, 235, 344, 464
hauteur, 6, 20, 38, 39, 65–67, 111, 217,
242–256, 267
d’un arbre 2-3, 158–159
d’un arbre–B, 164–165
d’un arbre binaire, 125, 200–204
d’un arbre binaire de recherche, 269
d’un arbre quadrant de recherche, 351,
363–364, 369
totale, 132
variance (abr), 249
horloge, 384, 469
Huffman, 113
hypergéométrique, 367
index (dans les bases de données), 111
insertion
à la racine dans un arbre binaire de
recherche, 24, 49, 64, 261, 406,
409–411, 415
aux feuilles dans un arbre 2–3, 28
aux feuilles dans un arbre binaire de
recherche, 24, 49–52, 64–67, 218,
261, 406–407
aux feuilles dans un arbre m-aire, 339–340
507
des opérations dans un arbre binaire de
recherche randomisé, 271–272
des opérations dans un arbre quadrant de
recherche, 369
du tri par tas, 92
du tri rapide, 80
descendant, 6
différentiation (complexité), 143–146, 175
distribution
de type double exponentielle, 329, 332
diviser pour régner, 52–54, 220, 222, 226, 233,
234, 242, 244, 267, 337, 341, 351,
356
drapeau hollandais, 89
Dyck
chemin, 202, 208
échantillonnage adaptatif, 108–110
élection de leader, 106–107
enraciné, 4
épine dorsale, 192, 256
Ethernet, 107
Euler
constante, 221, 275
excursion, 197
brownienne, 202, 204
expression
bien parenthésée, 176
mathématique, 135–137, 139
famille simple, 16–17, 135–146, 175
feuille, 6, 9
file de priorité, 21, 91
fonction
analytique, 136
Beta, 465, 472, 491
caractéristique, 468
Gamma, 460, 465, 472, 491
génératrice, 122, 128, 133, 219–223
génératrice bivariée, 129, 221
génératrice cumulée, 141
génératrice de probabilité, 129
génératrice des moments, 361, 469
génératrice exponentielle, 169
implicite (théorème), 139
méromorphe, 452, 461
forêt, 7
forme d’arbre, 3, 14, 15, 26, 51, 217, 261, 338
formule
d’équerre, 18, 48, 126, 146, 149, 151
de Lagrange, 138–139, 168, 457
de Nörlund-Rice, 318, 320
de Stirling, 125, 153, 169
forward, 45, 185, 187, 207
Fourier
transformée de, 468
fusion (de deux abr), 262, 264, 272, 406,
411–416
Galton-Watson
arbre, 41, 44, 208, 256, 258
processus, 184, 209, 248
Gamma
fonction, 460, 465, 472, 491
loi, 472
polynôme, 278, 466
génération, 37, 45–46
grandes déviations, 231, 248
hachage
dynamique, 111
extensible, 111
virtuel, 111
harmonique
nombre, 235, 344, 464
hauteur, 6, 20, 38, 39, 65–67, 111, 217,
242–256, 267
d’un arbre 2-3, 158–159
d’un arbre–B, 164–165
d’un arbre binaire, 125, 200–204
d’un arbre binaire de recherche, 269
d’un arbre quadrant de recherche, 351,
363–364, 369
totale, 132
variance (abr), 249
horloge, 384, 469
Huffman, 113
hypergéométrique, 367
index (dans les bases de données), 111
insertion
à la racine dans un arbre binaire de
recherche, 24, 49, 64, 261, 406,
409–411, 415
aux feuilles dans un arbre 2–3, 28
aux feuilles dans un arbre binaire de
recherche, 24, 49–52, 64–67, 218,
261, 406–407
aux feuilles dans un arbre m-aire, 339–340