Corrigé Mines-Ponts 2025 Informatique I MPI — Partie 1 (Q1 à Q11) : Tableau associatif par arbre binaire de recherche équilibré

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique I MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

L'épreuve étudie plusieurs implémentations en C d'un tableau associatif dont les clefs sont des char* et les valeurs des int ; seul le langage C est autorisé, les en-têtes standards (assert.h, stdbool.h, stdlib.h, string.h, …) sont supposés inclus, et l'annexe rappelle strlen, strcpy, strcat et strcmp. Les structures sont immuables : chaque fonction renvoie une nouvelle version, la mémoire n'est pas récupérée dans cette partie.

La hauteur de l'arbre vide vaut $- 1$ et $h (x) = max (h (x_{gauche}), h (x_{droit})) + 1$ ; la valeur d'équilibre d'un nœud est $e (x) = h (x_{gauche}) - h (x_{droit})$ , et un ABR est équilibré si $- 1 ⩽ e (x) ⩽ 1$ en tout nœud $x$ . Les nœuds sont ordonnés par leur clef, dans l'ordre alphabétique :


struct abrNoeud_s {
  char* clef;
  int valeur;

  struct abrNoeud_s* fils_gauche;
  struct abrNoeud_s* fils_droit;
};
typedef struct abrNoeud_s abrNoeud;

Q1. Représentation en mémoire d'une chaîne en C ; nombre d'octets de "arbre".
Q2. Écriture binaire et hexadécimale de 'a', de code ASCII $97$ .
Q3. Écrire char* copie_chaine(char* chaine) (chaine jamais NULL).
Q4. Écrire abrNoeud* abr_creer_noeud(char* clef, int valeur, abrNoeud* fils_gauche, abrNoeud* fils_droit), la clef étant copiée, les sous-arbres non.
Q5. Écrire int abr_equilibre(abrNoeud* noeud).
Q6. Complexité de abr_equilibre pour un arbre de taille $N$ ; comment l'améliorer (sans code) ?
Q7. Approximation du nombre minimal $N$ de nœuds d'un ABR équilibré de hauteur $h$ .
Q8. En déduire une borne supérieure de la hauteur d'un ABR équilibré de taille $N$ .
Q9. Écrire récursivement int abr_rechercher(abrNoeud* noeud, char* clef), la clef étant présente (== ne compare pas le contenu des chaînes).
Q10. Complexité de abr_rechercher sur un arbre équilibré de taille $N$ .
Q11. Intérêt d'un ABR toujours équilibré.

Corrigé

Q1. En C, une chaîne n'est pas un type à part : c'est un tableau de char (un octet chacun, sizeof(char) valant $1$ par définition), rangés à des adresses consécutives et terminés par le caractère nul ' 0', la sentinelle. Une variable char* comme le champ clef ne contient que l'adresse du premier caractère ; la longueur n'est stockée nulle part, on la retrouve en cherchant la sentinelle (c'est ce que fait strlen, en temps linéaire).

"arbre" occupe donc $5 + 1 = 6$ octets : les cinq lettres et le ' 0' final. (Le champ clef lui-même est un pointeur, de $8$ octets sur une machine $64$ bits ; il ne contient pas la chaîne.)

Ce que le correcteur attend : le caractère de fin de chaîne, oublié dans trop de copies selon le jury.

Q2. $97 = 64 + 32 + 1 = 2^{6} + 2^{5} + 2^{0}$ , d'où, sur un octet,

$97 = (01100001)_{2} = (61)_{16},$

chaque chiffre hexadécimal codant un groupe de quatre bits : $0110 = 6$ et $0001 = 1$ . On écrit 0x61 en C.

Q3. On alloue la longueur plus un octet pour la sentinelle, puis on copie avec strcpy (rappelée en annexe), qui recopie aussi le ' 0' :


char* copie_chaine(char* chaine) {
  char* copie = malloc((strlen(chaine) + 1) * sizeof(char));
  assert(copie != NULL);
  strcpy(copie, chaine);
  return copie;
}

La zone allouée a exactement $ℓ + 1$ octets pour une chaîne de longueur $ℓ$ , ce que strcpy écrit : pas de débordement. La copie est indépendante de l'original (modifier l'un ne change pas l'autre). Coût $Θ (ℓ)$ .

Q4. Un nœud renvoyé par la fonction doit survivre à l'appel : il est alloué dans le tas, jamais comme variable locale.


abrNoeud* abr_creer_noeud(char* clef, int valeur,
                          abrNoeud* fils_gauche,
                          abrNoeud* fils_droit) {
  abrNoeud* noeud = malloc(sizeof(abrNoeud));
  assert(noeud != NULL);
  noeud->clef = copie_chaine(clef);
  noeud->valeur = valeur;
  noeud->fils_gauche = fils_gauche;
  noeud->fils_droit = fils_droit;
  return noeud;
}

Les quatre champs sont initialisés ; la clef est copiée (Q3), de sorte que le nœud possède sa propre chaîne, tandis que les sous-arbres sont partagés, ce qui est légitime puisque les structures sont immuables.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →