282
7 Arbres digitaux
Le trie binaire Dans un cadre classique, les analyses des arbres digitaux se
focalisent sur la structure d’arbre digital la plus simple : le trie construit sur des
mots binaires sur l’alphabet A = {0, 1}. Rappelons que les clés sont soit finies,
auquel cas nous considérons des clés de l’ensemble B = A
∗ , soit infinies, et alors
B = A
N . Étant donné un ensemble ω d’éléments de B (i.e., ω ⊂ B), nous rappelons
la notation du chapitre 1
ω \ 0 := {w ∈ B | 0w ∈ ω}, ω \ 1 := {w ∈ B | 1w ∈ ω}.
Pour simplifier la présentation lorsque les clés sont finies, nous supposons
qu’aucune des clés n’est préfixe d’une autre. Le trie associé à ω est alors défini
grâce à la règle récursive :
trie(ω) :=
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
∅
si ω = ∅
la feuille étiquetée par w
si ω = {w}
(•, trie(ω \ 0), trie(ω \ 1)) sinon.
(7.1)
Comme il a déjà été mentionné aux chapitres 1 et 3, la structure de trie est une
structure de données de type dictionnaire, c’est-à-dire qu’elle permet aisément
les opérations d’insertion, de suppression, de recherche ou encore des opérations
ensemblistes. 1 Dans le chapitre 1, nous avons vu que cette structure peut aussi
bien être construite par insertions successives (vision dynamique) que par une
construction de la racine vers les feuilles en suivant la règle (7.1) (vision statique).
Notations Un nœud du trie est associé à un mot fini w ∈ A
∗ sur l’alphabet A.
Le mot w est préfixe de tous les mots contenus dans le sous-trie de racine w, de
manière cohérente avec la définition des arbres préfixes du chapitre 1. Dans les
représentations graphiques du trie comme celle de la figure 7.1, nous ne représentons
pas les sous-tries vides induits par la définition ci-dessus, et nous écrivons les lettres
sur les liens reliant un nœud à son parent à la manière d’un automate, si bien que le
mot w associé à un nœud correspond à la concaténation des lettres rencontrées en
suivant la branche de la racine jusqu’à ce nœud (que ce nœud soit interne ou externe
exactement, comme dans un arbre préfixe de la définition 1.2 en section 1.1.1).
Nous notons dans ce chapitre |ω| le cardinal d’un ensemble ω ⊂ B : c’est le
nombre de clés contenues dans le trie. C’est aussi le nombre de feuilles (ou nœuds
externes) du trie.
1 Voir les rappels algorithmiques de l’annexe A.
7 Arbres digitaux
Le trie binaire Dans un cadre classique, les analyses des arbres digitaux se
focalisent sur la structure d’arbre digital la plus simple : le trie construit sur des
mots binaires sur l’alphabet A = {0, 1}. Rappelons que les clés sont soit finies,
auquel cas nous considérons des clés de l’ensemble B = A
∗ , soit infinies, et alors
B = A
N . Étant donné un ensemble ω d’éléments de B (i.e., ω ⊂ B), nous rappelons
la notation du chapitre 1
ω \ 0 := {w ∈ B | 0w ∈ ω}, ω \ 1 := {w ∈ B | 1w ∈ ω}.
Pour simplifier la présentation lorsque les clés sont finies, nous supposons
qu’aucune des clés n’est préfixe d’une autre. Le trie associé à ω est alors défini
grâce à la règle récursive :
trie(ω) :=
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
∅
si ω = ∅
la feuille étiquetée par w
si ω = {w}
(•, trie(ω \ 0), trie(ω \ 1)) sinon.
(7.1)
Comme il a déjà été mentionné aux chapitres 1 et 3, la structure de trie est une
structure de données de type dictionnaire, c’est-à-dire qu’elle permet aisément
les opérations d’insertion, de suppression, de recherche ou encore des opérations
ensemblistes. 1 Dans le chapitre 1, nous avons vu que cette structure peut aussi
bien être construite par insertions successives (vision dynamique) que par une
construction de la racine vers les feuilles en suivant la règle (7.1) (vision statique).
Notations Un nœud du trie est associé à un mot fini w ∈ A
∗ sur l’alphabet A.
Le mot w est préfixe de tous les mots contenus dans le sous-trie de racine w, de
manière cohérente avec la définition des arbres préfixes du chapitre 1. Dans les
représentations graphiques du trie comme celle de la figure 7.1, nous ne représentons
pas les sous-tries vides induits par la définition ci-dessus, et nous écrivons les lettres
sur les liens reliant un nœud à son parent à la manière d’un automate, si bien que le
mot w associé à un nœud correspond à la concaténation des lettres rencontrées en
suivant la branche de la racine jusqu’à ce nœud (que ce nœud soit interne ou externe
exactement, comme dans un arbre préfixe de la définition 1.2 en section 1.1.1).
Nous notons dans ce chapitre |ω| le cardinal d’un ensemble ω ⊂ B : c’est le
nombre de clés contenues dans le trie. C’est aussi le nombre de feuilles (ou nœuds
externes) du trie.
1 Voir les rappels algorithmiques de l’annexe A.