Aller au contenu

2022, Polynésie, sujet 1, exercice 5⚓︎

Thème : Algorithmique et principalement algorithmes sur les arbres binaires

Remarque

Ce sujet est beaucoup plus long que la moyenne des sujets sur les arbres.

On manipule ici les arbres binaires avec trois fonctions :

  • est_vide(A) qui renvoie True si l'arbre binaire A est vide, False s'il ne l'est pas ;
  • sous_arbre_gauche(A) qui renvoie le sous-arbre gauche de l'arbre binaire A ;
  • sous_arbre_droit(A) qui renvoie le sous-arbre droit de l'arbre binaire A.

L'arbre binaire renvoyé par les fonctions sous_arbre_gauche et sous_arbre_droit peut éventuellement est l'arbre vide.

On définit la hauteur d'un arbre binaire non vide de la façon suivante :

  • si ses sous-arbres gauche et droit sont vides, sa hauteur est 0 ;
  • si l'un des deux au moins est non vide, alors sa hauteur est égale à \(1 + M\)\(M\) est la plus grande des hauteurs de ses sous-arbres (gauche et droit) non vides.
Remarque

Voilà une définition bien compliquée. Pourquoi pas simplement :

  • Si \(A\) est l'arbre vide alors sa hauteur est \(-1\) ;
  • sinon la hauteur est égale à \(1 + M\)\(M\) est la plus grande des hauteurs des sous-arbres (gauche et droit).

À noter que cette définition n'est pas la plus courante. Elle revient à compter les nombre d’arêtes du plus long chemin de la racine à une feuille. Pour un élève la hauteur de \(-1\) pour l'arbre vide peut être perturbant.

Question 1a

Donner la hauteur de l'arbre ci-dessous :

arbre 1a

Réponse

Avec la définition donnée, la hauteur de cet arbre est 2.

Question 1b

Dessiner sur la copie un arbre binaire de hauteur 4.

Réponse

arbre 1b

La hauteur d'un arbre est calculée par l'algorithme récursif suivant :

Algorithme de la hauteur (à compléter)
Algorithme hauteur(A):
    test d'assertion : A est supposé non vide
    si sous_arbre_gauche(A) vide et sous_arbre_droit(A) vide:
        renvoyer 0
    sinon, si sous_arbre_gauche(A) vide:
        renvoyer 1 + hauteur(sous_arbre_droit(A))
    sinon, si ... :
        renvoyer ...
    sinon
        renvoyer 1 + max(hauteur(sous_arbre_gauche(A)), hauteur(sous_arbre_droit(A)))
Question 2

Recopier sur la copie les lignes 7 et 8 en complétant les points de suspension.

Remarque

Beaucoup de questionnement sur cette deuxième question :

  • Pourquoi prendre la peine de définir l'arbre binaire vide si ce n'est pas pour l'utiliser ensuite ?
  • Pourquoi mettre en place la fonction est_vide mais ne pas l'utiliser ensuite ?
  • Pourquoi ne pas utiliser la syntaxe Python, plutôt que ce pseudo langage ?

Voilà ce qu'il aurait fallu donner :

Fonction hauteur à compléter...
def hauteur(arbre):
    if est_vide(arbre):
        return -1
    else:
        return 1 + max(..., ...)

Et la réponse attendue :

def hauteur(arbre):
    if est_vide(arbre):
        return -1
    else:
        return 1 + max(hauteur(sous_arbre_gauche(arbre)), hauteur(sous_arbre_droit(arbre)))
Réponse
Algorithme de la hauteur complété
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Algorithme hauteur(A):
    test d'assertion : A est supposé non vide
    si sous_arbre_gauche(A) vide et sous_arbre_droit(A) vide:
        renvoyer 0
    sinon, si sous_arbre_gauche(A) vide:
        renvoyer 1 + hauteur(sous_arbre_droit(A))
    sinon, si  sous_arbre_droit(A) vide:
        renvoyer 1 + hauteur(sous_arbre_gauche(A))
    sinon
        renvoyer 1 + max(hauteur(sous_arbre_gauche(A)), hauteur(sous_arbre_droit(A)))

On considère un arbre binaire \(R\) dont on note \(G\) le sous-arbre gauche et \(D\) le sous-arbre droit. On suppose que \(R\) est de hauteur \(4\) et \(G\) de hauteur \(2\).

Question 3a

Justifier le fait que \(D\) n'est pas l'arbre vide et déterminer sa hauteur.

Réponse

Par l'absurde. Supposons que \(D\) soit vide alors par construction la hauteur calculée de \(R\) serait \(1 + 2 = 3\) (application de la ligne 8 de l'algorithme de la hauteur); ce qui contredit l'énoncé.

