508
Index
aux feuilles dans un arbre quadrant de
recherche, 74, 350, 360–363, 369,
370
aux feuilles dans un arbre–B, 68–70
dans un arbre binaire de recherche,
260–267, 269–270
dans un tas, 48, 92, 442–443
dans un trie, 429
randomisée dans un arbre binaire de
recherche, 261
intervalle
vacant, 341
Jensen
inégalité, 243
Kesten-Stigum
théorème, 194, 195, 208
Kingman
théorème, 207
Kolmogorov
théorème, 52, 57, 189, 351
Kronecker, 383, 384, 491
Laplace
transformée de, 188, 206, 208, 469
largeur, 231
LC-trie, 112
lemme
de correspondance naturelle, 11
de transfert, 136, 140, 145, 171
Lempel-Ziv, 114
localité (de clés), 260
logique
intuitionniste, 98
quantitative, 95
loi
Beta, 472, 482, 483
de Dirichlet, 374, 482, 483
de Poisson, 55, 198, 200, 304, 379, 469
Gamma, 472, 483
Theta, 201, 204, 471
Ord, 50, 217, 260, 262–267, 271
longueur de cheminement, 37–40, 65–67, 82,
125–133, 143, 217, 219–231, 269
cumulée, 127, 129
dans un arbre quadrant de recherche, 356,
358–359, 368, 369
externe, 37, 65–67, 80, 84–88, 114,
231–240
interne, 37, 65–67
loi, 221–223
moyenne, 128, 129, 133, 220–221
variance, 129, 130, 133
marche aléatoire branchante, 242, 244
Markov
chaîne, 43, 50, 341, 347, 373, 473
processus, 44, 204
marquage canonique, see canonique, marquage
marque, 3
martingale, 187, 189, 194, 207, 224–233, 259,
269, 278, 371, 380, 383, 479
matrice
de remplacement, 374, 380, 388
méthode symbolique, 123
Moby Dick, 36
modèle
bourgeonnant, 40, 41
combinatoire, 41, 52, 121–181
de Bernoulli, 303
de Catalan, 40–43, 47, 52, 121–181, 269
de Poisson, 304
des permutations uniformes, 40, 46–47, 49,
52, 81, 218, 221, 263, 267, 273–278,
350
pour les tableaux, 81–85, 92
uniforme, 41, 52
mot, 114
multi-ensemble, 13
niveau, 6, 9, 36, 224
de saturation, 38, 39
de saturation, 65–67, 242, 246, 269
nœud
double, 9, 36, 40, 134
externe, 6
interne, 6, 32
interne terminal, 6, 27, 338
plein, 340
simple, 9, 36
spécial, 146, 148
numérotation
canonique, 4
OEIS, Online Encyclopaedia of Integer
Sequences, 125, 160
ordre
hiérarchique, 19, 48, 126, 147, 148, 403
postfixe, 402
préfixe, 402
suffixe, 402
symétrique, 402
Index
aux feuilles dans un arbre quadrant de
recherche, 74, 350, 360–363, 369,
370
aux feuilles dans un arbre–B, 68–70
dans un arbre binaire de recherche,
260–267, 269–270
dans un tas, 48, 92, 442–443
dans un trie, 429
randomisée dans un arbre binaire de
recherche, 261
intervalle
vacant, 341
Jensen
inégalité, 243
Kesten-Stigum
théorème, 194, 195, 208
Kingman
théorème, 207
Kolmogorov
théorème, 52, 57, 189, 351
Kronecker, 383, 384, 491
Laplace
transformée de, 188, 206, 208, 469
largeur, 231
LC-trie, 112
lemme
de correspondance naturelle, 11
de transfert, 136, 140, 145, 171
Lempel-Ziv, 114
localité (de clés), 260
logique
intuitionniste, 98
quantitative, 95
loi
Beta, 472, 482, 483
de Dirichlet, 374, 482, 483
de Poisson, 55, 198, 200, 304, 379, 469
Gamma, 472, 483
Theta, 201, 204, 471
Ord, 50, 217, 260, 262–267, 271
longueur de cheminement, 37–40, 65–67, 82,
125–133, 143, 217, 219–231, 269
cumulée, 127, 129
dans un arbre quadrant de recherche, 356,
358–359, 368, 369
externe, 37, 65–67, 80, 84–88, 114,
231–240
interne, 37, 65–67
loi, 221–223
moyenne, 128, 129, 133, 220–221
variance, 129, 130, 133
marche aléatoire branchante, 242, 244
Markov
chaîne, 43, 50, 341, 347, 373, 473
processus, 44, 204
marquage canonique, see canonique, marquage
marque, 3
martingale, 187, 189, 194, 207, 224–233, 259,
269, 278, 371, 380, 383, 479
matrice
de remplacement, 374, 380, 388
méthode symbolique, 123
Moby Dick, 36
modèle
bourgeonnant, 40, 41
combinatoire, 41, 52, 121–181
de Bernoulli, 303
de Catalan, 40–43, 47, 52, 121–181, 269
de Poisson, 304
des permutations uniformes, 40, 46–47, 49,
52, 81, 218, 221, 263, 267, 273–278,
350
pour les tableaux, 81–85, 92
uniforme, 41, 52
mot, 114
multi-ensemble, 13
niveau, 6, 9, 36, 224
de saturation, 38, 39
de saturation, 65–67, 242, 246, 269
nœud
double, 9, 36, 40, 134
externe, 6
interne, 6, 32
interne terminal, 6, 27, 338
plein, 340
simple, 9, 36
spécial, 146, 148
numérotation
canonique, 4
OEIS, Online Encyclopaedia of Integer
Sequences, 125, 160
ordre
hiérarchique, 19, 48, 126, 147, 148, 403
postfixe, 402
préfixe, 402
suffixe, 402
symétrique, 402