1.2 Arbres marqués
21
Fig. 1.18 Un arbre saturé de hauteur 3
Fig. 1.19 Deux exemples de tas de taille 9 sur les données {1, . . . , 9}
Les nœuds internes d’un arbre parfait ont tous deux enfants, sauf éventuellement,
lorsque la taille de l’arbre est paire, le dernier nœud interne de l’avant-dernier
niveau. Les feuilles d’un tel arbre sont sur les deux derniers niveaux (un seul s’il
est saturé). Comme pour un arbre saturé, la hauteur h d’un arbre binaire parfait est
totalement déterminée par sa taille n (la démonstration n’est pas plus détaillée) :
h = =log 2 (n + 1) − 1,
(1.7)
où désigne l’entier immédiatement supérieur ou égal à x.
Définition 1.27 Un tas est un arbre binaire parfait et croissant (figure 1.19). 9
Il est clair que la forme d’un tas est déterminée uniquement par sa taille, et que
deux tas de même taille construits sur le même ensemble de clés ne diffèrent que
par le marquage des nœuds. Par ailleurs, il est bien sûr possible d’obtenir un arbre
des rangs par marquage canonique d’un tas τ , en renumérotant ses marques de 1
à |τ | si elles sont toutes distinctes, et de 1 au nombre de marques distinctes sinon.
Mentionnons enfin que la marque de la racine est toujours une clé minimale ; cette
propriété est à la base de l’utilisation algorithmique des tas pour implémenter des
files de priorité.
9 Certains auteurs définissent un tas comme un arbre décroissant, i.e., chaque nœud a une marque
supérieures à celles de ses enfants, et la plus grande marque est à la racine de l’arbre. Ceci est bien
évidemment équivalent à notre définition : les analyses sont inchangées, et il suffit de renverser les
inégalités pour obtenir les algorithmes adéquats.
21
Fig. 1.18 Un arbre saturé de hauteur 3
Fig. 1.19 Deux exemples de tas de taille 9 sur les données {1, . . . , 9}
Les nœuds internes d’un arbre parfait ont tous deux enfants, sauf éventuellement,
lorsque la taille de l’arbre est paire, le dernier nœud interne de l’avant-dernier
niveau. Les feuilles d’un tel arbre sont sur les deux derniers niveaux (un seul s’il
est saturé). Comme pour un arbre saturé, la hauteur h d’un arbre binaire parfait est
totalement déterminée par sa taille n (la démonstration n’est pas plus détaillée) :
h = =log 2 (n + 1) − 1,
(1.7)
où désigne l’entier immédiatement supérieur ou égal à x.
Définition 1.27 Un tas est un arbre binaire parfait et croissant (figure 1.19). 9
Il est clair que la forme d’un tas est déterminée uniquement par sa taille, et que
deux tas de même taille construits sur le même ensemble de clés ne diffèrent que
par le marquage des nœuds. Par ailleurs, il est bien sûr possible d’obtenir un arbre
des rangs par marquage canonique d’un tas τ , en renumérotant ses marques de 1
à |τ | si elles sont toutes distinctes, et de 1 au nombre de marques distinctes sinon.
Mentionnons enfin que la marque de la racine est toujours une clé minimale ; cette
propriété est à la base de l’utilisation algorithmique des tas pour implémenter des
files de priorité.
9 Certains auteurs définissent un tas comme un arbre décroissant, i.e., chaque nœud a une marque
supérieures à celles de ses enfants, et la plus grande marque est à la racine de l’arbre. Ceci est bien
évidemment équivalent à notre définition : les analyses sont inchangées, et il suffit de renverser les
inégalités pour obtenir les algorithmes adéquats.