arbre td

7/21/2019 arbre td

http://slidepdf.com/reader/full/arbre-td 1/8

Université Paris Diderot – Paris 7 AlgorithmiqueL3 Informatique Année 2010-2011, 1er semestre

TD n◦

2

Arbres Binaire de Recherche

Le type de donné “arbre" sera utilisé pour indiquer l’ensemble de toutes les Arbres Binaires Étiquetés(ABEs) par des clés de type entier. La taille de un ABE a est par définition le nombre de clés contenuesdans a. Nous rappelons que un Arbres Binaire de Recherche (ABR) a est un ABE tel que tout nœudinterne b de a contient un clé– supérieure ou égale à toutes le clés contenues dans le sous-arbre gauche de b ;– inférieure strictement à toutes le clés contenues dans le sous-arbre droit de b.

Exercice 1 Est-ce que on peut utiliser la procédure suivante pour tester si un ABE a est un ABR?

Fonction estABR(a : arbre) : booléen1

début2

si (estVide(a)) alors3

retourner vrai;4

si (estVide(G(a))) alors5

gauche := clé(a);6

sinon7

gauche := clé(G(a));8

si (estVide(D(a))) alors9

droite := clé(a);10

sinon11

droite := clé(D(a));12

retourner (gauche ≤ clé(a) ≤ droite ∧ estABR(G(a)) ∧ estABR(D(a)));13

fin14

Sinon écrivez une fonction qui teste si un ABE a est un ABR.

Pour un tableau A[1, . . . , n] la définition de “k-ème élément" est très simple à comprendre et l’accès auk-ème élément est une opération élémentaire (c’est à dire, avec complexité Θ(1)). Au contraire un arbrebinaire n’est pas une structure linéaire et nous pouvons definire plusieur notions de “ k-ème élément",selon la facon dans laquelle nous parcourons l’arbre.

1

7/21/2019 arbre td


Étant donné un ABE quelconque on choisit la façon suivante de numéroter les nœuds de l’arbre :

Fig. 1 – Numérotation des nœuds d’un ABE

Exercice 2 [Accès au k-ème élément] Soit a un ABR.

Question 1. Proposez une méthode pour retourner le k-ème élément de a en utilisant :

– une procédure VisiteGRD(a : arbre) qui parcourt complètement l’arbre a.– un tableau d’entiers T .Quelle est la complexité de cette méthode en fonction de la taille de a ?

Question 2. En supposant d’avoir à disposition le type de donnée booléen × entier, proposez unefonction RecherchePos(a : arbre, k : entier) : booléen×entier telle que si (b, n) = RecherchePos(a, k)alors– si la taille de a est inférieure à k alors b = faux et n est la taille de a ;– si la taille de a n’est pas inférieure à k alors b = vrai et n est la valeur de la k-ème clé.Quelle est la complexité de cette méthode ?

Question 3. En supposant qu’on dispose d’une fonction taille(a : arbre) : entier calculant la tailled’un arbre a en Θ(1), proposez une fonction RecherchePos(a : arbre, k : entier) : arbre telle que si

b = RecherchePos(a, k) alors– si taille(a) < n, alors b = ArbreVide() ;– si taille(a) ≥ n, alors clé(b) est la k-ème clé dans l’arbre a.Évaluez la complexité de la procédure en fonction de la hauteur de l’arbre a.

Question 4. En acceptant de modifier légèrement la structure des ABRs, pouvez-vous proposer unefonction taille(a : arbre) : entier ayant complexité Θ(1) ? Vérifierez que votre modification ne changepas la complexité des fonctions d’insertion et de suppression d’un nœud dans un ABR.

Exercice 3 [Recherche du successeur] Modifiez légèrment la définition de ABR de telle sorte quetoutes les clés soyent distinctes. On appelle strict un ABR qui satisfait cette définition. Soit a un ABRstrict. Le successeur de un nœud x (s’il existe) est par définition le nœud y ayant la plus petit clé entrele clés plus grand que clé(x).

Question 1. Montrer rigoureusement que dans a :

(a) l’élément minimum se trouve à un nœud sans fils gauche.

(b) si un nœud a un fils droit, son successeur est le minimum de son sous arbre droit. En déduire quesi un nœud a un fils droit, alors son successeur n’a pas de fils gauche.

(c) si un nœud n’a pas de fils droit, son successeur, s’il existe, est le premier de ses ancètres dont le filsgauche est aussi l’un de ses ancètres.

