Aller au contenu

2022, Asie-Pacifique, jour 2 sujet 1, exercice 2⚓︎

Thème : arbres binaires de recherche

Un arbre binaire de recherche est un arbre 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 est 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 Aet 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 :

L'arbre A1

ABR A1

Remarque

Un rappel du vocabulaire et de quelques définitions. Le rappel de la hauteur est étrange : fait intervenir le concept de niveau qui n'a pas été défini.

Question 1a

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

Réponse

ABR 1a

Question 1b

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

Réponse

L'arbre obtenu a une taille de \(8\) pour une hauteur de \(4\).

Question 1c

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\) ?

Réponse

Si on appelle \(N(h)\) le nombre maximum de nœuds au niveau \(h\) on montre pas récurrence que \(N(h) = 2^{h-1}\). En effet la propriété est vraie pour \(h = 1\) puisque la racine est le seul nœeud on a bien \(N(1) = 1 = 2^0\). Supposons la propriété vraie pour un niveau \(h\). Si on passe au niveau \(h+1\), le nombre maximum de nœuds est atteint quand chaque nœud du niveau précédent possède 2 fils soit un total de \(2\times N(h)\) on a donc \(N(h+1) = 2\times 2^{h-1}\) et donc \(N(h+1) = 2^h\).

Pour un arbre de hauteur \(h\), le nombre maximum d'auteurs est atteint lorsque chaque niveau atteint son maximum de nœuds on a donc un total de \(1 + 2 + \ldots + 2^{h-1}\). Cette somme vaut \(2^h - 1\).

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.

Équilibre de l'arbre A2

Si on considère l'arbre suivant qu'on nommera A2:

ABR 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é.

Question 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é.

Réponse

ABR A2b

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
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)
Remarque

Plusieurs reproches ici :

  • confusion fonction et appel de fonction : 
    - une fonction récursive recherche_auteur(ABR, NOM)
+ une fonction récursive recherche_auteur
  • pourquoi ce pseudo code ?
  • pourquoi tout d'un coup Null est devenu NULL encore que là l'erreur est plutôt bien puisque NULL représente la constante arbre vide
  • les noms de variables (paramètres des fonctions) en majuscules, faisant fi du PEP8
  • t remplace NOM ?
  • enfin le réel point négatif est l'introduction de cette fonction mystere qui impJlémente une fonction de recherche mais sans exploiter le fait qu'on a des arbres binaires de recherche. Le lien avec recherche_auteur n'est pas établi.
Question 3

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

Réponse

Cet appel renvoie True puisque la clé 'SIMENON' fait partie de l'ABR A2. Au premier passage 'SIMENON' est comparé à 'KAFKA', comme il lui est différent, la fonction mystere est appelé sur le fils gauche et finira par renvoyer False, le OU évalue alors sa deuxième opérande et donc lance l'appel de la fonction mystere sur le fils droit. Ce deuxième appel renverra Truequi est aussi le résultat du OUet de l'appel initial.

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.

Question 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

Réponse

On donne la fonction en langage Python , en effet aucune raison de faire une espèce de pseudo code en français.

def hauteur(abr):
    if abr == NULL:
        return 0
    else:
        return 1 + max(hauteur(fils_gauche(abr)), hauteur(fils_droit(abr)))
Remarque

Ce sujet est plutôt raté : trop d'imprécisions à la fois sur le fond et la forme. Une fonction de recherche sur un ABR qui n'exploite pas la propriété des ABR ! Du pseudo-code qui n'apporte rien.