Solution de Dictionnaire des indices - Sujet 24 - EP NSI 2025

Énoncé du problème

Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction enumere qui prend en paramètre un tableau tab (type list) et renvoie un dictionnaire d dont les clés sont les éléments de tab avec pour valeur associée la liste des indices de l’élément dans le tableau tab.

Exemple :

>>> enumere([])
{}
>>> enumere([1, 2, 3])
{1: [0], 2: [1], 3: [2]}
>>> enumere([1, 1, 2, 3, 2, 1])
{1: [0, 1, 5], 2: [2, 4], 3: [3]}

Exercice 2

EXERCICE 2 (10 points)

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit représentés par une instance de la classe Noeud donnée ci-dessous.

class Noeud:
    """Classe représentant un noeud d'un arbre binaire"""
    def __init__(self, etiquette, gauche, droit):
        """Crée un noeud de valeur etiquette avec 
        gauche et droit comme fils."""
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit

def parcours(arbre, liste):
    """parcours récursivement l'arbre en ajoutant les étiquettes
    de ses noeuds à la liste passée en argument en ordre infixe."""
    if arbre != None:
        parcours(arbre.gauche, liste)
        liste.append(arbre.etiquette)
        parcours(arbre.droit, liste)
    return liste

La fonction récursive parcours renvoie la liste des étiquettes des nœuds de l’arbre implémenté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.

Compléter le code de la fonction insere, présenté page suivante, qui prend en argument un arbre binaire de recherche arbre représenté ainsi et une étiquette cle, non présente dans l’arbre, et qui :

renvoie une nouvelle feuille d’étiquette cle s’il est vide ;
renvoie l’arbre après l’avoir modifié en insérant cle sinon ;
garantit que l’arbre ainsi complété soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci- dessous :

flowchart TD
    n5((5)) --> n2((2))
    n5 --> n7((7))
    n2 --> n3((3))

[Figure : schéma d’un arbre binaire de recherche. La racine porte l’étiquette 5 ; son fils gauche porte l’étiquette 2 et son fils droit l’étiquette 7 ; le nœud d’étiquette 2 possède un unique fils, d’étiquette 3.]

def insere(arbre, cle):
    """insere la cle dans l'arbre binaire de recherche
    représenté par arbre.
    Retourne l'arbre modifié."""
    if arbre == None:
        return Noeud(cle, None, None) # creation d'une feuille
    else:
        if ...: 
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = ... 
        return arbre

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

tab est de type list et 0 <= len(tab) <= 10^4
les éléments de tab sont hachables : ils sont tous de type int ou tous de type str
si les éléments sont des entiers : -10^9 <= tab[i] <= 10^9
si les éléments sont des chaînes : 1 <= len(tab[i]) <= 100
enumere([]) renvoie le dictionnaire vide {}
pour chaque clé, la liste associée contient tous les indices de cet élément dans tab, rangés par ordre croissant
l’ordre des clés du dictionnaire renvoyé n’est pas imposé

Exercice 2

Contraintes :

arbre vaut None (arbre vide) ou est une instance de la classe Noeud fournie, et c’est un arbre binaire de recherche
l’arbre contient au plus 200 nœuds, et sa hauteur est donc au plus 200
les étiquettes sont des entiers deux à deux distincts, avec -10^9 <= etiquette <= 10^9
cle est un entier vérifiant -10^9 <= cle <= 10^9 et n’est pas déjà présente dans l’arbre
insere renvoie l’arbre binaire de recherche obtenu après insertion : une nouvelle feuille si arbre est vide, l’arbre arbre modifié sinon
la classe Noeud et la fonction parcours sont fournies et ne doivent pas être modifiées

Solution

Exercice 1 - le dictionnaire des indices

L’idée. On veut, pour chaque valeur du tableau, la liste des positions où elle apparaît. Il suffit de parcourir le tableau une seule fois en gardant l’indice i de l’élément que l’on regarde. Si cette valeur n’est pas encore une clé du dictionnaire, on lui associe une liste contenant i ; si elle y est déjà, on ajoute i à sa liste.

