CONCOURS BLANC  FILIÈRE MP2I

ÉPREUVE D'INFORMATIQUE COMMUNE

TRAVAUX PRATIQUES
LES ARBRES
Du vocabulaire de base aux arbres bicolores

Durée conseillée : 4 heures

Instructions générales.
ˆ Le sujet comporte cinq parties indépendantes mais de diculté croissante
; il est conseillé de les traiter dans l'ordre.
ˆ Les parties I, II et III forment le socle du cours (arbres d'arité quelconque,
arbres binaires, arbres binaires de recherche et arbres bicolores) et sont en-
tièrement rédigées , avec exercices d'application.
ˆ La partie IV propose des questions courtes de type concours, une par
thème du cours.
ˆ La partie V est un problème de synthèse en trois sous-parties, mêlant
les notions précédentes, dans l'esprit d'une épreuve écrite de concours.
ˆ Le langage utilisé pour les questions de programmation est le langage C, sauf
mention contraire.
ˆ Toute réponse doit être justiée : la seule valeur numérique ou le seul code,
sans explication, ne rapporte pas la totalité des points.
ˆ Le candidat est invité à dessiner les arbres obtenus à chaque étape des algo-
rithmes demandés ; un dessin clair et juste vaut une démonstration.

Ce sujet reprend et approfondit le cours  Les arbres : du vocabulaire de base aux arbres bicolores .
MP2I  Structures de données TP : Les Arbres

Contents
1 Généralités sur les arbres et arbres d'arité quelconque 2
1.1 Vocabulaire de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Représentation en C par la technique Left-Child Right-Sibling . . . . . . . . . . . 2
1.3 Parcours en profondeur (DFS) et en largeur (BFS) . . . . . . . . . . . . . . . . . 3

2 Arbres binaires 5
2.1 Structure et parcours en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Parcours en largeur et hauteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Arbres binaires de recherche et arbres bicolores 7

3.1 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Rotations et arbres bicolores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4 Questions de type concours (une par thème) 9

5 Problème de synthèse 10
Annexe  Éléments de correction détaillés 12

Tournez la page S.V.P. 1/ 16

MP2I  Structures de données TP : Les Arbres

Partie I  Généralités sur les arbres et arbres d'arité quelconque

Cette première partie revient sur le vocabulaire fondamental des arbres, puis sur leur représenta-
tion en langage C dans le cas général (arité quelconque), via la technique Left-Child Right-Sibling
(LCRS), et sur les parcours en profondeur et en largeur associés.

1.1 Vocabulaire de base

On considère l'arbre T suivant, que l'on gardera comme l rouge tout au long de cette sous-partie
:

A B

D E
F G

