Parcours d’un arbre binaire

2. l’ordre postfixe : on liste chaque sommet la dernière fois qu’on le rencontre. Ce qui donne ici : . . .

3. l’ordre infixe : on liste chaque sommet ayant un fils gauche la seconde fois qu’on le voit et chaque

sommet sans fils gauche la première fois qu’on le voit. Ce qui donne ici : . . .

(cid:7)

Une résolution

(cid:6)

(cid:4)

(cid:5)

1. ordre préfixe : r, a, c, h, d , i , j , (cid:96), b, e, k, f .

2. ordre postfixe : h, c, i , (cid:96), j , d , a, k, e, f , b, r .

3. ordre infixe : c, h, a, i , d , (cid:96), j , r, k, e, b, f .

1.2 Seconde définition des trois parcours

Dans la balade schématisée plus haut, on ajoute les fils fantômes manquants :

r

a

b

c

d

e

f

h

i

j

k

(cid:96)

On peut ainsi considérer qu’on passe une fois à gauche de chaque noeud (en descendant), une fois en-

dessous de chaque noeud, une fois à droite de chaque noeud (en remontant).

Vérifier, sur l’exemple, que chacun des ordres préfixe, infixe, postfixe est obtenu en listant tous les mots :

– soit lorsqu’on passe à leur gauche,

– soit lorsqu’on passe à leur droite,

– soit lorsqu’on passe en-dessous.

(cid:7)

Une résolution

(cid:6)

(cid:4)

(cid:5)

1. A gauche : préfixe.

2

IREM DE LYON

2. A droite : postfixe.

3. En-dessous : infixe.

2 Algorithmes récursifs

Pour chacun des parcours définis ci-dessus (postfixe, infixe, préfixe), définir récursivement le parcours.

(cid:7)

Une résolution

(cid:6)

(cid:4)

(cid:5)

1. Parcours préfixe.

Pseudo-code

ParcoursPréfixe ( Arbre binaire T de racine r )

c l e f [ r ]

A f f i c h e r

ParcoursPréfixe ( Arbre de racine f i l s _ g a u c h e [ r ] )

ParcoursPréfixe ( Arbre de racine f i l s _ d r o i t [ r ] )

2. Parcours postfixe.

Pseudo-code

ParcoursPostfixe ( Arbre binaire T de racine r )

ParcoursPostfixe ( Arbre de racine f i l s _ g a u c h e [ r ] )

ParcoursPostfixe ( Arbre de racine f i l s _ d r o i t [ r ] )

A f f i c h e r

c l e f [ r ]

3. Parcours infixe.

Pseudo-code

ParcoursInfixe ( Arbre binaire T de racine r )

ParcoursInfixe ( Arbre de racine f i l s _ g a u c h e [ r ] )

A f f i c h e r

ParcoursInfixe ( Arbre de racine f i l s _ d r o i t [ r ] )

c l e f [ r ]

3 Représentation en machine

Chaque nœud de l’arbre T est representé par un objet ayant un champ clef (des valeurs à trier par

exemple), un champ père, un champ fils_gauche, un champ fils_droit (stockent des pointeurs).

Lorsque père[x]=NIL, x est la racine de l’arbre. Lorsque x n’a pas de fils gauche, fils_gauche[x]=NIL

(idem pour fils_droit). La racine de l’arbre T est pointée par l’attribut racine[T]. Lorsque racine[T]=NIL,

l’arbre est vide.

3

IREM DE LYON

4 Complexité d’un parcours infixe

Vérifier qu’avec n noeuds, le parcours infixe

Pseudo-code

Parcours_Infixe ( arbre binaire T de racine x )

Si x d i s t i n c t de NIL * temps constant T( 0 ) =c pour un sous−arbre vide

alors

Parcours_Infixe ( arbre de racine f i l s _ g a u c h e [ x ] )

A f f i c h e r c l e f [ x ]

Parcours_Infixe ( arbre de racine f i l s _ d r o i t [ x ] )

FinSi

• temps T(n−k−1)

• temps constant d

• temps T( k )

prend un temps en Θ(n) (établir avec les notations suggérées ci-dessus : T (n) = (c + d )n + c)

(cid:7)

Une résolution

(cid:6)

Amorce : T (0) = c = (c + d ) × 0 + c.

Hérédité :

(cid:4)

(cid:5)

T (n) = T (k) + T (n − k − 1) + d

= [(c + d )k + c] + [(c + d )(n − k − 1) + c] + d

= (c + d )n + c − (c + d ) + c + d

= (c + d )n + c

5 La notation polonaise inverse

Écrire les sommets de l’arbre ci-dessous pour chacun des ordres postfixe, préfixe, infixe :

÷

×

+

+

−

e

f

a

b

c

d

Pour le parcours infixe, on ajoute la convention suivante : on ajoute une parenthèse ouvrante à chaque

fois qu’on entre dans un sous-arbre et on ajoute une parenthèse fermante lorsqu’on quitte ce sous-

arbre.

4

IREM DE LYON

(cid:7)

Une résolution

(cid:6)

(cid:4)

(cid:5)

1. Préfixe (notation polonaise) : ÷, ×, +, a, b, −, c, d , +, e, f .

2. Postfixe (polonaise inverse) : a, b, +, c, d , −, ×, e, f , +, ÷.

3. Infixe : a, +, b, ×, c, −, d , ÷, e, +, f .

