Aller au contenu

Devoir NSI - Arbres Binaires, Feuilles Basses et SQL

Durée : 90 minutes

Exercice 1 : Feuilles basses (12 points)

Un arbre binaire est soit vide, soit constitué d'un noeud racine ayant au plus deux sous-arbres (gauche et droit).

Une feuille est un noeud sans fils (ni fils gauche, ni fils droit).

La hauteur d'un arbre est la longueur du plus long chemin de la racine jusqu'à une feuille. Un arbre vide a une hauteur de -1, un arbre réduit à une seule feuille a une hauteur de 0.

La profondeur d'un noeud est la longueur du chemin de la racine jusqu'Ă  ce noeud. La racine a une profondeur de 0.

On définit une feuille basse comme une feuille dont la profondeur est égale à la hauteur de l'arbre. Autrement dit, c'est une feuille qui se trouve sur un chemin le plus long depuis la racine et qui "donne sa hauteur" à l'arbre.

1. Dessinez un arbre binaire de 5 noeuds contenant exactement 3 feuilles. Indiquez la profondeur de chaque feuille.

Corrigé 
    1
   / \
  2   3
     / \
    4   5

Feuilles et leurs profondeurs :

  • Noeud 2 : profondeur 1
  • Noeud 4 : profondeur 2
  • Noeud 5 : profondeur 2

2. Dans l'arbre suivant, identifiez toutes les feuilles basses.

Arbre

Corrigé

D'abord, identifions les feuilles : G, H, F

Calculons la hauteur de l'arbre : - Chemin A → B → D → G : longueur 3 - Chemin A → C → E → H : longueur 3 - Chemin A → C → F : longueur 2

La hauteur de l'arbre est 3.

Profondeurs des feuilles : - G : profondeur 3 - H : profondeur 3 - F : profondeur 2

Les feuilles basses sont : G et H (profondeur = hauteur = 3)

3. Expliquez pourquoi dans un arbre binaire parfait, toutes les feuilles sont des feuilles basses.

Corrigé

Dans un arbre binaire parfait, toutes les feuilles se trouvent au même niveau (dessin accepté), c'est-à-dire qu'elles ont toutes la même profondeur. Cette profondeur commune correspond nécessairement à la hauteur de l'arbre (puisque c'est le plus long chemin de la racine à une feuille). Par conséquent, toutes les feuilles ont une profondeur égale à la hauteur de l'arbre, ce qui fait d'elles des feuilles basses par définition.

On représente un arbre binaire en Python avec la classe suivante :

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit

4. On considère l'arbre suivant :

arbre = Noeud(1,Noeud(2,Noeud(4),Noeud(5)),Noeud(3,None,Noeud(6,Noeud(7),Noeud(8))))

Dessinez cet arbre et indiquez la profondeur de chaque noeud.

Corrigé 
        1 (prof: 0)
        / \
        2   3 (prof: 1)
        / \   \
    4   5   6 (prof: 2)
            / \
            7   8 (prof: 3)

5. Écrivez une fonction est_feuille(noeud) qui renvoie True si le noeud est une feuille, False sinon.

Corrigé 
def est_feuille(noeud):
    """Renvoie True si le noeud est une feuille, False sinon."""
    if noeud is None:
        return False
    return noeud.gauche is None and noeud.droit is None

6. Écrivez une fonction récursive hauteur(arbre) qui calcule la hauteur de l'arbre.

Corrigé 
def hauteur(arbre):
    """Calcule la hauteur de l'arbre."""
    if arbre is None:
        return -1
    return 1 + max(hauteur(arbre.gauche),hauteur(arbre.droit))

7. Écrivez une fonction récursive profondeur(noeud, arbre, profondeur_actuelle=0) qui renvoie la profondeur du noeud donné dans l'arbre.

Corrigé 
def profondeur(noeud, arbre, profondeur_actuelle=0):
    """Renvoie la profondeur du noeud donné dans l'arbre."""
    if arbre is None:
        return None

    if arbre == noeud:
        return profondeur_actuelle

    # Recherche dans le sous-arbre gauche
    prof_gauche = profondeur(noeud, arbre.gauche, profondeur_actuelle + 1)
    if prof_gauche is not None:
        return prof_gauche

    # Recherche dans le sous-arbre droit
    prof_droite = profondeur(noeud, arbre.droit, profondeur_actuelle + 1)
    return prof_droite

8. En déduire une fonction est_feuille_basse(noeud, arbre) qui renvoie True si le noeud est une feuille basse, False sinon.

Corrigé 
def est_feuille_basse(noeud, arbre):
    """Renvoie True si le noeud est une feuille basse, False sinon."""
    if not est_feuille(noeud):
        return False

    prof_noeud = profondeur(noeud, arbre)
    hauteur_arbre = hauteur(arbre)

    return prof_noeud == hauteur_arbre

9. En déduire une fonction compter_feuilles_basses(arbre) qui renvoie le nombre de feuilles basses dans l'arbre.

Corrigé 
def compter_feuilles_basses(arbre):
    """Renvoie le nombre de feuilles basses dans l'arbre."""
    if arbre is None:
        return 0

    if est_feuille(arbre):
        if est_feuille_basse(arbre, arbre):
            return 1
        return 0

    # Parcours récursif (tout parcours est possible)
    def compter_aux(noeud):
        if noeud is None:
            return 0

        if est_feuille(noeud) and est_feuille_basse(noeud, arbre):
            return 1

        return compter_aux(noeud.gauche) + compter_aux(noeud.droit)

    return compter_aux(arbre)

10. Écrivez une fonction supprimer_feuilles_basses(arbre) qui renvoie un nouvel arbre obtenu en supprimant toutes les feuilles basses de l'arbre original (les parents de ces feuilles deviennent alors des feuilles).

