Table des matières
xxvii
4.4 Arbres équilibrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 158
4.4.1 Arbres 2–3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 158
4.4.2 Arbres-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 164
4.5 Arbres non planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 168
4.5.1 Arbres de Cayley . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 168
4.5.2 Arbres de Pólya binaires . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 169
4.5.3 Dénombrement des arbres de Pólya . . . . . .. . . . . . . . . . . . . . . . . . . . 172
4.6 Exercices et problèmes .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 174
5 Approche probabiliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 183
5.1 Arbres de Galton-Watson . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 183
5.1.1 Extinction ou non ? . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 184
5.1.2 Arbre de Galton-Watson biaisé . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 189
5.1.3 Processus surcritique : Théorème de Kesten-Stigum . . . . . . . . 194
5.2 Modèle de Catalan et arbres de Galton-Watson .. .. . . . . . . . . . . . . . . . . . . . 196
5.2.1 Pour les arbres binaires et les arbres planaires . . . . . . . . . . . . . . . 196
5.2.2 Pour les arbres de Cayley . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 198
5.2.3 Largeur et hauteur des arbres sous le modèle de Catalan .. . . 200
5.3 Marche aléatoire branchante . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 204
5.4 Exercices et problèmes .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 208
6 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 217
6.1 Analyses de la longueur de cheminement et du profil . . . . . . . . . . . . . . . . 219
6.1.1 Longueur de cheminement et séries génératrices . . . . . . . . . . . . 219
6.1.2 Longueur de cheminement, profil et martingales . . . . . . . . . . . . 224
6.1.3 Méthode de contraction . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 233
6.1.4 Simulation de la loi limite .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 240
6.2 Analyse de la hauteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 242
6.2.1 Une approche élémentaire.. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 242
6.2.2 Connexion abr - bisection .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 244
6.2.3 Connexion abr - arbre de Yule . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 249
6.3 Arbres récursifs .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 253
6.3.1 Définition et dynamique .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 253
6.3.2 Hauteur des arbres récursifs.. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 256
6.4 Formes d’arbres binaires de recherche biaisées . . .. . . . . . . . . . . . . . . . . . . . 256
6.5 Arbres binaires de recherche randomisés . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 260
6.5.1 Randomisation d’un arbre binaire de recherche.. . . . . . . . . . . . . 260
6.5.2 Loi des arbres binaires de recherche randomisés . . . . . . . . . . . . 263
6.6 Coût des opérations algorithmiques . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 267
6.6.1 Arbres binaires de recherche classiques . .. . . . . . . . . . . . . . . . . . . . 267
6.6.2 Arbres équilibrés . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 270
6.6.3 Arbres binaires de recherche randomisés.. . . . . . . . . . . . . . . . . . . . 271
6.7 Un algorithme proche : le tri rapide . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 272
6.7.1 Modèle probabiliste et paramètres de coût . . . . . . . . . . . . . . . . . . . 273
6.7.2 Nombre moyen de comparaisons de clés . . . . . . . . . . . . . . . . . . . . . 273
6.7.3 Nombre d’échanges de clés . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 275
6.8 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 277
xxvii
4.4 Arbres équilibrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 158
4.4.1 Arbres 2–3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 158
4.4.2 Arbres-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 164
4.5 Arbres non planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 168
4.5.1 Arbres de Cayley . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 168
4.5.2 Arbres de Pólya binaires . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 169
4.5.3 Dénombrement des arbres de Pólya . . . . . .. . . . . . . . . . . . . . . . . . . . 172
4.6 Exercices et problèmes .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 174
5 Approche probabiliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 183
5.1 Arbres de Galton-Watson . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 183
5.1.1 Extinction ou non ? . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 184
5.1.2 Arbre de Galton-Watson biaisé . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 189
5.1.3 Processus surcritique : Théorème de Kesten-Stigum . . . . . . . . 194
5.2 Modèle de Catalan et arbres de Galton-Watson .. .. . . . . . . . . . . . . . . . . . . . 196
5.2.1 Pour les arbres binaires et les arbres planaires . . . . . . . . . . . . . . . 196
5.2.2 Pour les arbres de Cayley . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 198
5.2.3 Largeur et hauteur des arbres sous le modèle de Catalan .. . . 200
5.3 Marche aléatoire branchante . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 204
5.4 Exercices et problèmes .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 208
6 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 217
6.1 Analyses de la longueur de cheminement et du profil . . . . . . . . . . . . . . . . 219
6.1.1 Longueur de cheminement et séries génératrices . . . . . . . . . . . . 219
6.1.2 Longueur de cheminement, profil et martingales . . . . . . . . . . . . 224
6.1.3 Méthode de contraction . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 233
6.1.4 Simulation de la loi limite .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 240
6.2 Analyse de la hauteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 242
6.2.1 Une approche élémentaire.. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 242
6.2.2 Connexion abr - bisection .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 244
6.2.3 Connexion abr - arbre de Yule . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 249
6.3 Arbres récursifs .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 253
6.3.1 Définition et dynamique .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 253
6.3.2 Hauteur des arbres récursifs.. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 256
6.4 Formes d’arbres binaires de recherche biaisées . . .. . . . . . . . . . . . . . . . . . . . 256
6.5 Arbres binaires de recherche randomisés . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 260
6.5.1 Randomisation d’un arbre binaire de recherche.. . . . . . . . . . . . . 260
6.5.2 Loi des arbres binaires de recherche randomisés . . . . . . . . . . . . 263
6.6 Coût des opérations algorithmiques . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 267
6.6.1 Arbres binaires de recherche classiques . .. . . . . . . . . . . . . . . . . . . . 267
6.6.2 Arbres équilibrés . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 270
6.6.3 Arbres binaires de recherche randomisés.. . . . . . . . . . . . . . . . . . . . 271
6.7 Un algorithme proche : le tri rapide . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 272
6.7.1 Modèle probabiliste et paramètres de coût . . . . . . . . . . . . . . . . . . . 273
6.7.2 Nombre moyen de comparaisons de clés . . . . . . . . . . . . . . . . . . . . . 273
6.7.3 Nombre d’échanges de clés . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 275
6.8 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 277