Aller au contenu

Nom d'auteur dans un ABR⚓︎

Auteur : Sébastien Hoarau

D'après 2022, Asie, J2, Ex. 2

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

Exemple d'arbre binaire de recherche

L'arbre binaire A1 suivant est un arbre binaire de recherche : 

    %%{init: {'themeVariables': {'fontFamily': 'monospace'}}}%%
    flowchart TB
        n0(ELUARD) --> n1(ARAGON)
        n1 --> n3(APOLLINAIRE)
        n1 --> n4[Null]
        n0 --> n2(VOLTAIRE)

1.

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

Réponse 
    %%{init: {'themeVariables': {'fontFamily': 'monospace'}}}%%
    flowchart TB
        n0(ELUARD) --> n1(ARAGON)
        n1 --> n3(APOLLINAIRE)
        n1 --> n4(DUMAS)
        n0 --> n2(VOLTAIRE)
        n2 --> n5(HUGO)
        n2 --> n6(ZWEIG)
        n6 --> n7(ZOLA)
        n6 --> n8[Null]

1.b) Quelle est la taille de l'arbre obtenu ? Quelle est la hauteur de cet arbre ?

Réponse
  • Taille : 8
  • Hauteur : 4

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

Réponse

Si l'arbre est de hauteur \(h\) alors il y a \(2^h - 1\) auteurs au maximum.

Preuve

On montre d'abord que le nombre d'auteurs max au niveau \(n\) est \(2^{n-1}\). Immédiat par récurrence : au niveau 1, il n'y a qu'un auteur. La propriété est donc vraie. Si au niveau \(n\) on a \(2^{n-1}\) auteurs, alors, au niveau \(n+1\) on peut ajouter 2 auteurs pour chacun d'eux soit au total \(2\times 2^{n-1}\).

Un arbre complet de hauteur \(h\) a tous ses niveaux pleins et donc au total :

\[1 + 2 + ... + 2^{h-1}\]

Et 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.

Exemple

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

    %%{init: {'themeVariables': {'fontFamily': 'monospace'}}}%%
    flowchart TB
        n0(KAFKA) --> n1(DURAS)
        n0 --> n2(SAGAN)
        n2 --> n3[Null]
        n2 --> n4(SIMENON)
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 que cet arbre reste équilibré.

Réponse 
    %%{init: {'themeVariables': {'fontFamily': 'monospace'}}}%%
    flowchart TB
    n147(KAFKA) --> n148(DURAS)
    n147(KAFKA) --> n149(SAGAN)
    n148(DURAS) --> n150(BALZAC)
    n148(DURAS) --> n151(FLAUBERT)
    n150(BALZAC) --> n158(AUDIARD)
    n150(BALZAC) --> n159(COLETTE)

    n159(COLETTE) --> n166(CHRISTIE)

    n149(SAGAN) --> n152(PROUST)
    n149(SAGAN) --> n153(SIMENON)

    n153(SIMENON) --> n154(SAND)
    n153(SIMENON) --> n155(WOOLF)

3. L'éditeur souhaite utiliser une fonction récursive recherche_auteur 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 le début de cette fonction ci-dessous, recopier la et compléter la dernière ligne :

🐍 Script Python
def recherche_auteur(abr, nom):
    if est_vide(abr):
        return False
    elif valeur(abr) == nom:
        return True
    else:
        return ...

Une fois la fonction complétée, que renvoie l'appel recherche_auteur(A2, 'SIMENON') ? Justifier la réponse.

Réponse
🐍 Script Python
def recherche_auteur(abr, nom):
    if est_vide(abr):
        return False
    elif valeur(abr) == nom:
        return True
    else:
        return recherche_auteur(fils_gauche(abr), nom) or\
               recherche_auteur(fils_droit(abr), nom)

L'appel renvoie True. En effet, au premier appel, l'arbre n'est pas vide et la valeur de l'arbre ('KAFKA') n'est pas égale à la valeur recherchée. Il y a donc le premier appel récursif sur le sous-arbre gauche et la valeur 'SIMENON'. Cet appel va finir par renvoyer False (puisque 'SIMENON' n'est pas dans ce sous-arbre). Puisqu'on est sur l'évaluation d'un OU, le deuxième appel récursif est lancé, et finira par renvoyer True.

4. 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.

Écrire la fonction hauteur qui prend en entrée abr un arbre binaire de recherche et renvoie sa hauteur. On pourra avoir recours aux appels de fonctions prédéfinies min(val1, val2) et max(val1, val2) qui renvoient respectivement la plus petite et la plus grande valeur entre val1 et val2.

Réponse
🐍 Script Python
def hauteur(abr):
    if est_vide(abr):
        return 0
    else:
        return 1 + max(hauteur(fils_gauche(abr)), hauteur(fils_droit(abr)))