1.3 Paramètres d’arbres
39
Fig. 1.38 Un arbre binaire
de recherche à 7 clés
taille d’une « page ») n’est pas « développé », mais est réduit à une unique feuille
marquée par l’ensemble de toutes les clés de ce sous-arbre (c’est une notion qui
étend celle de trie paginé, définie en section 1.2.8). Alors le nombre de feuilles
d’un tel arbre est le nombre de sous-arbres de taille au plus b dans l’arbre initial.
– Pour un arbre de recherche (binaire ou non) τ , nous définissons d(α, τ ), la
profondeur d’insertion d’une clé α dans un arbre τ : c’est le niveau auquel se
trouve la clé α dans l’arbre obtenu après insertion de cette clé dans l’arbre τ ,
i.e., sa profondeur. Par exemple, dans l’arbre τ de la figure 1.38, la clé 8 doit
être insérée comme enfant gauche de 9, et aura donc une profondeur d’insertion
d(8, τ ) = 2, et la clé 5 comme enfant gauche de 6, avec une profondeur
d’insertion d(5, τ ) = 4.
Certains paramètres ne sont définis que sur les arbres planaires, pour lesquels
les sous-arbres d’un nœud donné sont naturellement ordonnés de gauche à droite.
Nous parlerons ainsi du j -ième sous-arbre d’un nœud (j étant un entier), ou de la
longueur de la branche droite dans un arbre τ : c’est la profondeur de la feuille la
plus à droite (bien sûr, on peut définir de même la longueur de la feuille la plus à
gauche, etc.) Lorsque l’arbre n’est pas planaire, les sous-arbres d’un nœud forment
un ensemble et la notion de j -ième sous-arbre comme celle de branche gauche ou
droite n’ont pas de sens.
1.3.2 Paramètres additifs
Les paramètres d’arbre ne sont pas tous de même nature ; certains comme la taille ou
la longueur de cheminement sont des paramètres additifs, c’est-à-dire une fonction
f (τ ) de l’arbre qui s’exprime additivement en fonction des sous-arbres enfants de
la racine. La taille, ou plus généralement le nombre de nœuds d’arité donnée d’un
arbre, sa longueur de cheminement, sont des paramètres additifs ; la hauteur ou le
niveau de saturation ne le sont pas. Nous verrons dans la partie II de ce livre que les
analyses sont très différentes selon que les paramètres sont additifs ou non.
Nous définissons formellement ci-dessous cette notion d’additivité, qui est
importante à reconnaître car elle permet souvent une étude générique ; voir par
exemple les sections 4.1.3 et 8.2.4 ou le chapitre 7.
39
Fig. 1.38 Un arbre binaire
de recherche à 7 clés
taille d’une « page ») n’est pas « développé », mais est réduit à une unique feuille
marquée par l’ensemble de toutes les clés de ce sous-arbre (c’est une notion qui
étend celle de trie paginé, définie en section 1.2.8). Alors le nombre de feuilles
d’un tel arbre est le nombre de sous-arbres de taille au plus b dans l’arbre initial.
– Pour un arbre de recherche (binaire ou non) τ , nous définissons d(α, τ ), la
profondeur d’insertion d’une clé α dans un arbre τ : c’est le niveau auquel se
trouve la clé α dans l’arbre obtenu après insertion de cette clé dans l’arbre τ ,
i.e., sa profondeur. Par exemple, dans l’arbre τ de la figure 1.38, la clé 8 doit
être insérée comme enfant gauche de 9, et aura donc une profondeur d’insertion
d(8, τ ) = 2, et la clé 5 comme enfant gauche de 6, avec une profondeur
d’insertion d(5, τ ) = 4.
Certains paramètres ne sont définis que sur les arbres planaires, pour lesquels
les sous-arbres d’un nœud donné sont naturellement ordonnés de gauche à droite.
Nous parlerons ainsi du j -ième sous-arbre d’un nœud (j étant un entier), ou de la
longueur de la branche droite dans un arbre τ : c’est la profondeur de la feuille la
plus à droite (bien sûr, on peut définir de même la longueur de la feuille la plus à
gauche, etc.) Lorsque l’arbre n’est pas planaire, les sous-arbres d’un nœud forment
un ensemble et la notion de j -ième sous-arbre comme celle de branche gauche ou
droite n’ont pas de sens.
1.3.2 Paramètres additifs
Les paramètres d’arbre ne sont pas tous de même nature ; certains comme la taille ou
la longueur de cheminement sont des paramètres additifs, c’est-à-dire une fonction
f (τ ) de l’arbre qui s’exprime additivement en fonction des sous-arbres enfants de
la racine. La taille, ou plus généralement le nombre de nœuds d’arité donnée d’un
arbre, sa longueur de cheminement, sont des paramètres additifs ; la hauteur ou le
niveau de saturation ne le sont pas. Nous verrons dans la partie II de ce livre que les
analyses sont très différentes selon que les paramètres sont additifs ou non.
Nous définissons formellement ci-dessous cette notion d’additivité, qui est
importante à reconnaître car elle permet souvent une étude générique ; voir par
exemple les sections 4.1.3 et 8.2.4 ou le chapitre 7.