Corrigé 
def supprimer_feuilles_basses(arbre):
    """Renvoie un nouvel arbre sans les feuilles basses."""
    if arbre is None:
        return None

    # Si c'est une feuille basse, on la supprime
    if est_feuille(arbre) and est_feuille_basse(arbre, arbre):
        return None

    # Sinon, on reconstruit l'arbre récursivement
    def supprimer_aux(noeud):
        if noeud is None:
            return None

        if est_feuille(noeud) and est_feuille_basse(noeud, arbre):
            return None

        nouveau_gauche = supprimer_aux(noeud.gauche)
        nouveau_droit = supprimer_aux(noeud.droit)

        return Noeud(noeud.valeur, nouveau_gauche, nouveau_droit)

    return supprimer_aux(arbre)

Exercice 2 (8 points)

Un supermarché utilise une base de données qui contient des informations sur les produits, les fournisseurs, les commandes passées et leurs détails. Le modèle relationnel de cette base est donné par le schéma ci-dessous :

Figure 1. Schéma relationnel de cette base

Dans ce schéma, les clés primaires sont soulignées et les clés étrangères sont précédées du symbole #. Le type de chaque attribut est indiqué entre parenthèses.

Schéma Relationnel

On considère l'extrait de la base de données ci-dessous :

Table Commandes

id_commande date_commande total_commande
1 03/06/2025 176.00
2 08/12/2024 1150.00
3 21/04/2025 155.00

Table Produits

id_produit nom categorie prix quantite_stock id_fournisseur
1 Yaourts blanc x 4 Alimentaire 2.80 50 2
2 Lait Alimentaire 1.20 200 2
3 Pain Alimentaire 1.50 100 4
4 Harry Potter 1 Livre 15.00 20 3
5 Jeu d'Ă©checs Jeux 40.00 30 3
6 T-shirt taille M VĂŞtement 10.00 80 1
7 Jeans taille M VĂŞtement 25.00 60 5

Table Fournisseurs

id_fournisseur nom adresse ville pays
1 Moda e stile Via della Moda, 45 Milano Italie
2 Laiteries Unies 22 Avenue des Vaches Lisieux France
3 Livres en Folie 56 Boulevard des Livres Toulouse France
4 Boulangerie du Coin 34 Rue du Pain Nantes France
5 Estilo Español Calle de la Moda, 123 Madrid Espagne

Table Details

id_details id_commande id_produit quantite prix_unitaire
1 1 1 20 2.80
2 1 2 100 1.20
3 2 6 40 10.00
4 2 7 30 25.00
5 3 5 2 40.00
6 3 4 5 15.00

L'énoncé de cet exercice utilise tout ou une partie des mots clefs du langage SQL suivants : SELECT, DISTINCT, FROM, WHERE, JOIN … ON, UPDATE … SET, DELETE, INSERT INTO … VALUES.

Avant de mettre en vente un nouveau produit, il faut le créer dans la base.

1. Écrire une requête SQL permettant d'ajouter le produit croissant référencé dans la base sous le numéro 10. Il est vendu au prix unitaire de 0,90 €. Le magasin se fournit, pour ce produit, auprès de Boulangerie du Coin.

Corrigé 
INSERT INTO Produits (id_produit, nom, categorie, prix, quantite_stock, id_fournisseur)
VALUES (10, 'Croissant', 'Alimentaire', 0.90, 0, 4);

Le fournisseur Livres en Folie a changé d'entrepôt. Il se trouve maintenant au 78 Rue des Jeux à Elbeuf (France).

2. Écrire la requête SQL permettant de mettre à jour la base de données.

Corrigé 
UPDATE Fournisseurs
SET adresse = '78 Rue des Jeux', ville = 'Elbeuf'
WHERE nom = 'Livres en Folie';

3. Décrire le résultat obtenu avec la requête SQL ci-dessous :

                                    SELECT nom 
                                    FROM Produits 
                                    WHERE categorie = 'Alimentaire' ;
Corrigé

Cette requête affiche le nom de tous les produits de catégorie "Alimentaire" :

  • Yaourts blanc x 4
  • Lait
  • Pain

4. Écrire une requête SQL permettant d'afficher les détails des commandes passées ayant un total de commande supérieur ou égal à 1000 €.

Corrigé 
SELECT *
FROM Commandes
WHERE total_commande >= 1000;

Ou pour afficher les détails complets :

SELECT Commandes.*, Details.*
FROM Commandes
JOIN Details ON Commandes.id_commande = Details.id_commande
WHERE total_commande >= 1000;

5. Écrire une requête SQL permettant d'afficher le nom des fournisseurs basés en Espagne ou en Italie.

Corrigé 
SELECT nom
FROM Fournisseurs
WHERE pays = 'Espagne' OR pays = 'Italie';

6. Écrire une requête SQL qui permet d'afficher le nom de tous les fournisseurs qui ont vendu des produits alimentaires.

Corrigé 
SELECT DISTINCT Fournisseurs.nom
FROM Fournisseurs
JOIN Produits ON Fournisseurs.id_fournisseur = Produits.id_fournisseur
WHERE Produits.categorie = 'Alimentaire';

7. Écrire une requête SQL permettant d'afficher le numéro et la date des commandes ainsi que le nom des fournisseurs où des produits de catégories Vêtement ont été commandés.

Corrigé 
SELECT DISTINCT Commandes.id_commande, Commandes.date_commande, Fournisseurs.nom
FROM Commandes
JOIN Details ON Commandes.id_commande = Details.id_commande
JOIN Produits ON Details.id_produit = Produits.id_produit
JOIN Fournisseurs ON Produits.id_fournisseur = Fournisseurs.id_fournisseur
WHERE Produits.categorie = 'VĂŞtement';