Question 1.1.1. Rappeler la dénition d'un arbre en termes de n÷uds, d'arêtes, de racine, et
de la propriété d'absence de cycle. Pourquoi cette dernière propriété est-elle indispensable pour
parler de profondeur d'un n÷ud sans ambiguïté ?
Question 1.1.2. Pour l'arbre T ci-dessus, donner : la racine, l'ensemble des feuilles, l'ensemble
des n÷uds internes, les ls de A, le père de H, les frères de F.
Question 1.1.3. Déterminer la profondeur de chacun des n÷uds de T , puis la hauteur de T .
Justier en une phrase la dénition retenue de la hauteur (plus long chemin racine-feuille, en
nombre d'arêtes).
Question 1.1.4. Déterminer l'arité de chaque n÷ud de T . En déduire si T peut être qualié
d'arbre binaire. Justier.
Question 1.1.5. On dénit le sous-arbre enraciné en un n÷ud n comme l'arbre formé de n et
de tous ses descendants. Donner la liste des n÷uds du sous-arbre enraciné en A. Ce sous-arbre
est-il lui-même un arbre au sens de la dénition de la question 1 ? Justier.
Remarque. On insiste sur le fait qu'un sous-arbre enraciné en n est un arbre à part entière
: il possède sa propre racine (n), et toute la théorie développée pour un arbre s'applique de
façon identique à ce sous-arbre. C'est ce qui permettra, dans toute la suite, de raisonner par
récurrence sur la structure de l'arbre : une propriété vraie sur les sous-arbres des ls d'un
n÷ud, combinée à un raisonnement local sur ce n÷ud, donne une propriété vraie sur l'arbre
entier.

1.2 Représentation en C par la technique Left-Child Right-Sibling

On rappelle la structure de n÷ud LCRS vue en cours :

Tournez la page S.V.P. 2/ 16

MP2I  Structures de données TP : Les Arbres

1 typedef int value_t ;

2
3 typedef struct node_t node_t ;
4 struct node_t {
5 value_t data ;
6 node_t * child ; /* pointeur vers le PREMIER fils */
7 node_t * sibling ; /* pointeur vers le FRERE SUIVANT */
8 };

Question 1.2.1. Expliquer pourquoi une structure C classique (à nombre de champs xé) ne
permet pas de représenter directement un n÷ud d'arité quelconque, contrairement à un type
algébrique OCaml utilisant un constructeur avec un argument de type liste.
Question 1.2.2. Représenter, à la façon du cours (dessin avec èches child en trait plein et
sibling en trait pointillé), l'arbre T de la sous-partie précédente sous forme LCRS.

Question 1.2.3. Écrire une fonction int nombre_fils(node_t *n) qui renvoie le nombre de
ls directs d'un n÷ud n (on ne demande pas de compter tous les descendants, seulement les ls).
Justier la terminaison de la boucle utilisée.
Question 1.2.4. En déduire une fonction récursive int arite_max(node_t *n) qui calcule
l'arité maximale parmi tous les n÷uds du sous-arbre enraciné en n (on rappelle qu'il faut parcourir
tout l'arbre, pas seulement les ls de n).
Question 1.2.5. On souhaite écrire une fonction int hauteur(node_t *n) qui calcule la hau-
teur du sous-arbre enraciné en n (hauteur −1 pour un arbre vide, par convention). Écrire cette
fonction en justiant pourquoi il faut prendre le maximum sur les ls, et non une simple
récursion sur child puis sibling comme pour un parcours.
Indication. On distinguera bien deux récursions diérentes : une récursion  en profondeur
 le long de child pour descendre chez les ls, combinée à une comparaison entre les hauteurs
obtenues, et non une simple addition comme lorsqu'on parcourt l'arbre.

1.3 Parcours en profondeur (DFS) et en largeur (BFS)

Question 1.3.1. Rappeler la diérence de principe entre un parcours en profondeur (DFS) et

un parcours en largeur (BFS). Laquelle des deux structures de données  pile ou le  est na-
turellement associée à chacun de ces parcours, et pourquoi la récursivité met-elle  gratuitement
 en jeu une pile ?
Question 1.3.2. On exécute dfs_prefixe(R) sur l'arbre T de la sous-partie 1.1. Donner, en le
justiant étape par étape comme dans le cours, l'ordre exact dans lequel les n÷uds sont traités.
Question 1.3.3. Même question pour dfs_postfixe(R). Comparer les deux ordres obtenus
: est-il vrai en général que le parcours postxe est exactement l'inverse du parcours préxe ?
Justier sur un petit contre-exemple si la réponse est négative.
Question 1.3.4. Dérouler à la main, comme dans le cours (tableau étape par étape avec l'état
de la le), l'exécution de bfs(R) sur l'arbre T . On détaillera en particulier le rôle de la boucle
interne while (s != NULL).
Question 1.3.5. Un élève propose la version suivante, censée réaliser un parcours en largeur,
mais sans boucle interne :

Tournez la page S.V.P. 3/ 16

MP2I  Structures de données TP : Les Arbres

1 void bfs_eleve ( node_t * n ) {

2 file * f = creer_file () ;
3 enfiler (f , n ) ;
4 while (! file_est_vide ( f ) ) {
5 node_t * s = defiler ( f ) ;
6 if ( s != NULL ) {
7 traitement ( s ) ;
8 enfiler (f , s - > child ) ;
9 enfiler (f , s - > sibling ) ;
10 }
11 }
12 detruire_file ( f ) ;
13 }

Expliquer pourquoi cette version, bien qu'elle termine et traite tous les n÷uds,ne respecte pas
l'ordre  niveau par niveau  attendu d'un BFS dès que l'arbre a un n÷ud de profondeur 2 ayant
lui-même un frère. On illustrera sur l'arbre T .
Question 1.3.6. (Approfondissement, notion de concours) On munit chaque n÷ud d'un
champ supplémentaire int taille initialisé à 0. Écrire une fonction void calcule_tailles(node_t
*n) qui, par un parcours postxe, remplit dans n->taille le nombre total de n÷uds du sous-
arbre enraciné en n (lui-même compris). Justier que la complexité est en O(N ) où N est le
nombre total de n÷uds de l'arbre.
Question 1.3.7. (Approfondissement) Proposer, sans écrire tout le code, une méthode
itérative (à base de pile explicite, sans récursivité) réalisant le même parcours que dfs_prefixe.
Quel est l'ordre dans lequel il faut empiler les enfants d'un n÷ud pour retrouver exactement le
même ordre de traitement que la version récursive ?

Tournez la page S.V.P. 4/ 16

MP2I  Structures de données TP : Les Arbres

Partie II  Arbres binaires

On se restreint maintenant au cas particulier, mais fondamental, des arbres binaires : chaque
n÷ud possède au plus un ls gauche et un ls droit, explicitement distingués.
1 typedef int value_t ;
2
3 typedef struct node_t node_t ;
4 struct node_t {
5 value_t data ;
6 node_t * left ;
7 node_t * right ;
8 };

On travaille sur l'arbre binaire B suivant :

b c

d e f g

2.1 Structure et parcours en profondeur

Question 2.1.1. Pourquoi la technique Left-Child Right-Sibling, vue en partie I, devient-elle

inutile pour un arbre binaire ? Quel est l'avantage pratique (en termes de simplicité du code) de
la structure left/right par rapport à child/sibling dans ce cas particulier ?
Question 2.1.2. Donner, sans justication excessive (il s'agit d'application directe), les trois
parcours en profondeur (préxe, inxe, postxe) de l'arbre B .
Question 2.1.3. Expliquer, à l'aide de la méthode du  contour  vue en cours (main gauche
posée sur l'arbre), comment retrouver à la main les trois ordres précédents sans écrire la récursion.
Appliquer explicitement cette méthode sur le sous-arbre enraciné en b.
Question 2.1.4. On donne le parcours préxe x, y, z, t et le parcours inxe y, x, t, z d'un arbre
binaire à quatre n÷uds. Reconstruire cet arbre et justier la méthode générale utilisée (rôle de
la racine dans le parcours préxe pour séparer le parcours inxe en deux morceaux).
Question 2.1.5. (Classique de concours) Montrer que la connaissance du parcours préxe et
du parcours inxe d'un arbre binaire détermine cet arbre de façon unique, alors que la connais-
sance du parcours préxe et du parcours postxe seuls ne le permet pas toujours. On illustrera
l'ambiguïté sur un petit exemple à deux n÷uds.

2.2 Parcours en largeur et hauteur

Question 2.2.1. Écrire la fonction bfs pour un arbre binaire (structure left/right), en
s'inspirant de la version n-aire du cours mais en protant de l'absence de boucle interne. Dérouler
ensuite son exécution sur B et donner l'ordre de traitement obtenu.

Tournez la page S.V.P. 5/ 16

MP2I  Structures de données TP : Les Arbres

Question 2.2.2. Écrire une fonction récursive int hauteur(node_t *n) pour un arbre binaire
(convention : hauteur −1 pour l'arbre vide). En déduire, sans la programmer, une méthode
pour tester si un arbre binaire est équilibré au sens AVL (diérence de hauteur entre sous-arbre
gauche et sous-arbre droit au plus 1, récursivement).
Question 2.2.3. Écrire une fonction int compte_feuilles(node_t *n) qui compte le nombre
de feuilles d'un arbre binaire. Donner, en la justiant par récurrence sur la hauteur h, une
majoration du nombre de feuilles d'un arbre binaire de hauteur h.
Question 2.2.4. (Classique de concours) On appelle arbre binaire complet un arbre binaire
dont tous les niveaux sont entièrement remplis, sauf éventuellement le dernier qui est rempli de
gauche à droite. Justier que, dans ce cas, la représentation par tableau vue en cours (ls gauche
d'indice 2i + 1, ls droit d'indice 2i + 2) ne gaspille aucune case. Que se passe-t-il si l'arbre n'est
pas complet ?
Question 2.2.5. (Approfondissement) Écrire une fonction bool meme_forme(node_t *a,
node_t *b) qui teste si deux arbres binaires ont la même forme (même disposition de n÷uds
internes et de feuilles), indépendamment des valeurs stockées. Quelle est la complexité de cette
fonction en fonction des tailles na et nb des deux arbres ?
Question 2.2.6. (Approfondissement, à rédiger avec soin) On souhaite sérialiser un
arbre binaire, c'est-à-dire produire une liste de valeurs (avec un marqueur spécial NIL pour les
ls absents) permettant de reconstruire l'arbre de façon unique. Montrer qu'un simple parcours
préxe, où l'on note explicitement NIL à chaque ls absent, sut à reconstruire l'arbre sans
ambiguïté (contrairement à la question 5 de la sous-partie précédente). Pourquoi la présence des
marqueurs NIL change-t-elle la situation ?

Tournez la page S.V.P. 6/ 16

MP2I  Structures de données TP : Les Arbres

Partie III  Arbres binaires de recherche et arbres bicolores

Cette partie, la plus longue, reprend en profondeur les arbres binaires de recherche (ABR), leur
défaut fondamental (absence de garantie d'équilibre), puis les arbres bicolores qui corrigent ce
défaut.

3.1 Arbres binaires de recherche

Question 3.1.1. Rappeler la dénition d'un ABR (on précisera bien : ordre total sur les clés,
unicité des clés, et la propriété portant sur les sous-arbres gauche et droit de chaque n÷ud, pas
seulement de la racine).
Question 3.1.2. On insère successivement, dans un ABR initialement vide, les clés 50, 30, 70, 20, 40, 60, 80.
Dessiner l'ABR obtenu. Donner son parcours inxe et vérier qu'il redonne les clés triées.
Question 3.1.3. (Classique) Justier soigneusement pourquoi le parcours inxe d'un ABR
donne toujours la liste des clés triées par ordre croissant. On rédigera une démonstration par
récurrence sur la structure de l'arbre, en utilisant la dénition d'ABR de la question 1.
Question 3.1.4. On insère maintenant les clés 10, 20, 30, 40, 50 (déjà triées) dans un ABR
initialement vide. Dessiner l'arbre obtenu et donner sa hauteur. En quoi cet exemple illustre-t-il
le défaut majeur des ABR non équilibrés ? Donner la complexité, dans le pire cas, de la recherche
d'une clé dans un ABR à n n÷uds construit de cette façon.
Question 3.1.5. Écrire une fonction récursive node_t *recherche(node_t *n, value_t x)
pour un ABR. Justier que sa complexité est en O(h), où h est la hauteur de l'arbre, et pourquoi
on ne peut pas espérer mieux dans le cas général.

3.2 Rotations et arbres bicolores

Question 3.2.1. Rappeler les cinq propriétés dénissant un arbre bicolore. Pour chacune,
indiquer en une phrase quel  risque  elle permet d'écarter si on la supprimait.
Question 3.2.2. Démontrer l'encadrement hn ≤ h ≤ 2hn entre la hauteur h d'un arbre bicolore
et sa hauteur noire hn , en reprenant l'argument du cours (alternance rouge/noir imposée par la
propriété 3). En déduire que h = O(log n).
Question 3.2.3. Expliquer précisément, schéma à l'appui, ce que réalise une rotation droite au
n÷ud x, et pourquoi cette opération préserve l'ordre inxe de l'arbre (on justiera en particulier
le devenir du sous-arbre noté α dans le cours). Quelle information supplémentaire, absente des
structures des parties I et II, est indispensable pour implémenter les rotations, et pourquoi ?
Question 3.2.4. On considère l'arbre bicolore suivant, où N est un nouveau n÷ud rouge que
l'on vient d'insérer :

