xxviii
Table des matières
7 Arbres digitaux .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 281
7.1 Analyses exactes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 283
7.1.1 Approche symbolique (modèle fini équiprobable) .. . . . . . . . . . 285
7.1.2 Approche symbolique (modèle infini i.i.d. binaire
uniforme).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 293
7.1.3 Approche symbolique (sources) . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 300
7.2 Analyses asymptotiques .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 308
7.2.1 Paramètres additifs : méthode élémentaire . . . . . . . . . . . . . . . . . . . 309
7.2.2 Paramètres additifs : transformée de Mellin.. . . . . . . . . . . . . . . . . 313
7.2.3 Paramètres additifs : formule de Nörlund-Rice . . . . . . . . . . . . . . 315
7.2.4 Hauteur .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 325
7.3 Mise en perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 332
7.4 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 333
8 Arbres m-aires et quadrants .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 337
8.1 Arbres m-aires de recherche . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 337
8.1.1 Définitions des arbres m-aires de recherche .. . . . . . . . . . . . . . . . . 338
8.1.2 Etude des arbres m-aires de recherche par séries
génératrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 341
8.1.3 Etude dynamique des arbres m-aires de recherche.. . . . . . . . . . 345
8.2 Arbres quadrants de recherche .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 349
8.2.1 Dénombrement des arbres quadrants . . . . .. . . . . . . . . . . . . . . . . . . . 349
8.2.2 Aléa sur les arbres quadrants de recherche .. . . . . . . . . . . . . . . . . . 349
8.2.3 Probabilités induites sur les sous-arbres ... . . . . . . . . . . . . . . . . . . . 351
8.2.4 Paramètres additifs . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 355
8.2.5 Profondeur d’insertion d’une clé : cas d = 2 . . . . . . . . . . . . . . . . 360
8.2.6 Hauteur d’un arbre quadrant de recherche . . . . . . . . . . . . . . . . . . . 363
8.2.7 Polynômes de niveaux .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 364
8.2.8 Synthèse des résultats et interprétation algorithmique .. . . . . . 368
8.3 Exercices et problèmes .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 370
9 Urnes de Pólya et applications .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 373
9.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 373
9.2 Etude combinatoire analytique.. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 375
9.2.1 Les histoires.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 375
9.2.2 Une urne dans un abr .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 379
9.3 Etude probabiliste dynamique . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 380
9.3.1 Etude en moyenne . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 381
9.3.2 Comportement asymptotique de Y n : approche
algébrique .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 383
9.4 Passage du modèle combinatoire discret au modèle continu .. . . . . . . . 384
9.4.1 Principe du plongement en temps continu.. . . . . . . . . . . . . . . . . . . 384
9.4.2 Principaux résultats .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 385
9.5 Applications algorithmiques . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 386
9.5.1 Arbres m-aires de recherche . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 387
9.5.2 Arbres 2–3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 390
Table des matières
7 Arbres digitaux .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 281
7.1 Analyses exactes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 283
7.1.1 Approche symbolique (modèle fini équiprobable) .. . . . . . . . . . 285
7.1.2 Approche symbolique (modèle infini i.i.d. binaire
uniforme).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 293
7.1.3 Approche symbolique (sources) . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 300
7.2 Analyses asymptotiques .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 308
7.2.1 Paramètres additifs : méthode élémentaire . . . . . . . . . . . . . . . . . . . 309
7.2.2 Paramètres additifs : transformée de Mellin.. . . . . . . . . . . . . . . . . 313
7.2.3 Paramètres additifs : formule de Nörlund-Rice . . . . . . . . . . . . . . 315
7.2.4 Hauteur .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 325
7.3 Mise en perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 332
7.4 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 333
8 Arbres m-aires et quadrants .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 337
8.1 Arbres m-aires de recherche . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 337
8.1.1 Définitions des arbres m-aires de recherche .. . . . . . . . . . . . . . . . . 338
8.1.2 Etude des arbres m-aires de recherche par séries
génératrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 341
8.1.3 Etude dynamique des arbres m-aires de recherche.. . . . . . . . . . 345
8.2 Arbres quadrants de recherche .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 349
8.2.1 Dénombrement des arbres quadrants . . . . .. . . . . . . . . . . . . . . . . . . . 349
8.2.2 Aléa sur les arbres quadrants de recherche .. . . . . . . . . . . . . . . . . . 349
8.2.3 Probabilités induites sur les sous-arbres ... . . . . . . . . . . . . . . . . . . . 351
8.2.4 Paramètres additifs . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 355
8.2.5 Profondeur d’insertion d’une clé : cas d = 2 . . . . . . . . . . . . . . . . 360
8.2.6 Hauteur d’un arbre quadrant de recherche . . . . . . . . . . . . . . . . . . . 363
8.2.7 Polynômes de niveaux .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 364
8.2.8 Synthèse des résultats et interprétation algorithmique .. . . . . . 368
8.3 Exercices et problèmes .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 370
9 Urnes de Pólya et applications .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 373
9.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 373
9.2 Etude combinatoire analytique.. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 375
9.2.1 Les histoires.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 375
9.2.2 Une urne dans un abr .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 379
9.3 Etude probabiliste dynamique . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 380
9.3.1 Etude en moyenne . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 381
9.3.2 Comportement asymptotique de Y n : approche
algébrique .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 383
9.4 Passage du modèle combinatoire discret au modèle continu .. . . . . . . . 384
9.4.1 Principe du plongement en temps continu.. . . . . . . . . . . . . . . . . . . 384
9.4.2 Principaux résultats .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 385
9.5 Applications algorithmiques . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 386
9.5.1 Arbres m-aires de recherche . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 387
9.5.2 Arbres 2–3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 390