Avec un ajout de parenthèses (ouvrante en rencontrant le nœud racine du sous arbre pour la pre-

mière fois et fermante lorsqu’on le rencontre pour la dernière fois, avec exception sur les sous-

arbres constitués d’une feuille) : (cid:161)(a + b) × (c − d )(cid:162) ÷ (e + f ).

L’infixe nécessite cette convention pour lever les ambiguïtés, les deux autres non. La préfixe consiste à

voir les opérateurs comme des fonctions de deux variables :

÷, ×, +, a, b, −, c, d , +, e, f = ÷

(cid:179)

× [+(a, b), −(c, d )] , +(e, f )

(cid:180)

Idem avec la postfixe mais avec la fonction écrite sur la droite.

6 Le tri du bijoutier

On dispose d’une liste de nombres. Par exemple, la liste 7, 9, 3, 5, 4, 1, 8. On associe à chaque élément n

de la liste un nœud v (initialisation : père[v]=NIL, fils_gauche[v]=NIL, fils_droit[v]=NIL, clef[v]=n).

Pseudo-code

Arbre_Insérer ( Arbre T , noeud z )

y : = NIL

x : = racine [T]

TantQue x d i s t i n c t de NIL f a i r e

y : = x

Si c l e f [ z ] < c l e f [ x ]

alors x : = f i l s _ g a u c h e [ x ]

sinon x : = f i l s _ d r o i t [ x ]

FinSi

FinTantQue

père [ z ] : = y

Si y=NIL

alors racine [T ] : = z

sinon

Si c l e f [ z ] < c l e f [ y ]

alors f i l s _ g a u c h e [ y ] : = z

sinon f i l s _ d r o i t [ y ] : = z

FinSi

FinSi

5

IREM DE LYON

1. Dresser l’arbre obtenu en appliquant l’algorithme Arbre_Insérer aux éléments de la liste (dans

l’ordre de la liste) en partant d’un arbre vide pour le premier élément, chaque appel à l’algorithme

modifiant l’arbre.

2. L’un des parcours postfixe, infixe, préfixe de la liste trie la liste. Lequel ?

3. Dans la construction de l’arbre pour une liste de n nombres, quel est le nombre de comparaisons

effectuées dans le pire des cas ?

4. Quel est le nombre de comparaisons effectuées si l’arbre final est un arbre binaire complet (arbre

binaire dans lequel tout nœud autre qu’une feuille a deux fils et dans lequel les feuilles sont tous

des nœuds de même profondeur).

(cid:7)

Une résolution

(cid:6)

(cid:4)

(cid:5)

1. L’arbre obtenu :

7

3

9

1

5

8

4

2. Le parcours infixe trie la liste. Les éléments de gauche sont en effet par construction plus petits

qu’un noeud et sont affichés avant le nœud dans l’ordre infixe et les éléments de droite qui sont,

par construction, plus grands sont affichés dans l’ordre infixe après le nœud. Par "récurrence", on

a donc un affichage des éléments de la liste dans l’ordre.

On peut donner une version graphique de ce parcours en projetant verticalement les nœuds sur

une droite horizontale (à dessiner sous l’arbre).

3. Le pire des cas correspond aux cas où la liste est triée (ordre croissant ou décroissant). Le nombre

de comparaisons à effectuer est alors de 1 + 2 + · · · + (n − 1) = 1

2 n(n − 1).

4. Pour ajouter un noeud au niveau de profondeur p (la racine étant au niveau de profondeur 0), on

effectue p comparaisons. Si la profondeur est h, on aura effectué une comparaison pour chacun

des deux noeuds de profondeur 1 (2 × 1), deux comparaisons pour chacun des 22 noeuds de pro-

fondeur 2 ( total 21 + 2 × 22), tros comparaisons pour chacun des 23 noeuds de profondeur 3 (total

21 + 2 × 22 + 3 × 23) . . .

Le nombre de comparaisons pour une profondeur h est (preuve facile par récurrence) :

j × 2 j = (h − 1) × 2h+1 + 2

h

(cid:88)

j =1

6

IREM DE LYON

Avec n noeuds (c’est à dire n nombres à trier), on a 1 + 2 + 22 + · · · + 2h = 2h+1 − 1 et

h

(cid:88)

j =1

j × 2 j = (h − 1) × 2h+1 + 2 = (log2(n + 1) − 1) × (n + 1) + 2

On a donc un cas optimal en O(n log(n)) et on peut montrer (comme pour le quick sort) que

la hauteur moyenne d’un arbre binaire de recherche construit aléatoirement à partir de n clefs

est O(log(n)) (référence : introduction à l’algorithmique, Cormen, Leiserson,Rivest, Stein, éditions

Dunod, 2002, page 258, paragraphe 12.4).

Les caractéristiques de temps sont les mêmes que pour le quick sort, mais avec un avantage du

côté des caractéristiques d’espace pour le quick sort (on trie le tableau sur place pour le quick sort,

on crée un arbre de recherche pour le tri du bijoutier).

7 Références

1. Introduction à l’algorithmique. Auteurs : Cormen, Leiserson, Rivest, Stein. Edition française : Du-

nod 2002.

Plus de 1100 pages sur les algorithmes et les structures de référence. Le chapitre 12 concerne les

arbres binaires de recherche.

2. Un article de Jean-Claude Oriol sur le site de l’apmep avec un passage sur le tri du bijoutier :

http://www.apmep.asso.fr/spip.php?article3405

3. Le cours de Pierre Audibert (Paris 8) en ligne :

http://www.ai.univ-paris8.fr/~audibert/ens/06-ARBREBINX.pdf

7