Exercice 2 · Bac Numérique et Sciences Informatiques Asie 2022 (jour 2)

EXERCICE 2 (4 points)

Thèmes abordés: arbres binaires de recherche.

Un arbre binaire de recherche est un arbre binaire pour lequel chaque nœud possède une étiquette dont la valeur est supérieure ou égale à toutes les étiquettes des nœuds de son fils gauche et strictement inférieure à celles des nœuds de son fils droit. On rappelle que:

sa taille est son nombre de nœuds;

sa hauteur est le nombre de niveaux qu'il contient.

Un éditeur réédite des ouvrages. Il doit gérer un nombre important d'auteurs de la littérature. Pour stocker le nom des auteurs, il utilise un programme informatique qui les enregistre dans un arbre binaire de recherche.

L'arbre vide sera noté Null pour les algorithmes de cet exercice.

Si A est un nœud non vide, valeur(A) renvoie le nom de l'auteur; fils_gauche(A) renvoie le fils gauche du nœud A et fils_droit(A) renvoie le fils droit du nœud A.

L'ordre alphabétique est utilisé pour classer le nom des auteurs.

Par exemple, on a APOLLINAIRE < BAUDELAIRE

Ainsi, pour tout nœud A, si fils_gauche(A) et fils_droit(A) ne sont pas Null, on a:

valeur(fils_gauche(A)) ≤ valeur(A) < valeur(fils_droit(A))

Par exemple, l'arbre binaire suivant A1 est un arbre binaire de recherche:

1.

a.

Recopier et compléter l'arbre binaire de recherche précédent en insérant successivement dans cet ordre les noms suivants:

DUMAS; HUGO; ZWEIG; ZOLA

b.

Quelle est la taille de l'arbre obtenu ? Quelle est la hauteur de cet arbre ?

c.

Plus généralement, si l'arbre est de hauteur $h$, quel est le nombre maximal d'auteurs enregistrés dans cet arbre en fonction de $h$ ?

On définit ici l'équilibre d'un arbre binaire: il s'agit d'un nombre entier positif ou négatif. Il vaut 0 si l'arbre est vide. Sinon il vaut la différence des hauteurs des sous-arbres gauche et droit de l'arbre.

Par exemple, si on considère l'arbre suivant que l'on nommera A2:

Son équilibre vaut -1 car la hauteur de son sous-arbre gauche vaut 1, la hauteur de son sous-arbre droit vaut 2 et $1 - 2 = -1$.

Un arbre est dit équilibré si son équilibre vaut -1, 0 ou 1.

L'arbre précédent est donc équilibré.

2.

Recopier et compléter l'arbre de ce dernier exemple avec les noms

FLAUBERT, BALZAC, PROUST, SAND, WOOLF, COLETTE, CHRISTIE et AUDIARD

quitte à modifier l'ordre d'insertion de manière à ce que cet arbre reste équilibré.

L'éditeur souhaite utiliser une fonction récursive recherche_auteur(ABR, NOM) qui prend en paramètres ABR un arbre binaire de recherche et NOM un nom d'auteur. La fonction renvoie TRUE si NOM est une étiquette de l'arbre ABR et FALSE dans le cas contraire.

On donne la fonction suivante:

Fonction mystere(ABR, t):

SI ABR = NULL:

RENVOYER FAUX

SINON SI valeur(ABR) = t:

RENVOYER VRAI

SINON:

RENVOYER mystere(fils_gauche(ABR), t) OU mystere(fils_droit(ABR), t)

3.

Que renvoie l'appel mystere(A2, 'SIMENON') ? Justifier la réponse.

L'éditeur souhaite utiliser une fonction récursive hauteur(ABR) qui prend en paramètre un arbre binaire ABR et renvoie la hauteur de cet arbre.

4.

Écrire un algorithme de la fonction hauteur(ABR) qui prend en entrée ABR un arbre binaire de recherche et renvoie sa hauteur. On pourra avoir recours aux fonctions MIN(val1, val2) et MAX(val1, val2) qui renvoient respectivement la plus petite et la plus grande valeur entre val1 et val2.