Tournez la page S.V.P. 7/ 16

MP2I  Structures de données TP : Les Arbres

G (noir)

P (rouge) (noir)

U (noir) N (rouge)

Identier, en justiant à partir de l'aiguillage du cours (insertion_repare_arbre), dans quel

cas de réparation (1 à 5) on se trouve. Préciser en particulier si l'on est dans une conguration
en  ligne droite  ou en  zig-zag , et pourquoi cela conditionne la suite du traitement.
Question 3.2.5. Pour la conguration de la question précédente, dérouler entièrement la ré-
paration (rotation(s) et recoloriage(s)) et dessiner l'arbre nal. Vérier explicitement, sur le
résultat, les cinq propriétés bicolores.
Question 3.2.6. (Classique de concours) Pourquoi choisit-on de colorier en rouge le n÷ud
nouvellement inséré dans un arbre bicolore, plutôt qu'en noir ? Justier rigoureusement, en ex-
pliquant quelle propriété serait nécessairement violée dans le second cas, et pourquoi la violation
potentielle dans le premier cas est plus facile à réparer localement.
Question 3.2.7. On insère successivement les clés 10, 20, 30, 15 dans un arbre bicolore initiale-
ment vide (on suivra exactement l'algorithme du cours). Reproduire, sous forme d'un tableau à
quatre lignes comme dans le support de cours, le déroulé complet : n÷ud inséré, cas de réparation
rencontré, opérations eectuées. Dessiner l'arbre nal et vérier les cinq propriétés.
Question 3.2.8. (Approfondissement) Justier que la fonction de réparation par insertion
eectue au plus deux rotations, quel que soit l'arbre de départ et quelle que soit la clé insérée.
On s'appuiera sur le fait que seul le cas 3 se relance récursivement, et que les cas 4 et 5 ne se
relancent jamais.
Question 3.2.9. (Approfondissement, ouverture sur la suppression) On rappelle que
la suppression d'un n÷ud S se ramène à la suppression de son prédécesseur inxe M (le plus
grand élément de son sous-arbre gauche), lequel n'a jamais de ls droit. Justier cette dernière
armation. Expliquer pourquoi le cas  M noir et son ls C noir  est le seul cas problématique
parmi les trois cas listés en cours, en le reliant à la propriété 5 (hauteur noire uniforme).

