36
1 Botanique
Fig. 1.35 Un arbre digital de recherche pour la suite de mots (bcaac, cacbcabb, aabcb,
bcacab, caba, aabbaa, caaba, cacbbb), insérés dans cet ordre et correspondant donc à une
permutation de l’ensemble de mots Y de la figure 1.32. Un symbole de terminaison † est ajouté à
la fin de chaque mot
Remarque 1.46 Contrairement au trie, un arbre digital de recherche, construit sur
une suite de mots et non sur un ensemble, dépend de l’ordre d’insertion des
éléments. Remarquons aussi qu’un arbre digital de recherche construit sur n mots
possède exactement n nœuds (figure 1.35).
La figure 1.36 illustre différents types d’arbres digitaux sur un exemple de mots
issus d’un paragraphe du roman Moby Dick de Melville.
1.3 Paramètres d’arbres
1.3.1 Les paramètres classiques
Définition 1.47 Soit T un ensemble d’arbres. Un paramètre est une fonction T →
R.
Un certain nombre de paramètres se retrouvent dans la plupart des analyses sur
les arbres ; nous les présentons ci-dessous. Dans ce qui suit, τ désigne un arbre fini,
∂τ l’ensemble des feuilles de τ , et si u est un nœud de τ , alors M u désigne l’arité
de u (figure 1.37).
– La taille |τ | (déjà rencontrée dans la définition 1.3) est le nombre de nœuds
de τ . Les conventions peuvent varier : parfois la « taille » est le nombre de
nœuds internes de l’arbre, parfois le nombre de ses feuilles ; nous le précisons si
nécessaire.
– Le nombre de nœuds d’arité donnée k est t k = Card{u ∈ τ, M u = k}. Nous
distinguons ainsi, dans les arbres binaires, le nombre de feuilles (nœuds d’arité
0), de nœuds simples, i.e., d’arité 1 (ces nœuds sont absents dans un arbre binaire
complet), ou de nœuds doubles (arité 2).
– Les nœuds d’un arbre τ (planaire ou non) peuvent être partitionnés par niveaux
suivant leur distance à la racine. Nous parlerons indifféremment du niveau d’un
1 Botanique
Fig. 1.35 Un arbre digital de recherche pour la suite de mots (bcaac, cacbcabb, aabcb,
bcacab, caba, aabbaa, caaba, cacbbb), insérés dans cet ordre et correspondant donc à une
permutation de l’ensemble de mots Y de la figure 1.32. Un symbole de terminaison † est ajouté à
la fin de chaque mot
Remarque 1.46 Contrairement au trie, un arbre digital de recherche, construit sur
une suite de mots et non sur un ensemble, dépend de l’ordre d’insertion des
éléments. Remarquons aussi qu’un arbre digital de recherche construit sur n mots
possède exactement n nœuds (figure 1.35).
La figure 1.36 illustre différents types d’arbres digitaux sur un exemple de mots
issus d’un paragraphe du roman Moby Dick de Melville.
1.3 Paramètres d’arbres
1.3.1 Les paramètres classiques
Définition 1.47 Soit T un ensemble d’arbres. Un paramètre est une fonction T →
R.
Un certain nombre de paramètres se retrouvent dans la plupart des analyses sur
les arbres ; nous les présentons ci-dessous. Dans ce qui suit, τ désigne un arbre fini,
∂τ l’ensemble des feuilles de τ , et si u est un nœud de τ , alors M u désigne l’arité
de u (figure 1.37).
– La taille |τ | (déjà rencontrée dans la définition 1.3) est le nombre de nœuds
de τ . Les conventions peuvent varier : parfois la « taille » est le nombre de
nœuds internes de l’arbre, parfois le nombre de ses feuilles ; nous le précisons si
nécessaire.
– Le nombre de nœuds d’arité donnée k est t k = Card{u ∈ τ, M u = k}. Nous
distinguons ainsi, dans les arbres binaires, le nombre de feuilles (nœuds d’arité
0), de nœuds simples, i.e., d’arité 1 (ces nœuds sont absents dans un arbre binaire
complet), ou de nœuds doubles (arité 2).
– Les nœuds d’un arbre τ (planaire ou non) peuvent être partitionnés par niveaux
suivant leur distance à la racine. Nous parlerons indifféremment du niveau d’un