506
Index
de recherche, 27–30, 67–75
de Yule, 249–252
des rangs, 14, 15, 17, 18, 21, 22
des suffixes, 75, 77
digital, 30–36, 54–60, 75–78, 112
digital de recherche, 34–36, 76, 116
équilibré, 158–167, 270–271
étiqueté, 14
filiforme, 126, 267, 270
généalogique, 61
idéal, 244–247
lexicographique, 30–31
m-aire, 338
m-aire de recherche, 27, 90, 337–348
marqué, 14–36, 46–255
non marqué, 4–14, 41–46
non planaire, 13–14, 168–174
paginé, 38, 89
parfait, 20–21, 48, 85, 93, 126, 146
Patricia, 34, 75–76, 107, 112
planaire, 4–167, 175–176
préfixe, 5, 31
quadrant, 71–75, 349
quadrant complet, 71
quadrant de recherche, 71–74, 349–369,
425
quadrant paginé, 357, 368, 370–371
randomisé, 272
récursif, 22, 253–256, 386
saturé, 20, 158, 363
ternaire, 138
Union-Find, 101–105, 255
arité, 6, 7, 9, 17, 36, 39, 44
b-trie, 34
backward, 45, 185
balance, 375, 380, 385
Beta
fonction, 465, 472, 491
loi, 472
Biggins
théorème, 208
bijection
planaire-binaire, 11–13, 138
bisection, 244–248
branche droite, 39, 270
branchement
processus, 204, 385
camembert
hypothèse, 457–459
canonique
marquage, 15, 18, 19, 21, 26, 28, 46, 47,
68, 273, 339, 340
numérotation, 4
représentation, 4–9
cascade, 205
Catalan
C.E., 124
nombre, 42, 124, 125, 130, 173, 349
chemin
de Dyck, 202, 208
Chernov,
lemme, 248
classe d’équivalence, 101
code
de Huffman, 114
instantané, 113
préfixe, 112
combinatoire
classe, 3, 4, 7–8, 13
compatibles
distributions, 52
permutations, 52, 351
compression
de chemins, 103
de données, 112–117
comptage
approché, 108–110
probabiliste, 108
condition x log x, 194, 208
construction
d’un arbre 2-3, 28–30
d’un arbre binaire de recherche, 24–26, 79
d’un arbre m-aire, 339–340
d’un arbre quadrant, 74
d’un arbre-B, 68–70
d’un tas, 47–48
contour, 202
contraction
lemme, 236
méthode, 233–240
coupure, 261, 263–265, 272, 406, 409–411
coût
d’insertion, 66
d’insertion dans un tas, 157
de construction d’un arbre binaire de
recherche, 66
de construction d’un tas, 155–156
de recherche avec succès dans un arbre
binaire de recherche, 66
de recherche sans succès dans un arbre
binaire de recherche, 66
de suppression dans un arbre binaire de
recherche, 66
de suppression dans un tas, 156–157
Index
de recherche, 27–30, 67–75
de Yule, 249–252
des rangs, 14, 15, 17, 18, 21, 22
des suffixes, 75, 77
digital, 30–36, 54–60, 75–78, 112
digital de recherche, 34–36, 76, 116
équilibré, 158–167, 270–271
étiqueté, 14
filiforme, 126, 267, 270
généalogique, 61
idéal, 244–247
lexicographique, 30–31
m-aire, 338
m-aire de recherche, 27, 90, 337–348
marqué, 14–36, 46–255
non marqué, 4–14, 41–46
non planaire, 13–14, 168–174
paginé, 38, 89
parfait, 20–21, 48, 85, 93, 126, 146
Patricia, 34, 75–76, 107, 112
planaire, 4–167, 175–176
préfixe, 5, 31
quadrant, 71–75, 349
quadrant complet, 71
quadrant de recherche, 71–74, 349–369,
425
quadrant paginé, 357, 368, 370–371
randomisé, 272
récursif, 22, 253–256, 386
saturé, 20, 158, 363
ternaire, 138
Union-Find, 101–105, 255
arité, 6, 7, 9, 17, 36, 39, 44
b-trie, 34
backward, 45, 185
balance, 375, 380, 385
Beta
fonction, 465, 472, 491
loi, 472
Biggins
théorème, 208
bijection
planaire-binaire, 11–13, 138
bisection, 244–248
branche droite, 39, 270
branchement
processus, 204, 385
camembert
hypothèse, 457–459
canonique
marquage, 15, 18, 19, 21, 26, 28, 46, 47,
68, 273, 339, 340
numérotation, 4
représentation, 4–9
cascade, 205
Catalan
C.E., 124
nombre, 42, 124, 125, 130, 173, 349
chemin
de Dyck, 202, 208
Chernov,
lemme, 248
classe d’équivalence, 101
code
de Huffman, 114
instantané, 113
préfixe, 112
combinatoire
classe, 3, 4, 7–8, 13
compatibles
distributions, 52
permutations, 52, 351
compression
de chemins, 103
de données, 112–117
comptage
approché, 108–110
probabiliste, 108
condition x log x, 194, 208
construction
d’un arbre 2-3, 28–30
d’un arbre binaire de recherche, 24–26, 79
d’un arbre m-aire, 339–340
d’un arbre quadrant, 74
d’un arbre-B, 68–70
d’un tas, 47–48
contour, 202
contraction
lemme, 236
méthode, 233–240
coupure, 261, 263–265, 272, 406, 409–411
coût
d’insertion, 66
d’insertion dans un tas, 157
de construction d’un arbre binaire de
recherche, 66
de construction d’un tas, 155–156
de recherche avec succès dans un arbre
binaire de recherche, 66
de recherche sans succès dans un arbre
binaire de recherche, 66
de suppression dans un arbre binaire de
recherche, 66
de suppression dans un tas, 156–157