440
A Rappels algorithmiques
Fonction chercherRapide(tableau T, entier gauche, entier
droite, entier r)
// Précondition : Pour tout j , 1 ≤ j ≤ n, T[j] < T[n+1].
// Postcondition : Retourne le tableau T, qui a été partiellement réordonné ;
l’élément de rang r se trouve maintenant en T[r].
// Utilise : partition, chercherRapide
// Variable locale : entier k
si gauche < droite alors
k, T = partition(T, gauche, droite)
si k > r alors
T = chercherRapide(T, gauche, k - 1, r)
sinon
si k < r alors
T = chercherRapide(T, k + 1, droite, r)
retourner T
A.6.3 Tas
Implémentation d’un arbre parfait dans un tableau
La numérotation en ordre hiérarchique des nœuds des tas (ou plus exactement,
des arbres parfaits) joue un rôle essentiel dans leur implémentation, puisqu’elle
permet de s’affranchir de la représentation classique des arbres binaires donnée en
section A.1.1 et de les représenter dans un tableau. En effet, le nœud qui a pour rang
en ordre hiérarchique i a pour père le nœud de rang i/2 (sauf si i = 1 : dans ce
cas il s’agit de la racine de l’arbre), et pour fils droit et gauche, les nœuds de rangs
respectifs 2i et 2i + 1. Nous pouvons ainsi naviguer dans l’arbre, et retrouver les
feuilles : ce sont les nœuds de rang i tel que 2i > n, auxquels s’ajoute, lorsque la
taille n du tas est paire, l’unique nœud simple qui a pour rang
n
2 .
Nous donnons en figure A.25 un exemple d’arbre parfait marqué et de sa
représentation dans un tableau, en suivant l’ordre hiérarchique.
Fig. A.25 Un arbre parfait marqué et le tableau le représentant
A Rappels algorithmiques
Fonction chercherRapide(tableau T, entier gauche, entier
droite, entier r)
// Précondition : Pour tout j , 1 ≤ j ≤ n, T[j] < T[n+1].
// Postcondition : Retourne le tableau T, qui a été partiellement réordonné ;
l’élément de rang r se trouve maintenant en T[r].
// Utilise : partition, chercherRapide
// Variable locale : entier k
si gauche < droite alors
k, T = partition(T, gauche, droite)
si k > r alors
T = chercherRapide(T, gauche, k - 1, r)
sinon
si k < r alors
T = chercherRapide(T, k + 1, droite, r)
retourner T
A.6.3 Tas
Implémentation d’un arbre parfait dans un tableau
La numérotation en ordre hiérarchique des nœuds des tas (ou plus exactement,
des arbres parfaits) joue un rôle essentiel dans leur implémentation, puisqu’elle
permet de s’affranchir de la représentation classique des arbres binaires donnée en
section A.1.1 et de les représenter dans un tableau. En effet, le nœud qui a pour rang
en ordre hiérarchique i a pour père le nœud de rang i/2 (sauf si i = 1 : dans ce
cas il s’agit de la racine de l’arbre), et pour fils droit et gauche, les nœuds de rangs
respectifs 2i et 2i + 1. Nous pouvons ainsi naviguer dans l’arbre, et retrouver les
feuilles : ce sont les nœuds de rang i tel que 2i > n, auxquels s’ajoute, lorsque la
taille n du tas est paire, l’unique nœud simple qui a pour rang
n
2 .
Nous donnons en figure A.25 un exemple d’arbre parfait marqué et de sa
représentation dans un tableau, en suivant l’ordre hiérarchique.
Fig. A.25 Un arbre parfait marqué et le tableau le représentant