Question 2. Écrire une fonction succ(b : arbre) : arbre qui retourne le sous arbre de a dont la racineest le successeur de b. Quelle est la complexité en temps de cet algorithme?

2

7/21/2019 arbre td


Exercice 4 Soit a un ABR strict, soient x un nœud feuille et y son parent. Montrer que clé(x) est soitla plus petite clé de a supérieure à clé(y), soit la plus grande clé de a inférieure à clé(y).

Exercice 5 On peut trier un tableau T de nombres entiers en commençant par construire par insertionssuccessives un ABR contenant ces nombres puis en effectuant un parcours infixe de l’arbre. Quels sontles temps d’exécution de cet algorithme en fonction de la taille de T dans le pire et dans le meilleur descas?

Exercice 6 [Insertion à la racine] Dans un arbre binaire de recherche, avec la méthode d’insertionclassique, toutes les nouvelles valeurs sont placées aux feuilles de l’arbre. Si l’on souhaite accéder à unnœud inséré récemment dans l’arbre, il faudra parcourir toute la hauteur de l’arbre. Dans certainesapplications, on souhaite accéder plus fréquemment aux derniers éléments insérés. Il s’agit du principeLRU

1. Dans ce cas particulier, il peut être intéressant d’insérer à la racine. En procédant de la sorte, lesvaleurs auxquelles on souhaite accéder le plus souvent ont plus de chance d’être à une faible profondeur.

En considérant l’exemple de la figure 2 :

Question 1. Tracez le chemin qui va de la racine au nœud où classiquement il faudrait insérer le nœud33.

Question 2. À partir des réponses aux questions précédentes, proposez une procédure insertionRacine(a :arbre, k : entier) d’insertion à la racine dans un ABR.

Évaluer la complexité de cet algorithme dans le pire des cas.

Fig. 2 – un arbre binaire de recherche

1pour Least Recently Used !

3

7/21/2019 arbre td


1 Solutions

Solution 1 L’algorithme n’est pas correct. Par exemple l’arbre (2 < −3− > 5) < −4− > 5 n’est pasun ABR. Un bon algorithme est, par exemple :

Fonction estABR(a : arbre) : booléen1

début2


retourner vrai;4


gauche := clé(a);6

sinon7

gauche := max(G(a));8

// calcule la clé maximum de l’arbre9

si (estVide(D(a))) alors10

droite := clé(a) + 1;11

sinon12

droite := min(D(a));13

// calcule la clé minimum de l’arbre14

retourner (gauche ≤ clé(a) < droite ∧ estABR(G(a)) ∧ estABR(D(a)));15

fin16

Solution 2

Réponse 1.

Fonction main(a : arbre, k : entier) : entier1

début2

i := 1;3

VisiteGRD(a);4

retourner T [k];5

fin6

Procédure VisiteGRD(a : arbre)1

début2

si (¬estVide(a)) alors3

VisiteGRD(G(a));4

T [i] := clé(a);5

i := i + 1;6

VisiteGRD(D(a));7

retourner;8

fin9

Cette méthode est en Θ(n).

Réponse 2.

4

7/21/2019 arbre td


Fonction RecherchePos(a : arbre, k : entier) : booléen× entier1

début2


retourner (faux, 0);4

(b, n) := RecherchePos(G(a), k);5

si (b = vrai) alors6

retourner (vrai, n);7

sinon8

si (k = n + 1) alors9

retourner (vrai,clé(a));10

sinon11

(b, n) := RecherchePos(D(a), k − n− 1);12

si (b = vrai) alors13

retourner (vrai, n);14

sinon15

retourner (faux, n + n + 1);16

fin17

La complexité de la fonction RecherchePos est Θ(k).

Réponse 3. On remarque qu’il est nécessaire de parcourir la branche gauche d’un arbre uniquement sik est supérieur au nombre de nœuds du fils-gauche. Une possibilité est donc de calculer préalablement lataille de fils gauche avant de décider si on effectue la recherche à gauche ou à droite.

Fonction RecherchePos(a : arbre, k : entier) : arbre1

début2

tailleFG := taille(G(a));3

tailleFD := taille(D(a));4

si (tailleFG + tailleF D + 1 < k) alors5

retourner arbreVide();6

// la position k n’est pas dans l’arbre7

si (tailleFG = k − 1) alors8

retourner a;9

// la position k est le noeud courant10

si (tailleFG < k) alors11

retourner RecherchePos(G(a), k);12

// la position k est dans le sous-arbre gauche13

sinon14

retourner RecherchePos(D(a), k − tailleFG − 1);15

// la position k est dans le sous-arbre droit16

fin17

Le nombre maximum d’appel récursif de la fonction RecherchePos étant h, la hauteur de l’arbre, onpourrait dire naïvement que la complexité dans le pire cas de cet algorithme est O(h). Ce n’est le cas quesi la fonction taille est en Θ(1).

Or, normalement une fonction taille pour les ABR est en Θ(n) (où n est la taille de l’arbre). Dans lecas où l’on recherche le prémier élément d’un arbre de taille n complètement déséquilibré à gauche, lacomplexité de la fonction RecherchePos est en réalité O(n2). Cela se vérifie par récursion sur la taille del’arbre.

5

7/21/2019 arbre td


Réponse 4. La seule manière d’obtenir une fonction taille en Θ(1) est de modifier la structure del’arbre pour que chaque nœud stocke sa taille.

Pour que cette information sur la taille reste cohérente, il faut modifier les fonction d’insertion et desuppression. Ces modifications peuvent être faites sans changer leur complexités respectives.– Lors de l’insertion il suffit de rajouter sur le chemin du nouveau nœud jusq’à la racine 1 à la taille de

chaque arbre. On peut aisément voir que lorsqu’on ajoute un nœud à un ABR, on augmente la taille de1 récursivement sur les sous-arbres concernés. Incrémenter O(h) compteurs, se fait en temps constantsur chaque nœud donc la complexité reste O(h).

– Concernant la suppression, en utilisant la méthode de suppression qui utilise le successeur, il fautdécrémenter de 1 la taille de tout les nœuds allant de la racine à l’ancienne position du successeur.La nouvelle taille de la racine est l’ancienne taille −1. Décrémenter O(h) compteur, se fait en tempsconstant sur chaque nœud donc la complexité rest O(h).

Solution 3 Un ABR strict a est un ABE tel que tout nœud interne b de a contient un clé– supérieure strictement à toutes le clés contenues dans le sous-arbre gauche de b ;– inférieure strictement à toutes le clés contenues dans le sous-arbre droit de b.

Réponse 5.(a) Soit un nœud x avec un fils gauche y, on a clé(y) < clé. Donc x ne contient pas la clé minimale.

Par contraposée, on en déduit que la clé minimale est située sur un nœud sans fils gauche.

(b) Soit un nœud x avec un fils droit. On note d’abord que succ(x) existe puisque D(x) a une cléplus grand que clé(x). Puis on montre que succ(x) est dans le sous arbre droit de x. C’est clairque succ(x) = x et que succ(x) n’est pas dans le sous arbre gauche de x. En effet, soit succ(x)un nœud que n’a pas pour ancètre x. Alors x et succ(x) ont un premier ancètre commun u = x.Si u = succ(x) alors forcement x,D(x) sont dans le sous arbre gauche de succ(x), mais alorsclé(x) < clé(D(x)) < clé(succ(x)) : ça est en contradiction avec l’hypothèse que succ(x) est lesuccesseur de x dans a. Donc forcement u = succ(x) et x est dans le sous arbre gauche de u etsucc(x) est dans le sous arbre droit de u. Mais alors clé(x) < clé(u) < clé(succ(x)) : ça est encontradiction avec l’hypothèse que succ(x) est le successeur de x dans a.

La seule possibilité est finalement que succ(x) soit dans le sous arbre droit de x. En plus, si succ(x)a un fils gauche, alors encore une fois on a clé(x) < clé(G(succ(x))) < clé(succ(x)) et ça n’est paspossible.

(c) On montre d’abord que, s’il existe, le succ(x) est un ancètre de x. C’est claire que succ(x) ne peutpas apparâitre dans un sous arbre de x et succ(x) = x. Don on a deux possibilités : succ(x) estun ancètre de x ou succ(x) et x ont un prémier ancètre commun u = succ(x). Dans le deuxièmecas on aurait que succ(x) est dans le sous arbre droit de u et x est dans le sous arbre gauche de u

(l’inverse n’est pas possible) et donc clé(x) < clé(u) < clé(succ(x)) : ça est en contradiction avecla définition de successeur de x.

Fonction min(a : arbre) : arbre1

début2


retourner a;4

retourner min(G(a));5

fin6

6

7/21/2019 arbre td


Fonction succ(a : arbre) : arbre1

début2

si (¬estVide(D(a))) alors3

