2.2 Aléa sur les arbres marqués
47
qui entraîne l’uniformité du réordonnement. Ainsi dans ce modèle, seuls les rangs,
l’ordre des données comptent, pas leur valeur.
La proposition 2.4 justifie le fait que, dans les sections suivantes, ce sera l’arbre des
rangs C(τ ) qui sera étudié au lieu de τ .
Remarque 2.5 Il peut arriver que nous ayons besoin de travailler directement sur les
permutations de taille donnée n, et de les supposer tirées uniformément dans S n ;
c’est cette situation qui mérite réellement le nom de « modèle des permutations
uniformes ». Nous utiliserons ce modèle au chapitre 3 lorsque nous évoquerons
l’analyse d’algorithmes de tri par comparaison ; cf. la définition 3.6.
2.2.2 Aléa sur les tas
Nous supposons ici que les clés sont toutes distinctes ; de sorte que le marquage
canonique (définition 1.16) permet de se ramener à l’ensemble {1, . . . , n} pour un
tas de taille n. L’ensemble des (arbres des rangs pour les) tas de taille donnée est
donc fini.
Il y a deux manières d’envisager l’aléa sur les tas :
– soit l’aléa porte sur l’ensemble des tas eux-mêmes : nous avons une loi de
probabilité sur l’ensemble des tas de taille donnée (par exemple la loi uniforme,
mais pas seulement) ; cette approche est analogue à celle de la section 2.1.1 pour
le modèle de Catalan ;
– soit l’aléa porte sur les entrées de l’algorithme utilisé pour construire un
tas. En d’autres termes, l’aléa porte sur la suite initiale des n clés. Nous
supposerons dans ce cas travailler sous le modèle des permutations uniformes
(cf. la définition 2.4 et la remarque 2.5 dans la section précédente), ce qui permet
de se ramener à une permutation de S n . Nous construisons alors un tas à partir
de cette permutation, et la question est de savoir quelle est la distribution induite
sur l’ensemble des tas de taille n. Cette approche est analogue à celle que nous
adopterons ci-après pour les arbres binaires de recherche, cf. la section 2.2.3.
Dans le cas où l’aléa porte sur la suite de clés à partir de laquelle un tas est
construit, la distribution induite sur l’ensemble des tas peut évidemment dépendre
de l’algorithme retenu pour la construction ; nous donnons à l’annexe A.6.3 deux
algorithmes classiques, dus respectivement à Floyd et à Williams. La différence
entre ces deux algorithmes est analogue à celle entre deux points de vue déjà
rencontrés lors de la présentation des arbres binaires de recherche (cf. section 1.2.5) :
l’ensemble des clés peut être connu dès le départ, et nous avons alors une
construction « statique », ou les clés peuvent être insérées au fur et à mesure de
leur arrivée, c’est une construction « dynamique ». Une différence essentielle est
cependant que les deux algorithmes conduisent à des distributions de probabilité
différentes sur l’ensemble des tas (cf. la figure 2.4).
47
qui entraîne l’uniformité du réordonnement. Ainsi dans ce modèle, seuls les rangs,
l’ordre des données comptent, pas leur valeur.
La proposition 2.4 justifie le fait que, dans les sections suivantes, ce sera l’arbre des
rangs C(τ ) qui sera étudié au lieu de τ .
Remarque 2.5 Il peut arriver que nous ayons besoin de travailler directement sur les
permutations de taille donnée n, et de les supposer tirées uniformément dans S n ;
c’est cette situation qui mérite réellement le nom de « modèle des permutations
uniformes ». Nous utiliserons ce modèle au chapitre 3 lorsque nous évoquerons
l’analyse d’algorithmes de tri par comparaison ; cf. la définition 3.6.
2.2.2 Aléa sur les tas
Nous supposons ici que les clés sont toutes distinctes ; de sorte que le marquage
canonique (définition 1.16) permet de se ramener à l’ensemble {1, . . . , n} pour un
tas de taille n. L’ensemble des (arbres des rangs pour les) tas de taille donnée est
donc fini.
Il y a deux manières d’envisager l’aléa sur les tas :
– soit l’aléa porte sur l’ensemble des tas eux-mêmes : nous avons une loi de
probabilité sur l’ensemble des tas de taille donnée (par exemple la loi uniforme,
mais pas seulement) ; cette approche est analogue à celle de la section 2.1.1 pour
le modèle de Catalan ;
– soit l’aléa porte sur les entrées de l’algorithme utilisé pour construire un
tas. En d’autres termes, l’aléa porte sur la suite initiale des n clés. Nous
supposerons dans ce cas travailler sous le modèle des permutations uniformes
(cf. la définition 2.4 et la remarque 2.5 dans la section précédente), ce qui permet
de se ramener à une permutation de S n . Nous construisons alors un tas à partir
de cette permutation, et la question est de savoir quelle est la distribution induite
sur l’ensemble des tas de taille n. Cette approche est analogue à celle que nous
adopterons ci-après pour les arbres binaires de recherche, cf. la section 2.2.3.
Dans le cas où l’aléa porte sur la suite de clés à partir de laquelle un tas est
construit, la distribution induite sur l’ensemble des tas peut évidemment dépendre
de l’algorithme retenu pour la construction ; nous donnons à l’annexe A.6.3 deux
algorithmes classiques, dus respectivement à Floyd et à Williams. La différence
entre ces deux algorithmes est analogue à celle entre deux points de vue déjà
rencontrés lors de la présentation des arbres binaires de recherche (cf. section 1.2.5) :
l’ensemble des clés peut être connu dès le départ, et nous avons alors une
construction « statique », ou les clés peuvent être insérées au fur et à mesure de
leur arrivée, c’est une construction « dynamique ». Une différence essentielle est
cependant que les deux algorithmes conduisent à des distributions de probabilité
différentes sur l’ensemble des tas (cf. la figure 2.4).