Tournez la page S.V.P. 8/ 16

MP2I  Structures de données TP : Les Arbres

Partie IV  Questions de type concours (une par thème)

Cette partie regroupe des questions courtes, dans l'esprit des questions de cours ou de début de
problème que l'on rencontre en épreuve écrite. Chaque question porte sur un thème distinct des
parties précédentes ; une réponse concise mais rigoureusement justiée est attendue.
Question 4.1. (Vocabulaire) Un arbre à n n÷uds possède exactement n − 1 arêtes. Démontrer
cette propriété par récurrence sur n.
Question 4.2. (Arbres n-aires) Dans la représentation LCRS, pourquoi le champ sibling de
la racine vaut-il toujours NULL ? Cette propriété reste-t-elle vraie pour la racine d'un sous-arbre
quelconque de l'arbre ? Justier.
Question 4.3. (DFS/BFS) Donner un exemple d'arbre (au moins 5 n÷uds) pour lequel le
parcours préxe et le parcours en largeur (BFS) coïncident exactement. Cette situation est-elle
possible pour un arbre de hauteur ≥ 2 ayant un n÷ud d'arité ≥ 2 à la racine ? Justier.
Question 4.4. (Arbres binaires) Combien existe-t-il d'arbres binaires distincts (en tant que
formes, indépendamment des valeurs) à 3 n÷uds ? Énumérer.
Question 4.5. (Parcours inxe) Un arbre binaire de recherche non vide a-t-il toujours un n÷ud
de plus petite clé sans ls gauche ? Justier, et en déduire un algorithme (sans le programmer)
pour trouver le minimum d'un ABR.
Question 4.6. (Complexité) Justier que la recherche, l'insertion et la suppression dans un
ABR quelconque sont en O(h) où h est la hauteur de l'arbre, puis pourquoi cette borne devient
O(log n) dans un arbre bicolore à n n÷uds.

Question 4.7. (Rotations) Une rotation (gauche ou droite) modie-t-elle le nombre total de
n÷uds de l'arbre ? Modie-t-elle nécessairement sa hauteur ? Justier chaque réponse par un
exemple.
Question 4.8. (Arbres bicolores) Un arbre réduit à un seul n÷ud (la racine, sans ls autres que
des feuilles NIL) est-il un arbre bicolore valide ? Justier en vériant les cinq propriétés.
Question 4.9. (Hauteur noire) Deux arbres bicolores distincts, construits par des insertions
dans des ordres diérents mais portant sur le même ensemble de n clés, ont-ils nécessairement
la même hauteur noire ? Justier ou donner un contre-exemple.
Question 4.10. (Synthèse) Classer, en le justiant en une phrase pour chacun, les quatre types
de structures vues dans ce TP (arbre n-aire, arbre binaire, ABR, arbre bicolore) du plus général
au plus contraint.

Tournez la page S.V.P. 9/ 16

MP2I  Structures de données TP : Les Arbres

Partie V  Problème de synthèse

On termine ce TP par un problème unique, dans l'esprit d'une épreuve de concours, qui réunit les
trois structures étudiées : arbre d'arité quelconque, arbre binaire, arbre bicolore. On considère
une application de gestion d'une arborescence de chiers, dans laquelle on souhaite indexer
rapidement les noms de chiers pour une recherche ecace.

V.1  De l'arborescence de chiers à l'arbre n-aire

On modélise une arborescence de chiers par un arbre d'arité quelconque, représenté en LCRS
comme en partie I, où chaque n÷ud représente soit un dossier (n÷ud interne), soit un chier
(feuille).
Question 5.1. Écrire une fonction int compte_fichiers(node_t *n) qui renvoie le nombre
de feuilles du sous-arbre enraciné en n (donc le nombre de chiers, en excluant les dossiers vides
éventuels que l'on supposera absents ici).
Question 5.2. On souhaite calculer, pour chaque dossier, la profondeur maximale de chier
qu'il contient (profondeur relative à ce dossier). Proposer, sans nécessairement écrire tout le
code C, l'algorithme (récursif, en indiquant le ou les appels récursifs et la façon de combiner les
résultats) permettant de calculer cette quantité pour tous les n÷uds en un seul parcours.
Question 5.3. Justier que l'algorithme précédent s'exécute en O(N ) où N est le nombre total
de n÷uds de l'arborescence, en distinguant bien le travail  local  eectué à chaque n÷ud du
nombre total d'appels récursifs.
Question 5.4. On veut désormais acher l'arborescence  niveau par niveau  (tous les
dossiers et chiers de profondeur 0, puis 1, etc.), comme le ferait une commande d'exploration
par paliers. Quel parcours du cours est adapté à cette tâche ? Justier en une phrase, puis
rappeler la structure de données auxiliaire nécessaire.

V.2  Passage à une structure binaire pour l'indexation