Par conséquent \(D\) n'est pas vide et si on note \(h_D\) sa hauteur on sait que la hauteur de \(R\) vaut \(1 + max(2, h_D)\) (application de la ligne 10 de l'algorithme de la hauteur). Comme cette hauteur est \(4\), on en déduit que \(h_D = 3\).

Question 3a

Illustrer cette situation par un dessin.

Réponse

arbre 3b

Soit un arbre binaire non vide de hauteur \(h\). On note \(n\) le nombre de nœuds de cet arbre. On admet que \(h+1 \leq n\leq 2^{h+1} - 1\).

Question 4a

Vérifier ces inégalités sur l'arbre binaire de la question 1a.

Réponse

Dans l'arbre 1a on a \(n = 4\) et \(h = 2\). On a bien : \(2 + 1 = 3 \leq 4\leq 2^3 - 1 = 7\).

Question 4b

Expliquer comment construire un arbre binaire de hauteur \(h\) quelconque ayant \(h+1\) nœuds.

Réponse

Puisque \(h+1\) est le minimum de nœuds pour un arbre de hauteur \(h\), cela signifie que si on ôte un nœud, on perd 1 de hauteur. Il suffit donc de créer un arbre possédant une seule branche qui contiendra les \(h+1\) nœuds (et donc \(h\) arêtes).

Question 4c

Expliquer comment construire un arbre binaire de hauteur \(h\) quelconque ayant \(2^{h+1} - 1\) nœuds.

Réponse

Puisque \(2^{h+1} - 1\) est le maximum de nœuds pour un arbre de hauteur \(h\), cela signifie qu'on va remplir chaque niveau de notre arbre ; on montre par récurrence que le niveau \(p\) possède \(2^p\) nœuds au plus :

  • le niveau 0, celui de la racine possède \(1\) nœud (\(2^1 = 1\))
  • on suppose la propriété vraie pour un niveau \(p\). Considérons le niveau \(p+1\) ; le maximum de nœuds est atteint lorsque tous les nœuds du niveau précédent possèdent 2 fils. Comme il y a \(2^p\) nœuds au niveau \(p\), il y a \(2\times 2^p\) au niveau \(p+1\).

Ainsi notre arbre de hauteur \(h\) complet possède \(h\) niveaux tous pleins et donc un total de \(1 + 2 + \ldots + 2^h\) nœuds. Cette somme vaut \(2^{h+1} - 1\).

L'objectif de la fin de l'exercice est d'écrire le code d'une fonction fabrique(h, n) qui prend comme paramètres deux nombres entiers positifs h et n tels que \(h+1 \lt n \lt 2^{h+1} - 1\), et qui renvoie un arbre de hauteur \(h\) à \(n\) nœuds.

Pour cela, on a besoin des deux fonctions suivantes :

  • arbre_vide(), qui renvoie l'arbre vide ;
  • arbre(gauche, droit) qui renvoie l'arbre de fils gauche gaucheet de fils droit droit.
Remarque

Confusion entre une fonction et l'appel d'une fonction :

- le code d'une fonction fabrique(h, n)
+ le code d'une fonction fabrique
Question 5

Recopier sur la copie l'arbre binaire ci-dessous et numéroter ses nœuds de 1 en 1 en commençant à 1, en effectuant un parcours en profondeur préfixe.

arbre 5a

Réponse

arbre 5a num

La fonction fabrique ci-dessous a pour but de répondre au problème posé. Pour cela, la fonction annexe utilise la valeur de n, qu'elle peut modifier, et renvoie un arbre binaire de hauteur hauteur_max dont le nombre de nœuds est égal à la valeur de \(n\) au moment de son appel.

Fonction fabrique à compléter...
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def fabrique(h, n):
    def annexe(hauteur_max):
        if n == 0:
            return arbre_vide()
        elif hauteur_max == 0:
            n = n - 1
            return ...
        else:
            n = n - 1
            gauche = annexe(hauteur_max - 1)
            droite = ...
            return arbre(gauche, droite)
    return annexe(h)
Question 6

Recopier sur la copie les lignes 7 et 11 en complétant les points de suspension.

Réponse
Fonction fabrique
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def fabrique(h, n):
    def annexe(hauteur_max):
        if n == 0:
            return arbre_vide()
        elif hauteur_max == 0:
            n = n - 1
            return arbre(arbre_vide(), arbre_vide())
        else:
            n = n - 1
            gauche = annexe(hauteur_max - 1)
            droite = annexe(hauteur_max - 1)
            return arbre(gauche, droite)
    return annexe(h)
Remarque

Cette dernière question est bien au-delà de ce qu'il est raisonnable de demander à un exercice du bac sur les arbres. En plus ici la variable n ne peut pas être modifiée par la fonction annexe à moins de la déclarer comme nonlocal. Il faudrait, pour rendre le sujet acceptable supprimer purement et simplement cette 6e question.