Table des matières
Partie I Modèles
1 Botanique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
3
1.1 Arbres non marqués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
4
1.1.1 Arbres planaires . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
4
1.1.2 Arbres binaires et arbres binaires complets . . . . . . . . . . . . . . . . . .
8
1.1.3 Bijection entre les arbres planaires et les arbres binaires .. . . 11
1.1.4 Arbres non planaires, ou de Pólya. . . . . . . .. . . . . . . . . . . . . . . . . . . . 13
1.2 Arbres marqués .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 14
1.2.1 Définition des arbres marqués . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 14
1.2.2 Familles simples d’arbres . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 16
1.2.3 Arbres de Cayley . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 17
1.2.4 Arbres croissants, tas, et arbres récursifs .. . . . . . . . . . . . . . . . . . . . 18
1.2.5 Arbres binaires de recherche .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 22
1.2.6 Arbres de recherche . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 27
1.2.7 Arbres digitaux : tries . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 30
1.2.8 Autres types d’arbres digitaux . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 34
1.3 Paramètres d’arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 36
1.3.1 Les paramètres classiques . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 36
1.3.2 Paramètres additifs . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 39
1.3.3 Loi d’un paramètre . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 40
2 Aléa sur les arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 41
2.1 Aléa sur les arbres non marqués . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 41
2.1.1 Modèle de Catalan .. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 41
2.1.2 Arbres bourgeonnants . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 43
2.1.3 Arbres de branchement. Arbres de Galton-Watson . . . . . . . . . . 44
2.2 Aléa sur les arbres marqués .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 46
2.2.1 Le modèle des permutations uniformes . .. . . . . . . . . . . . . . . . . . . . 46
2.2.2 Aléa sur les tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 47
2.2.3 Arbres binaires de recherche aléatoires.. .. . . . . . . . . . . . . . . . . . . . 49
xxv