Un petit exemple. Pour [1, 1, 2] : à l’indice 0, la clé 1 n’existe pas, on crée {1: [0]} ; à l’indice 1, la clé 1 existe déjà, on complète en {1: [0, 1]} ; à l’indice 2, on crée la clé 2 et on obtient {1: [0, 1], 2: [2]}.

def enumere(tab):
    d = {}
    for i in range(len(tab)):
        element = tab[i]
        # Première rencontre de l'élément : on crée sa liste d'indices,
        # sinon on ajoute l'indice à la liste déjà présente
        if element not in d:
            d[element] = [i]
        else:
            d[element].append(i)
    return d

d est le dictionnaire que l’on construit petit à petit et que l’on renvoie à la fin. On boucle sur range(len(tab)) plutôt que directement sur les éléments, parce qu’on a besoin de l’indice i autant que de la valeur. Comme on parcourt le tableau de la gauche vers la droite, les indices sont ajoutés dans l’ordre croissant : les listes sont donc triées sans qu’on ait rien à faire. Enfin, si tab est vide, la boucle ne tourne aucune fois et on renvoie {}, ce qui est bien le résultat attendu.

Exercice 2 - insertion dans un arbre binaire de recherche

L’idée. Dans un arbre binaire de recherche, toutes les étiquettes du sous-arbre gauche d’un nœud sont plus petites que son étiquette, et toutes celles de son sous-arbre droit sont plus grandes. Pour insérer cle, on la compare donc à l’étiquette de la racine : si cle est plus petite, elle a sa place dans le sous-arbre gauche, sinon dans le sous-arbre droit. On recommence la même chose sur ce sous-arbre, jusqu’à tomber sur un arbre vide : c’est là que la nouvelle feuille se crée.

Un petit exemple. Insérer 4 dans l’arbre de racine 5 : 4 < 5, on descend à gauche, sur le nœud 2 ; 4 > 2, on descend à droite, sur le nœud 3 ; 4 > 3, on descend à droite de 3, qui est vide : la feuille 4 est créée à cet endroit.

def insere(arbre, cle):
    """insere la cle dans l'arbre binaire de recherche
    représenté par arbre.
    Retourne l'arbre modifié."""
    if arbre == None:
        return Noeud(cle, None, None) # creation d'une feuille
    else:
        # À gauche les étiquettes plus petites, à droite les plus grandes :
        # c'est ce qui garde un arbre binaire de recherche valide
        if cle < arbre.etiquette:
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = insere(arbre.droit, cle)
        return arbre

Le premier trou devient le test cle < arbre.etiquette, et le second l’appel récursif insere(arbre.droit, cle), exactement symétrique de celui de la branche gauche. Le cas d’arrêt était déjà écrit dans l’énoncé : quand arbre vaut None, on renvoie une feuille neuve. Ce sont les lignes arbre.gauche = ... et arbre.droit = ... qui raccrochent cette feuille à l’arbre : l’appel récursif renvoie le sous-arbre une fois modifié, et on le réaffecte au bon fils. Comme l’énoncé précise que cle n’est pas déjà dans l’arbre, le cas d’égalité ne se présente jamais.

Le test demandé. Dans l’arbre de la figure, le nœud 3 est le fils droit du nœud 2, puisque 3 est plus grand que 2.

arbre = Noeud(5, Noeud(2, None, Noeud(3, None, None)), Noeud(7, None, None))
for cle in [1, 4, 6, 8]:
    arbre = insere(arbre, cle)
print(parcours(arbre, []))  # [1, 2, 3, 4, 5, 6, 7, 8]

Le parcours infixe d’un arbre binaire de recherche donne toujours les étiquettes en ordre croissant : obtenir [1, 2, 3, 4, 5, 6, 7, 8] est donc une bonne façon de vérifier que les quatre insertions ont bien respecté la structure.