Pour accélérer la recherche d'un chier par son nom, on extrait l'ensemble des noms de chiers
de l'arborescence précédente (question V.1, en listant les feuilles par un parcours de son choix)
et on les insère un par un, dans l'ordre obtenu, dans un arbre binaire de recherche vide, les noms
étant comparés selon l'ordre lexicographique.
Question 5.5. On suppose que le parcours choisi en V.1 pour lister les chiers est un parcours
préxe, et que l'arborescence de chiers a été construite en ajoutant les chiers dans l'ordre
alphabétique croissant à chaque dossier. Expliquer pourquoi l'ABR obtenu risque de dégénérer
en une structure proche d'une liste chaînée. Quelle est alors la complexité, dans le pire cas, d'une
recherche de chier ?
Question 5.6. Proposer, en une ou deux phrases, une idée simple (sans la programmer entière-
ment) permettant de limiter ce risque de dégénérescence sans changer complètement de structure
de données (on pourra penser à l'ordre dans lequel les clés sont insérées).
Question 5.7. Écrire la fonction récursive node_t *inserer_abr(node_t *racine, value_t
nom) qui insère un nom de chier dans l'ABR en respectant la propriété d'ABR (on ne gèrera
pas les doublons, supposés absents).

Tournez la page S.V.P. 10/ 16

MP2I  Structures de données TP : Les Arbres

Question 5.8. Justier que le parcours inxe de l'ABR obtenu permet d'acher instantanément
la liste de tous les chiers triés par ordre alphabétique, sans tri supplémentaire. Quel est l'intérêt
pratique de cette propriété pour une interface de type explorateur de chiers ?

V.3  Garantir la performance : passage à un arbre bicolore

Pour éliminer dénitivement le risque de dégénérescence identié en V.2, on décide de réimplé-
menter l'index sous la forme d'un arbre bicolore.
Question 5.9. Rappeler, en une phrase chacune, les deux opérations supplémentaires (par
rapport à un ABR classique) qu'il faut eectuer après une insertion  ABR classique  dans un
arbre bicolore, et pourquoi elles sont nécessaires.
Question 5.10. On insère, dans un arbre bicolore initialement vide destiné à indexer des noms
de chiers, les clés (préalablement converties en entiers pour simplier) c1 < c2 < c3 < c4 < c5
dans cet ordre croissant. Montrer, en déroulant l'algorithme comme en partie III, que l'arbre
obtenu reste de hauteur O(log n), contrairement à l'ABR naïf de la question V.2.1. On pourra
s'appuyer sur l'exemple 10, 20, 30, 15 traité en partie III et le prolonger avec une cinquième clé
25.

Question 5.11. (Bilan) En comparant les trois structures mises en ÷uvre dans ce problème
(arbre n-aire pour l'arborescence, ABR simple, arbre bicolore), rédiger une synthèse d'une dizaine
de lignes expliquant pourquoi le choix de la structure de données doit dépendre à la fois de la
nature hiérarchique des données (arité quelconque ou binaire) et des garanties de performance
recherchées (pire cas contrôlé ou non).

Tournez la page S.V.P. 11/ 16

MP2I  Structures de données TP : Les Arbres

Annexe  Éléments de correction détaillés des questions classiques

Cette annexe corrige, de façon rédigée, les questions signalées comme  classiques de concours  dans le
sujet. Les autres questions sont laissées à l'appréciation du candidat ; on l'invite à les rédiger avant de
consulter cette annexe.

A.1  Partie I, question 3 : hauteur de l'arbre T

On avait numéroté les profondeurs : R à profondeur 0 ; A, B à profondeur 1 ; D, E, F, G à
profondeur 2 ; H à profondeur 3. La hauteur est le maximum de ces profondeurs, atteint en H
(chemin R → A → E → H, soit 3 arêtes) : h(T ) = 3.

A.2  Partie II, question 4 : unicité préxe + inxe

Principe. Dans un parcours préxe, le premier élément énuméré est toujours la racine de
l'arbre (ou du sous-arbre considéré). Une fois cette racine r connue, on la localise dans le
parcours inxe : tout ce qui précède r dans le parcours inxe appartient au sous-arbre gauche,
tout ce qui suit appartient au sous-arbre droit (c'est la dénition même du parcours inxe).
On sait alors combien d'éléments compte chaque sous-arbre, ce qui permet de scinder également
le parcours préxe restant (les k éléments juste après la racine, dans le préxe, correspondent
exactement au sous-arbre gauche, où k est la taille de ce sous-arbre gauche). On recommence
alors récursivement sur chaque morceau. Cette construction est déterministe à chaque étape,
donc l'arbre est unique.
Application. Préxe x, y, z, t, inxe y, x, t, z . Racine = x (premier du préxe). Dans l'inxe,
x sépare {y} (sous-arbre gauche, 1 élément) de {t, z} (sous-arbre droit, 2 éléments). Le préxe
restant après x, soit y, z, t, se scinde donc en y (sous-arbre gauche) et z, t (sous-arbre droit).
Pour le sous-arbre droit, préxe z, t / inxe t, z : racine z , et t (avant z dans l'inxe) est son ls
gauche. Arbre nal : racine x, ls gauche y (feuille), ls droit z , lequel a pour ls gauche t.

A.3  Partie II, question 4 (sous-partie 2.1) : contre-exemple préxe/postxe

Avec deux n÷uds, un arbre où la racine x a un unique ls gauche y donne : préxe x, y ; postxe
y, x. Un arbre où x a un unique ls droit y donne exactement les mêmes parcours : préxe x, y
; postxe y, x. Les deux arbres sont pourtant diérents (ls à gauche ou à droite) : la paire
(préxe, postxe) ne sut donc pas à déterminer l'arbre de façon unique, contrairement à la
paire (préxe, inxe).

A.4  Partie III, question 3 (sous-partie 3.1) : parcours inxe trié

On démontre par récurrence sur la structure de l'arbre (récurrence forte sur le nombre de n÷uds)
la propriété P(a) :  le parcours inxe de l'ABR a énumère ses clés par ordre strictement croissant
.
Initialisation. Si a est vide, le parcours inxe est la liste vide, trivialement triée.
Hérédité. Soit a un ABR non vide, de racine r, de clé c, de sous-arbre gauche g et de sous-
arbre droit d. Par hypothèse de récurrence, le parcours inxe de g énumère ses clés triées,
toutes strictement inférieures à c (propriété d'ABR) ; de même pour d, avec des clés strictement
supérieures à c. Le parcours inxe de a est, par dénition de l'algorithme, la concaténation :
(inxe de g ), puis c, puis (inxe de d). Cette liste est bien triée : elle commence par des valeurs

Tournez la page S.V.P. 12/ 16

MP2I  Structures de données TP : Les Arbres

< c elles-mêmes triées, se poursuit par c, puis par des valeurs > c elles-mêmes triées. D'où P(a).
Par récurrence, la propriété est vraie pour tout ABR. ■

A.5  Partie III, question 2 (sous-partie 3.2) : encadrement hn ≤ h ≤ 2hn

Première inégalité, .
hn ≤ h La hauteur noire ne compte, sur une branche, que les n÷uds
noirs, alors que la hauteur h compte tous les n÷uds de la branche la plus longue. Le nombre de
n÷uds noirs sur une branche est donc toujours inférieur ou égal au nombre total de n÷uds sur
cette branche, d'où hn ≤ h.
Seconde inégalité, .
h ≤ 2hn Par la propriété 3, deux n÷uds rouges ne se suivent jamais
directement sur une branche : entre deux n÷uds noirs consécutifs, il y a donc au plus un n÷ud
rouge intercalé. Ainsi, sur n'importe quelle branche de la racine à une feuille NIL, si l'on compte
k n÷uds noirs, on compte au plus k n÷uds rouges intercalés (dans le pire cas, un rouge entre
chaque paire de noirs consécutifs). La longueur totale de la branche est donc au plus k + k = 2k.
En particulier, pour la branche la plus longue (de longueur h), le nombre de n÷uds noirs qu'elle
contient est au moins h/2 ; or ce nombre de noirs sur n'importe quelle branche vaut exactement
hn (propriété 5, hauteur noire uniforme). D'où h/2 ≤ hn , soit h ≤ 2hn .
Conséquence. Comme un arbre binaire de hauteur noire hn contient au moins 2hn − 1 n÷uds
noirs (arbre binaire quasi complet sur les noirs), on a n ≥ 2hn − 1, donc hn = O(log n), puis
h ≤ 2hn = O(log n).

A.6  Partie III, question 8 (sous-partie 3.2) : pourquoi rouge et non noir
Si l'on coloriait le nouveau n÷ud en noir : ce n÷ud, inséré comme feuille (remplaçant une feuille
NIL, noire par convention), fait passer de 1 n÷ud noir (la NIL) à 2 n÷uds noirs (le nouveau
n÷ud, plus ses deux nouvelles feuilles NIL lles) sur les branches qui le traversent, sans que rien
ne change sur les autres branches de l'arbre. La propriété 5 (hauteur noire identique sur toutes
les branches) serait alors nécessairement violée, et ce de façon non locale : il faudrait recalculer
un décalage sur toute une portion de l'arbre.
Si l'on colorie le nouveau n÷ud en rouge : la hauteur noire de toutes les branches reste inchangée
(un n÷ud rouge ne compte pas dans la hauteur noire), donc la propriété 5 est automatiquement
préservée. Le seul risque est de violer la propriété 3 (pas deux rouges consécutifs), et seulement si
le père du nouveau n÷ud était déjà rouge : c'est un défaut strictement local, visible uniquement
en regardant le n÷ud, son père, son grand-père et son oncle, ce qui rend la réparation par les
cinq cas du cours possible en temps O(log n).

A.7  Partie III, question 9 : insertion de 10, 20, 30, 15 puis 25

On reprend l'arbre obtenu en cours après insertion de 10, 20, 30, 15 :

20 (noir)

10 (noir) 30 (noir)

15 (rouge)

Tournez la page S.V.P. 13/ 16

MP2I  Structures de données TP : Les Arbres

On insère à présent 25. Descente ABR : 25 > 20, puis 25 < 30 : 25 devient ls gauche de 30,
inséré en rouge. Son père (30) est noir : on est dans le cas 2
de l'aiguillage  rien à faire.
L'arbre nal est :

20 (noir)

10 (noir) 30 (noir)

15 (rouge)
25 (rouge)

On vérie : racine noire (✓) ; les deux rouges (15 et 25) n'ont pas d'enfant rouge (✓) ; hauteur
noire hn = 2 sur toutes les branches (✓) ; hauteur totale h = 2, bien ≤ 2hn = 4 (✓). L'ajout
d'une cinquième clé n'a nécessité aucune rotation : l'arbre reste de hauteur logarithmique, alors
qu'un ABR naïf construit avec des clés proches de l'ordre trié se serait déjà déséquilibré à ce
stade.

A.8  Partie IV : corrigés brefs

IV.1. Récurrence sur n : pour n = 1 (racine seule), 0 arête, formule vériée. Si un arbre à
n n÷uds a n − 1 arêtes, ajouter un nouveau n÷ud (forcément comme ls d'un n÷ud existant,
sinon l'arbre serait déconnecté ou aurait deux racines) ajoute exactement 1 arête et 1 n÷ud,
donc n → n + 1 n÷uds et (n − 1) + 1 = n arêtes : la formule n − 1 arêtes reste vraie.
IV.2. Le champ sibling d'un n÷ud pointe vers le ls suivant du même père. La racine de
l'arbre entier n'a pas de père, donc pas de frère : sibling = NULL. Cette propriété reste vraie
pour la racine de tout sous-arbre considéré isolément (elle n'a pas de frère dans ce sous-arbre ),
mais attention : dans l'arbre complet, ce même n÷ud peut très bien avoir un sibling non nul
s'il a des frères dans l'arbre englobant. La propriété ne concerne donc que la racine de l'arbre
global.
IV.3. Un arbre en  peigne  (chaque n÷ud n'a qu'un seul ls) donne un parcours préxe et un
BFS identiques, mais tout n÷ud y est d'arité ≤ 1. Dès qu'un n÷ud de hauteur ≥ 2 possède un
ls d'arité ≥ 2, le DFS descend immédiatement dans les petits-enfants avant de traiter le second
ls, alors que le BFS traite d'abord tous les n÷uds de profondeur 1 : les deux ordres divergent
nécessairement. La coïncidence n'est donc possible que pour un arbre liforme.
IV.4. Il existe 5 formes distinctes (nombre de Catalan C3 = 5) : peigne gauche total (3 niveaux),
peigne droit total, racine avec ls gauche ayant lui-même un ls droit, racine avec ls droit ayant
lui-même un ls gauche, racine à deux ls dont l'un a un ls supplémentaire... plus précisément
les 5 arbres binaires à 3 n÷uds correspondent aux 5 façons de parenthéser un produit de 3
facteurs.
IV.5. Oui : dans un ABR, descendre toujours à gauche depuis la racine mène à la plus petite
clé, et un n÷ud a une clé strictement supérieure à tout son sous-arbre gauche ; si ce n÷ud avait
un ls gauche, ce ls (et son sous-arbre) contiendrait une clé encore plus petite, contradiction
avec la minimalité. Algorithme : descendre à gauche tant que c'est possible.
IV.6. Recherche/insertion/suppression ABR : à chaque étape on descend d'un niveau, donc au
plus h comparaisons, d'où O(h). Dans un arbre bicolore, on a démontré (A.5) que h = O(log n),
d'où O(log n).

Tournez la page S.V.P. 14/ 16

MP2I  Structures de données TP : Les Arbres

IV.7. Une rotation ne modie jamais le nombre de n÷uds (c'est un simple réarrangement de
pointeurs, aucune création ni suppression). Elle peut modier la hauteur : par exemple une
rotation qui transforme un peigne de hauteur n − 1 en un arbre plus équilibré réduit strictement
la hauteur ; à l'inverse, elle peut la laisser inchangée sur un arbre déjà équilibré localement.
IV.8. Oui : racine noire (✓, propriété 2) ; pas de n÷ud rouge donc propriété 3 trivialement vraie
; les deux feuilles NIL sont noires par convention et à la même hauteur noire hn = 1 (propriété
5, vraie sur les deux seules branches racine-NIL).
IV.9. Oui, nécessairement : la hauteur noire est entièrement déterminée par le nombre de n÷uds
noirs sur n'importe quelle branche (propriété 5), et deux arbres bicolores portant sur le même
ensemble de clés n'ont pas forcément la même structure ni les mêmes couleurs par n÷ud selon
l'ordre d'insertion, mais on montre (hors programme, admis en TP) que hn = ⌊log2 (n + 1)⌋ n'est
pas un invariant absolu d'un ensemble de clés : deux arbres bicolores distincts sur les mêmes clés
peuvent en réalité avoir des hauteurs noires diérentes, tant que l'encadrement hn ≤ h ≤ 2hn
reste respecté. (Question ouverte à discuter en TD : donner un exemple sur 3 clés.)
IV.10. Du plus général au plus contraint : arbre n-aire (arité quelconque, aucune contrainte
d'ordre) ⊃ arbre binaire (arité ≤ 2, toujours aucune contrainte d'ordre) ⊃ ABR (arbre binaire +
contrainte d'ordre sur les clés, mais hauteur non garantie) ⊃ arbre bicolore (ABR + contrainte
de coloriage garantissant h = O(log n)).

A.9  Formulaire récapitulatif des complexités

Structure Recherche Insertion Hauteur garantie

Arbre O(N ) (parcours complet) O(1) (en tête de liste de ls) Aucune
n-
aire
quel-
conque
(LCRS)
Arbre O(N ) O(N ) (position libre) Aucune
bi-
naire
quel-
conque
ABR O(h), h pouvant valoir n − 1 O(h) Aucune (pire cas O(n))
non
équili-
bré
Arbre O(log n) O(log n) h ≤ 2 log2 (n + 1)
bi-
col-
ore

Tournez la page S.V.P. 15/ 16

MP2I  Structures de données TP : Les Arbres

Cas d'insertion (arbre bicolore) Condition et action

Cas 1 N est la racine ⇒ recolorier N en noir.
Cas 2 Parent de N noir ⇒ rien à faire.
Cas 3 Parent rouge, oncle rouge ⇒ recolorier parent et on-
cle en noir, grand-parent en rouge, relancer depuis le
grand-parent.
Cas 4 Parent rouge, oncle noir, conguration en zig-zag ⇒
rotation au niveau du parent pour se ramener au cas
5.
Cas 5 Parent rouge, oncle noir, conguration en ligne droite
⇒ rotation au niveau du grand-parent, puis recoloriage
(parent en noir, grand-parent en rouge). Cas terminal.

Fin de l'épreuve.

Tournez la page S.V.P. 16/ 16