Avant-propos
xi
chaînes de caractères, la recherche d’un élément dans un ensemble, et le tri d’un
ensemble, soit pour des situations plus élaborées ; c’est ce chapitre qui justifie un
éventuel intérêt pratique du livre.
Dans les chapitres 4 à 9 sont analysées de nombreuses familles d’arbres, qui
diffèrent notamment par le type d’aléa.
– Au chapitre 4 sont étudiés d’abord les arbres binaires planaires, puis différentes
familles d’arbres planaires (familles simples d’arbres, tas, arbres équilibrés), et
ensuite les arbres non planaires, le tout sous un modèle probabiliste où les arbres
de même taille (parfois de même hauteur) sont équiprobables. Nous sommes
ainsi dans le domaine de la combinatoire.
– Au chapitre 5 sont présentés les processus de branchement, notamment les arbres
de Galton-Watson et les marches aléatoires branchantes. Un lien est également
établi entre les arbres de Galton-Watson et les arbres « combinatoires » étudiés
au chapitre précédent. Le point de vue est largement probabiliste, même si la
récursivité partout présente n’est pas sans rappeler les raisonnements du type
« diviser pour régner » utilisés aux chapitres 2 et 4.
– Le chapitre 6 concerne les arbres binaires de recherche et plusieurs de leurs
extensions, venues soit des probabilités (arbres biaisés), soit de l’informatique
(arbres récursifs, arbres binaires de recherche randomisés, lien avec le tri rapide).
Nous utilisons les deux points de vue probabiliste ou combinatoire de façon
complémentaire.
– Les tries, qui sont la structure digitale de base, sont analysés dans le chapitre 7,
essentiellement avec des outils de combinatoire analytique.
– Deux types d’arbres de recherche, étendant les classiques arbres binaires de
recherche, sont analysés en détail dans le chapitre 8 : les arbres m-aires, dans
lesquels il est possible d’avoir plusieurs clés dans un même nœud, puis les arbres
quadrants, qui permettent de prendre en compte des clés multi-dimensionnelles.
– Enfin, au chapitre 9 sont approfondis les résultats sur les arbres de recherche, en
voyant certains de leurs paramètres comme une urne de Pólya ; les analyses font
intervenir successivement combinatoire analytique et probabilités.
Les annexes qui terminent ce livre devraient permettre à nos lecteurs de trouver les
bases nécessaires pour suivre nos modélisations et analyses.
– À l’annexe A sont présentés les algorithmes les plus classiques sur la plupart des
structures arborescentes que nous rencontrons dans les chapitres précédents.
– Les annexes B et C, quant à elles, sont des compendiums des notions mathématiques, respectivement combinatoires et probabilistes, nécessaires à la compréhension des modèles et des analyses présentés dans les chapitres 1 à 9.
– Enfin, l’annexe D présente une histoire, partielle et partiale, de l’utilisation des
arbres en analyse d’algorithmes.
Prérequis Une familiarité avec les outils mathématiques de base (niveau L2)
est souhaitable. Une connaissance de tout ou partie des outils que nous utilisons
(combinatoire analytique, probabilités), ou des implémentations informatiques des
xi
chaînes de caractères, la recherche d’un élément dans un ensemble, et le tri d’un
ensemble, soit pour des situations plus élaborées ; c’est ce chapitre qui justifie un
éventuel intérêt pratique du livre.
Dans les chapitres 4 à 9 sont analysées de nombreuses familles d’arbres, qui
diffèrent notamment par le type d’aléa.
– Au chapitre 4 sont étudiés d’abord les arbres binaires planaires, puis différentes
familles d’arbres planaires (familles simples d’arbres, tas, arbres équilibrés), et
ensuite les arbres non planaires, le tout sous un modèle probabiliste où les arbres
de même taille (parfois de même hauteur) sont équiprobables. Nous sommes
ainsi dans le domaine de la combinatoire.
– Au chapitre 5 sont présentés les processus de branchement, notamment les arbres
de Galton-Watson et les marches aléatoires branchantes. Un lien est également
établi entre les arbres de Galton-Watson et les arbres « combinatoires » étudiés
au chapitre précédent. Le point de vue est largement probabiliste, même si la
récursivité partout présente n’est pas sans rappeler les raisonnements du type
« diviser pour régner » utilisés aux chapitres 2 et 4.
– Le chapitre 6 concerne les arbres binaires de recherche et plusieurs de leurs
extensions, venues soit des probabilités (arbres biaisés), soit de l’informatique
(arbres récursifs, arbres binaires de recherche randomisés, lien avec le tri rapide).
Nous utilisons les deux points de vue probabiliste ou combinatoire de façon
complémentaire.
– Les tries, qui sont la structure digitale de base, sont analysés dans le chapitre 7,
essentiellement avec des outils de combinatoire analytique.
– Deux types d’arbres de recherche, étendant les classiques arbres binaires de
recherche, sont analysés en détail dans le chapitre 8 : les arbres m-aires, dans
lesquels il est possible d’avoir plusieurs clés dans un même nœud, puis les arbres
quadrants, qui permettent de prendre en compte des clés multi-dimensionnelles.
– Enfin, au chapitre 9 sont approfondis les résultats sur les arbres de recherche, en
voyant certains de leurs paramètres comme une urne de Pólya ; les analyses font
intervenir successivement combinatoire analytique et probabilités.
Les annexes qui terminent ce livre devraient permettre à nos lecteurs de trouver les
bases nécessaires pour suivre nos modélisations et analyses.
– À l’annexe A sont présentés les algorithmes les plus classiques sur la plupart des
structures arborescentes que nous rencontrons dans les chapitres précédents.
– Les annexes B et C, quant à elles, sont des compendiums des notions mathématiques, respectivement combinatoires et probabilistes, nécessaires à la compréhension des modèles et des analyses présentés dans les chapitres 1 à 9.
– Enfin, l’annexe D présente une histoire, partielle et partiale, de l’utilisation des
arbres en analyse d’algorithmes.
Prérequis Une familiarité avec les outils mathématiques de base (niveau L2)
est souhaitable. Une connaissance de tout ou partie des outils que nous utilisons
(combinatoire analytique, probabilités), ou des implémentations informatiques des