Chapitre 7
Arbres digitaux
Dans ce chapitre, nous nous concentrerons uniquement sur la structure de trie. Les
autres types d’arbres digitaux ne seront pas abordés sauf en exercice. Les méthodes
présentées, ou du moins leurs principes, s’appliquent néanmoins à ces autres arbres.
Il est de fait assez courant de confondre arbres digitaux et tries.
Les arbres digitaux sont des structures arborescentes assez différentes des autres
structures d’arbres présentées dans ce livre. Par exemple, dans un abr, les clés
sont vues comme des atomes « indivisibles » (éléments d’un domaine comme
des entiers, des réels de l’intervalle [0, 1], etc) alors que dans un trie les clés
sont décomposées sur un alphabet. Et c’est cette décomposition qui est utilisée
pour définir la structure arborescente d’arbre digital. Nous revenons donc sur la
définition des tries (cf section 1.2.7) en nous attachant plus particulièrement au
cas classique de l’alphabet binaire. Ensuite, dans la section 7.1, nous étudions
par des moyens combinatoires et de manière exacte les espérances des principaux
paramètres (taille, longueur de cheminement et hauteur) pour différents modèles
aléatoires : modèle fini équiprobable, modèle infini i.i.d. uniforme, et enfin modèle
des sources générales de la section 2.3.2. Comme souvent avec l’approche de
la combinatoire analytique, les expressions exactes ne sont pas immédiatement
informatives et la section 7.2, dans un deuxième temps, décrit plusieurs moyens
(de nature analytique) afin d’obtenir le développement asymptotique.
Dans ce chapitre, nous insistons particulièrement sur la diversité des modèles
et des analyses. Nous restons par contre dans le cadre assez limitatif de l’analyse
en moyenne : nous calculons seulement l’espérance de paramètres. Il est bien sûr
intéressant d’aller plus loin et d’obtenir selon les paramètres les moments suivants
ou même la loi limite que ce soit pour les tries ou une de leurs généralisations (voir
par exemple [33, 55, 56, 58, 59, 113, 141–145, 150, 166, 204, 208]).
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_7
281
Arbres digitaux
Dans ce chapitre, nous nous concentrerons uniquement sur la structure de trie. Les
autres types d’arbres digitaux ne seront pas abordés sauf en exercice. Les méthodes
présentées, ou du moins leurs principes, s’appliquent néanmoins à ces autres arbres.
Il est de fait assez courant de confondre arbres digitaux et tries.
Les arbres digitaux sont des structures arborescentes assez différentes des autres
structures d’arbres présentées dans ce livre. Par exemple, dans un abr, les clés
sont vues comme des atomes « indivisibles » (éléments d’un domaine comme
des entiers, des réels de l’intervalle [0, 1], etc) alors que dans un trie les clés
sont décomposées sur un alphabet. Et c’est cette décomposition qui est utilisée
pour définir la structure arborescente d’arbre digital. Nous revenons donc sur la
définition des tries (cf section 1.2.7) en nous attachant plus particulièrement au
cas classique de l’alphabet binaire. Ensuite, dans la section 7.1, nous étudions
par des moyens combinatoires et de manière exacte les espérances des principaux
paramètres (taille, longueur de cheminement et hauteur) pour différents modèles
aléatoires : modèle fini équiprobable, modèle infini i.i.d. uniforme, et enfin modèle
des sources générales de la section 2.3.2. Comme souvent avec l’approche de
la combinatoire analytique, les expressions exactes ne sont pas immédiatement
informatives et la section 7.2, dans un deuxième temps, décrit plusieurs moyens
(de nature analytique) afin d’obtenir le développement asymptotique.
Dans ce chapitre, nous insistons particulièrement sur la diversité des modèles
et des analyses. Nous restons par contre dans le cadre assez limitatif de l’analyse
en moyenne : nous calculons seulement l’espérance de paramètres. Il est bien sûr
intéressant d’aller plus loin et d’obtenir selon les paramètres les moments suivants
ou même la loi limite que ce soit pour les tries ou une de leurs généralisations (voir
par exemple [33, 55, 56, 58, 59, 113, 141–145, 150, 166, 204, 208]).
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_7
281