492
E Rappel des notations utilisées
E.2 Arbres
E.2.1 Les différentes familles d’arbres
– B : arbres binaires planaires complets.
– C : arbres binaires planaires, parfois appelés arbres « de Catalan ».
– Cay : arbres de Cayley.
– DST (Y ) : arbre digital de recherche associé à une suite Y de mots.
– M : arbres m-aires (non marqués).
– P : arbres planaires.
– Pó : arbres non planaires, ou arbres de Pólya.
– P (2) : arbres de Pólya binaires.
– Pref (Y ) : arbre préfixe associé à un ensemble Y de mots.
– Q : arbres quadrants de recherche.
Si T est un ensemble d’arbres, la notation T n désigne le sous-ensemble des
arbres de taille n, et la notation T E , avec E ⊂ N, le sous-ensemble des arbres dont
les arités des sommets appartiennent à E.
E.2.2 Les différents types de nœuds
Dans tout le livre, nous utilisons la convention suivante :
– • pour le cas général d’un nœud dans un arbre, et pour les nœuds internes d’un
arbre binaire complété.
– pour une feuille d’un arbre général, ou d’un arbre complété.
– ◦ pour les nœuds d’un arbre binaire, aussi bien internes (simples ou doubles)
qu’externes.
E.2.3 Paramètres d’un arbre τ
– Taille de l’arbre : |τ |.
– Hauteur : h(τ ).
– Niveau de saturation : s(τ ).
– Longueur de cheminement : lc(τ ) ; longueurs de cheminement interne lci(τ ) et
externe lce(τ ),
– Profondeur d’insertion d’une clé α dans l’arbre τ : d(α, τ ).
– Profondeur d’insertion d’une clé dans un arbre de recherche τ n : D n+1 .
– Nombre de feuilles qui se trouvent au niveau p : U p (τ ).
– Polynôme de niveaux : W τ (z).
– S : ensemble de symboles lié à une famille simple d’arbres.