1.2 Arbres marqués
33
Fig. 1.32 Deux représentations pour un trie construit sur l’ensemble de mots Y =
{aabbaa, aabcb, bcaac, bcacab, caaba, caba, cacbbb}. La représentation du haut correspond
à la définition 1.40 comme ensemble préfixe, et la représentation du bas à la définition 1.41 plus
« informatique »: les mots sont lus le long des branches, et les sous-arbres vides qui alourdiraient
le dessin ont été omis
de ces lettres nous créons une branche, et construisons récursivement le soustrie correspondant au sous-ensemble des clés qui commencent par cette lettre,
mais en « effaçant » cette lettre commune en début de mot.
(ii) Nous avons une construction dynamique pour laquelle les clés sont insérées
successivement dans un trie initialement vide en appliquant le principe de construction récursif suivant. Soit w une clé à insérer dans l’arbre.
– Si le trie est vide, la clé est mise dans une feuille qui est l’unique nœud du
trie.
– si le trie est réduit à une feuille contenant une clé y, soit p = p 1 . . . p k le plus
long préfixe commun à w et y. Écrivons w = paw et y = pby (avec a et
b deux lettres distinctes). Une telle décomposition de w et y existe car nous
avons supposé qu’aucun mot n’est préfixe d’un autre. Créons une branche
« filaire » correspondant au préfixe p au bout de laquelle nous attachons les
deux feuilles w et y par des arêtes correspondant respectivement aux lettres
a et b.
33
Fig. 1.32 Deux représentations pour un trie construit sur l’ensemble de mots Y =
{aabbaa, aabcb, bcaac, bcacab, caaba, caba, cacbbb}. La représentation du haut correspond
à la définition 1.40 comme ensemble préfixe, et la représentation du bas à la définition 1.41 plus
« informatique »: les mots sont lus le long des branches, et les sous-arbres vides qui alourdiraient
le dessin ont été omis
de ces lettres nous créons une branche, et construisons récursivement le soustrie correspondant au sous-ensemble des clés qui commencent par cette lettre,
mais en « effaçant » cette lettre commune en début de mot.
(ii) Nous avons une construction dynamique pour laquelle les clés sont insérées
successivement dans un trie initialement vide en appliquant le principe de construction récursif suivant. Soit w une clé à insérer dans l’arbre.
– Si le trie est vide, la clé est mise dans une feuille qui est l’unique nœud du
trie.
– si le trie est réduit à une feuille contenant une clé y, soit p = p 1 . . . p k le plus
long préfixe commun à w et y. Écrivons w = paw et y = pby (avec a et
b deux lettres distinctes). Une telle décomposition de w et y existe car nous
avons supposé qu’aucun mot n’est préfixe d’un autre. Créons une branche
« filaire » correspondant au préfixe p au bout de laquelle nous attachons les
deux feuilles w et y par des arêtes correspondant respectivement aux lettres
a et b.