Introduction
xxi
étudier non seulement la moyenne mais les moments d’ordres supérieurs ou la
loi limite de la longueur de cheminement, il s’avère souvent pertinent de recourir
à d’autres méthodes : des théorèmes de point fixe, des outils probabilistes, par
exemple en faisant apparaître des martingales.
Pour une recherche sans succès dans un arbre τ , nous pouvons toujours mesurer
son coût en nombre de nœuds visités, ou en nombre de comparaisons de clés :
c’est la profondeur d’insertion de la clé x dans τ . Remarquons que cette profondeur
d’insertion de x est la profondeur à laquelle nous trouverons la clé lors de recherches
avec succès ultérieures.
Quels arbres ?
Ce livre ne prétend pas être exhaustif. Nous avons retenu les classes d’arbres
suivantes, fréquemment rencontrées en informatique :
– les arbres binaires planaires, qui sont « la » structure arborescente de base, et
plus généralement les arbres planaires, puis les familles simples d’arbres et les
arbres non planaires ;
– les tas, qui sont des arbres binaires particuliers, essentiels pour une méthode de
tri dite (justement !) « par tas », et qui permettent aussi d’implémenter des files
de priorité ;
– les structures digitales, essentiellement les tries, qui apparaissent souvent dans
les algorithmes sur des chaînes de caractères, et permettent en outre de modéliser
le comportement d’algorithmes venant de domaines variés ;
– les arbres de Galton-Watson et d’autres processus de branchement dont les
marches aléatoires branchantes ;
– les arbres binaires de recherche, les arbres récursifs qui en sont proches, et
certaines de leurs variantes : arbres quadrants, arbres 2-3, arbres-B, arbres maires de recherche ; l’analyse de certaines de ces structures, appelée parfois
« analyse de frange », fait souvent intervenir des urnes de Pólya.
Nous avons par ailleurs fait le choix d’étudier prioritairement certains paramètres
sur les arbres, tout d’abord le nombre d’arbres de taille (nombre de nœuds) donnée,
puis la longueur de cheminement et la hauteur, paramètres qui sont à la fois les plus
classiques et parmi les plus utiles en analyse d’algorithmes.
Les différents types d’arbres, ainsi que les paramètres liés aux complexités des
algorithmes les plus courants sur ces arbres, sont présentés dans les chapitres 1
à 2 ; dans ces deux premiers chapitres sont également mis en place les principaux
cadres mathématiques permettant l’analyse de ces paramètres. Le chapitre 3 est à la
fois plus informel et au cœur du sujet : il présente un certain nombre d’exemples,
plus ou moins classiques, de l’utilisation très diverse de structures arborescentes
en algorithmique et en analyse d’algorithmes et de la manière dont les paramètres
d’arbres déterminent la complexité d’un algorithme. L’analyse desdits paramètres
xxi
étudier non seulement la moyenne mais les moments d’ordres supérieurs ou la
loi limite de la longueur de cheminement, il s’avère souvent pertinent de recourir
à d’autres méthodes : des théorèmes de point fixe, des outils probabilistes, par
exemple en faisant apparaître des martingales.
Pour une recherche sans succès dans un arbre τ , nous pouvons toujours mesurer
son coût en nombre de nœuds visités, ou en nombre de comparaisons de clés :
c’est la profondeur d’insertion de la clé x dans τ . Remarquons que cette profondeur
d’insertion de x est la profondeur à laquelle nous trouverons la clé lors de recherches
avec succès ultérieures.
Quels arbres ?
Ce livre ne prétend pas être exhaustif. Nous avons retenu les classes d’arbres
suivantes, fréquemment rencontrées en informatique :
– les arbres binaires planaires, qui sont « la » structure arborescente de base, et
plus généralement les arbres planaires, puis les familles simples d’arbres et les
arbres non planaires ;
– les tas, qui sont des arbres binaires particuliers, essentiels pour une méthode de
tri dite (justement !) « par tas », et qui permettent aussi d’implémenter des files
de priorité ;
– les structures digitales, essentiellement les tries, qui apparaissent souvent dans
les algorithmes sur des chaînes de caractères, et permettent en outre de modéliser
le comportement d’algorithmes venant de domaines variés ;
– les arbres de Galton-Watson et d’autres processus de branchement dont les
marches aléatoires branchantes ;
– les arbres binaires de recherche, les arbres récursifs qui en sont proches, et
certaines de leurs variantes : arbres quadrants, arbres 2-3, arbres-B, arbres maires de recherche ; l’analyse de certaines de ces structures, appelée parfois
« analyse de frange », fait souvent intervenir des urnes de Pólya.
Nous avons par ailleurs fait le choix d’étudier prioritairement certains paramètres
sur les arbres, tout d’abord le nombre d’arbres de taille (nombre de nœuds) donnée,
puis la longueur de cheminement et la hauteur, paramètres qui sont à la fois les plus
classiques et parmi les plus utiles en analyse d’algorithmes.
Les différents types d’arbres, ainsi que les paramètres liés aux complexités des
algorithmes les plus courants sur ces arbres, sont présentés dans les chapitres 1
à 2 ; dans ces deux premiers chapitres sont également mis en place les principaux
cadres mathématiques permettant l’analyse de ces paramètres. Le chapitre 3 est à la
fois plus informel et au cœur du sujet : il présente un certain nombre d’exemples,
plus ou moins classiques, de l’utilisation très diverse de structures arborescentes
en algorithmique et en analyse d’algorithmes et de la manière dont les paramètres
d’arbres déterminent la complexité d’un algorithme. L’analyse desdits paramètres