retourner min(D(a));4

y := père(a);5

tant que (¬estVide(y) ∧ x = D(y)) faire6

x := y;7

y := père(y);8

retourner y;9

fin10

On effectue un simple parcours de l’arbre à partir du nœud x soit vers le bas, soit vers le haut,donc la complexité en temps est O(h). Si on veut calculer la complexité en fonction du nombre n

de clés, dans le meilleur des cas la complexité est O(lg n) et dans le pire des cas O(n).

Solution 4 Deux cas sont possibles :

Cas 1 : x est le fils droit de y. Comme les clés sont distinctes, on en déduit que clé(y) < clé(x).Considérons un noeud n quelconque différent de x et de y .Sous cas 1 : n est un ancètre de y . Ou bien y est dans le sous arbre droit de n, et alors x l’est aussi et

on en déduit que clé(n) < clé(y) < clé(x). Ou bien y est dans le sous arbre gauche de n, et alorsx l’est aussi et on en déduit que clé(y) < clé(x) < clé(n).

Sous cas 2 : y est un ancètre de n. Comme x est une feuille et est le fils droit de y, n est dans le sousarbre gauche de y et donc clé(n) < clé(y) < clé(x).

Sous cas 3 : n n’est pas un ancètre de y et y n’est pas un ancètre de n.n et y ont un premier ancètre commun n. Nécessairement, n = y et n = n donc x et n sont dansles sous-arbres de n. Ses deux sous-arbres sont différents car n est le premier ancètre commun :ou bien y et x sont dans le sous arbre droit de n et n est dans le sous arbre gauche de n, et alorsclé(n) < clé(y) < clé(x), ou bien y et x sont dans le sous arbre gauche de n et n est dans le sous

arbre droit de n

, et alors cl

é(y

) < cl

é(x

) < cl

é(n

).Donc pour tout noeud n différent de x et de y, on a clé(n) < clé(y) < clé(x) ou clé(y) < clé(x) <

clé(n), on peut donc conclure que clé(x) est la plus petite clé de l’arbre supérieure à clé(y).Cas 2 : x est le fils gauche de y et en menant un raisonnement semblable, on montre que clé(x) est la

plus grande clé de l’arbre inférieure à clé(y).

Solution 5 Remarquons d’abord que la complexité du parcours infixe évolue en Θ(n).

Pour la construction de l’ABR, dans le meilleur des cas, après chaque insertion, l’arbre est équilibrédonc la complexité de l’insertion est O(lg k) où k est le nombre de valeurs déjà insérées. Donc la construc-tion de l’ABR évolue en O(Σn

k=1 lg k).

Or Σn

k=1 lg k = lg(n!) et d’après la formule de Stirling

n! =√

2πn

n

e

n

(1 + Θ(n−1))

donclg(n!) =

1

2 lg(2πn) + n lg n− n lg(e) + Θ(n−1)

On en déduit que la complexité du tri dans le meilleur des cas évolue en O(n lg n).

Dans le pire des cas, après chaque insertion, l’arbre est complètement déséquilibré donc la complexitéde l’insertion est O(k) où k est le nombre de valeurs insérées. Donc la construction de l’ABR évolue enO(Σn

k=1k) = O(n2). Dans le pire des cas, la complexité du tri évolue en O(n2).

7

7/21/2019 arbre td


Solution 6

Réponse 6. 100, 1, 40, 30, 32, 34, 33.

Réponse 7.

Fonction rotationGauche(a : arbre)1

début2

b := D(a);3

D(a) := G(b);4

G(b) := a;5

retourner b;6

fin7

Fonction rotationDroite(a : arbre)1

début2

b := G(a);3

G(a) := D(b);4

D(b) := a;5

retourner b;6

fin7

Procédure insertionRacine(a : arbre, k : entier)1

début2


a := nouvArbre(k, arbreVide(),arbreVide());4

// crée un nouveau arbre avec clé k5

retourner ;6

si (k < clé(a)) alors7

G(a) := insertionRacine(G(a), k);8

a := rotationDroit(a);9

sinon10

D(a) := insertionRacine(D(a), k);11

a := rotationGauche(a);12

retourner ;13

fin14

Dans le pire cas on appel récursivement la fonction insertionRacine h fois, où h est la hauteur dea. Le fonctions rotationDroite et rotationGauche ont complexité Θ(1) et donc la complexité deinsertionRacine est O(h) (O(lg n)).

8

Documents

arbre td