Arbres binaires, arbres binaires de recherche et tas : cours et exercices corrigés de prépa

Q: Comment calculer la hauteur d'un arbre binaire ?

La hauteur est la plus grande profondeur d'un nœud, la profondeur étant le nombre d'arêtes depuis la racine. Avec cette convention, une feuille a la hauteur 0 et l'arbre vide -1 : `hauteur(A)` renvoie -1 si `A` est vide, sinon 1 + max des hauteurs des deux sous-arbres, en O(n). Certains énoncés comptent les niveaux, ce qui ajoute 1 : au concours, on applique la définition de l'énoncé.

Q: Quelle est la différence entre parcours préfixe, infixe et postfixe ?

Les trois visitent le sous-arbre gauche avant le droit ; ils diffèrent par le moment où l'on note la racine : avant ses sous-arbres (préfixe), entre les deux (infixe), après (postfixe). Le parcours infixe d'un arbre binaire de recherche donne ses valeurs dans l'ordre croissant. On les écrit avec une liste accumulateur remplie par `append`, en O(n) ; des concaténations répétées coûteraient O(nh).

Q: Comment faire un parcours en largeur d'un arbre binaire en Python ?

On utilise une file : `F = deque()` du module `collections`, on y met l'arbre, puis, tant qu'elle n'est pas vide, on retire le plus ancien sous-arbre par `F.popleft()`, on note sa racine et on ajoute ses sous-arbres non vides, le gauche d'abord. Le parcours est en O(n). Avec une liste et `pop(0)`, chaque retrait décale toute la file et le parcours devient quadratique.

Q: Quelle est la complexité de la recherche dans un arbre binaire de recherche ?

Elle est en O(h) : chaque comparaison fait descendre d'un niveau. C'est O(log n) seulement si la hauteur est minimale, et O(n) pour un peigne, obtenu en insérant des données déjà triées. Construire un ABR par n insertions coûte O(n^2) au pire et O(n log n) au meilleur : la construction n'est jamais linéaire.

Q: Comment insérer et extraire dans un tas ?

Dans un tas-max rangé dans une liste, les fils de l'indice i sont en 2i + 1 et 2i + 2, son père en (i - 1) // 2. Pour insérer, on ajoute l'élément en fin de liste et on le fait remonter tant qu'il dépasse son père. Pour extraire le maximum, on met le dernier élément à la racine et on le fait descendre vers le plus grand de ses fils. Chaque opération coûte O(log n) au pire et O(1) au meilleur.

Q: Comment utiliser un tas comme file de priorité ?

On range des couples (priorité, numéro d'arrivée) et l'on retire toujours la racine. Dans le tas-max du cours, on range (priorité, -numéro) : à priorité égale, c'est le premier arrivé qui sort, et l'on ne compare jamais les données elles-mêmes. Dans un tas-min, on range (priorité, numéro). Ajouts et retraits coûtent O(log n), et l'on construit un tas à partir d'une liste en O(n) par descentes.

MP
PSI
TSI 2
Offert à l'essai

Vocabulaire des arbres, hauteur et profondeur, arbres binaires représentés par des listes, fonctions récursives, parcours préfixe, infixe, postfixe et en largeur, arbres binaires de recherche (recherche, insertion, création, hauteur, suppression), tas (insertion, extraction, construction), file de priorité, tri par tas, complexités.

17méthodes
34exercices corrigés
3problèmes
21pièges
57figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Les arbres binaires sont au programme de deuxième année en MP, PSI et TSI au Maroc. On les représente en Python par des listes : l'arbre vide est [], un nœud est [r, G, D]. Sur un arbre de $n$ nœuds et de hauteur $h$ , comptée en arêtes (une feuille a la hauteur 0, l'arbre vide $-1$ ), une fonction récursive coûte $O(n)$ et sa pile $O(h)$ . On le parcourt en profondeur (préfixe, infixe, postfixe) ou en largeur, avec une file deque. Dans un arbre binaire de recherche (ABR), la recherche et l'insertion coûtent $O(h)$ , entre $O(\log n)$ et $O(n)$ selon la forme de l'arbre. Un tas est un arbre binaire parfait rangé dans une liste : il donne le maximum en $O(1)$ , l'ajoute ou le retire en $O(\log n)$ , et sert de file de priorité et de base au tri par tas. Tu y trouves les définitions, les codes Python avec leurs preuves et leurs complexités au meilleur et au pire cas, puis des exercices corrigés, dont des sujets du CNC (arbre de Huffman, arbre des suffixes).

Ce que tu sauras faire

Une liste range des données les unes après les autres. Beaucoup de données sont pourtant hiérarchiques : des dossiers qui contiennent des dossiers, une famille et ses générations, une expression et ses sous-expressions. Les arbres les représentent, et deux arbres particuliers, l'arbre binaire de recherche et le tas, permettent de chercher, d'ajouter et de retirer bien plus vite qu'avec une liste. À la fin de ce chapitre, tu dois savoir :

employer le vocabulaire des arbres et calculer la profondeur d'un nœud et la hauteur d'un arbre, en lisant la convention de l'énoncé ;
représenter un arbre binaire par une liste [r, G, D] et écrire une fonction récursive sur un arbre ;
écrire et dérouler les parcours préfixe, infixe, postfixe et en largeur ;
rechercher, insérer, construire et trier avec un arbre binaire de recherche, et relier le coût à la hauteur ;
représenter un tas par une liste, y insérer, en extraire la racine, le construire, et trier par tas ;
donner la complexité de chaque opération au meilleur et au pire cas, pile d'appels comprise.

L'essentiel : Vocabulaire et conventions Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Définitions

Racine : le nœud sans père ; feuille : nœud sans fils ; nœud interne : nœud qui a au moins un fils.
Degré d'un nœud : son nombre de fils ; degré (ou ordre) d'un arbre : le plus grand degré de ses nœuds ; taille : nombre de nœuds.
Profondeur d'un nœud : nombre d'arêtes depuis la racine (racine : 0).
Hauteur : plus grande profondeur ; feuille seule : 0 ; arbre vide : $-1$ .

Convention des sujets qui comptent les niveaux : $h_{\text{niveaux}} = h + 1$ . Au concours, on applique la définition de l'énoncé.

Une méthode du chapitre Extrait gratuit

Méthode Passer de l'arbre parfait au tableau, et vérifier qu'une liste est un tas

Quand l’utiliser

« Représenter le tas par une liste », « donner l'indice du père », « vérifier qu'une liste est un tas ».

Rappel de cours

Fils de $i$ : $2i + 1$ et $2i + 2$ ; père de $i \geq 1$ : $(i - 1) // 2$ ; feuilles : indices $n // 2$ à $n - 1$ ; hauteur $\lfloor \log_2 n \rfloor$ . Tas-max : chaque élément est inférieur ou égal à son père (cours, sections 10.1 et 10.2).

Démarche

Numéroter les nœuds niveau par niveau, de gauche à droite, à partir de 0.
Pour vérifier un tas, comparer chaque T[i] ( $i \geq 1$ ) à son père.
S'arrêter au premier défaut.

Rédaction type

« Chaque nœud autre que la racine a un père : vérifier T[(i - 1) // 2] >= T[i] pour $1 \leq i < n$ suffit, puisque la relation est alors vraie entre chaque père et chacun de ses fils. $O(n)$ au pire, $O(1)$ au meilleur. »

Exemple traité

Dans un tas de 12 éléments, le père de l'indice 11 est l'indice 5 ; les fils de l'indice 4 sont les indices 9 et 10 ; les feuilles sont les indices 6 à 11, soit 6 feuilles ; la hauteur est 3. La liste [9, 7, 8, 7, 8, 1] n'est pas un tas-max : l'élément 8 d'indice 4 dépasse son père 7.

Erreurs fréquentes

(i - 1) / 2 : un flottant.
Mélanger les conventions d'un tableau qui commence à 1 et d'une liste Python.
Croire qu'un arbre parfait est un tas, ou qu'un tas est trié.

Pour s’entraîner

Exercices 11 et 13.

Un exercice corrigé Extrait gratuit

Exercice Est-ce un tas ? ★☆☆

On considère les listes suivantes, vues comme des arbres binaires parfaits stockés dans un tableau (fils de l'indice $i$ en $2i + 1$ et $2i + 2$ ).

T1 = [90, 40, 70, 10, 30, 60, 50]
T2 = [1, 3, 2, 7, 4, 5]
T3 = [2, 4, 6, 8, 10, 12]
T4 = [3, 5, 8, 7, 10, 6, 11, 4, 9]
T5 = [9, 5, 8, 6, 1]

Pour chaque liste, dire si elle est un tas-max, un tas-min, ou ni l'un ni l'autre, en dessinant l'arbre.
Écrire une fonction est_tas_min(T) sur le modèle de est_tas, et vérifier les réponses.
Donner la complexité de est_tas_min au meilleur et au pire cas.

Indications

Méthode 13 : le père de l'indice $i \geq 1$ est à l'indice $(i - 1) // 2$ ; il suffit de comparer chaque élément à son père.
Une liste triée dans l'ordre croissant a chaque père avant ses fils.

Correction détaillée

Question 1.

T1 est un tas-max : 40 et 70 sont sous 90, 10 et 30 sous 40, 60 et 50 sous 70.
T2 est un tas-min : 3 et 2, fils de 1, sont plus grands que lui ; 7 et 4 sont plus grands que leur père 3 ; 5 est plus grand que son père 2.
T3 est un tas-min : dans une liste croissante, le père, d'indice plus petit, est plus petit que ses fils.
T4 n'est ni l'un ni l'autre : 5 est sous 3 (pas tas-max), et 4, fils de 7 (indice $7$ , père $(7 - 1) // 2 = 3$ ), est plus petit que son père (pas tas-min). Avoir la forme d'un arbre parfait ne suffit pas à faire un tas.
T5 n'est ni l'un ni l'autre : 6, à l'indice 3, est plus grand que son père 5 (pas tas-max) ; 5 est sous 9 (pas tas-min).

Question 2. Analyse. On reprend est_tas en renversant la comparaison : un tas-min est mal formé dès qu'un élément est strictement plus petit que son père.

def est_tas_min(T):
    # True si la liste T est un tas-min : chaque
    # élément est supérieur ou égal à son père
    for i in range(1, len(T)):
        if T[(i - 1) // 2] > T[i]:
            return False
    return True

for T in [T1, T2, T3, T4, T5]:
    print(est_tas(T), est_tas_min(T))

Le programme affiche :

True False
False True
False True
False False
False False

Question 3. Au pire cas (la liste est un tas-min), la boucle fait $n - 1$ tours de coût constant : $O(n)$ . Au meilleur cas, la première comparaison échoue (T[1] < T[0]) : un seul tour, $O(1)$ .

Méthodes à retenir

Un tas, c'est la forme (arbre parfait, donc une liste sans trou) et l'ordre entre chaque père et ses fils. On le vérifie en comparant chaque élément à son père. Voir la méthode 13 et le cours, section 10.2.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 17 méthodes, 21 pièges corrigés, la carte mentale, 34 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Une question ? WhatsApp

Plan du cours

1. Pourquoi des arbres
- 1.1 Des données hiérarchiques
- 1.2 Chercher vite dans des données qui changent
2. Vocabulaire des arbres
- 2.1 Nœuds, racine, feuilles
- 2.2 Degré, ordre, taille
- 2.3 Profondeur, niveau, hauteur
- 2.4 Une autre convention
3. Arbres binaires
- 3.1 Définition
- 3.2 Arbres binaires particuliers
4. Représenter un arbre binaire par une liste
- 4.1 La liste [r, G, D]
- 4.2 Les fonctions d'interface
- 4.3 Partage et copie
- 4.4 D'autres représentations
5. Fonctions récursives sur un arbre binaire
- 5.1 Le schéma
- 5.2 Taille, hauteur, feuilles
- 5.3 Profondeur d'un nœud
- 5.4 Terminaison et correction
- 5.5 Coût et pile d'appels
6. Taille et hauteur
- 6.1 Encadrer la taille
- 6.2 Hauteur minimale et hauteur maximale
- 6.3 Arbres binaires stricts
- 6.4 Combien d'arbres binaires
7. Parcours en profondeur
- 7.1 Trois ordres de visite
- 7.2 Le code
- 7.3 Le coût caché des concaténations
- 7.4 Arbre d'expression
- 7.5 Reconstruire un arbre
8. Parcours en largeur
- 8.1 L'idée
- 8.2 Le code et sa trace
- 8.3 Coût, et le piège de pop(0)
- 8.4 Pas de marquage
9. Arbres binaires de recherche
- 9.1 Définition
- 9.2 Le parcours infixe est croissant
- 9.3 Rechercher, minimum, maximum
- 9.4 Insérer
- 9.5 Construire un ABR, trier par ABR
- 9.6 La hauteur décide de tout
- 9.7 Les complexités d'un ABR
- 9.8 Pour aller plus loin : supprimer une valeur
10. Tas
- 10.1 Définition
- 10.2 Un tas dans une liste
- 10.3 Accéder au maximum
- 10.4 Insérer : la remontée
- 10.5 Extraire la racine : la descente
- 10.6 Construire un tas
- 10.7 File de priorité
- 10.8 Supprimer une valeur quelconque
11. Le tri par tas
- 11.1 L'algorithme
- 11.2 Correction et complexité
- 11.3 Comparaison avec les tris du chapitre 2
12. Complexités du chapitre
- 12.1 Le tableau
- 12.2 En fonction de $n$ ou de $h$

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Lire une définition d'énoncé et l'appliquer à un petit arbre
Passer d'un dessin à la liste [r, G, D], et inversement
Écrire une fonction récursive sur un arbre binaire et la prouver
Calculer la profondeur d'un nœud ou lister un niveau
Démontrer une propriété d'arbre par récurrence
Écrire et dérouler les parcours en profondeur
Écrire le parcours en largeur avec une file et en donner la trace
Évaluer et écrire un arbre d'expression
Tester si un arbre est un ABR
Rechercher une valeur, le minimum, le maximum dans un ABR
Insérer dans un ABR, construire, trier
Supprimer une valeur dans un ABR
Passer de l'arbre parfait au tableau, et vérifier qu'une liste est un tas
Insérer dans un tas et extraire la racine
Construire un tas et trier par tas
Justifier une complexité sur un arbre
Supprimer une valeur quelconque d'un tas

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (13)

Lire un arbre : vocabulaire et mesures
Du dessin à la liste, et retour
Taille, feuilles, hauteur, maximum
Profondeur d'une valeur, liste d'un niveau
Les trois parcours à la main
Le parcours en largeur et sa file
Notations préfixée et postfixée d'une expression
ABR ou non
Construire un ABR à la main
Minimum, maximum, recherche
Est-ce un tas ?
Insérer et extraire à la main
Indices et feuilles d'un tas

Entraînement (16)

Taille, hauteur et feuilles : les inégalités
Combien d'arbres binaires à $n$ nœuds
Évaluer et écrire un arbre d'expression
Reconstruire un arbre à partir de deux parcours
Un arbre de décision
Le produit d'une chaîne de matrices suit un arbre
Un arbre donné par les pères
pop(0) contre deque
Parcours par concaténation
Recherche et insertion en boucle dans un ABR
Trier par ABR, et l'ordre d'insertion
Successeur et prédécesseur dans un ABR
Construire un tas : deux méthodes
Le tri par tas pas à pas
Les $k$ plus grandes valeurs
Supprimer une valeur quelconque d'un tas

Approfondissement (5)

Supprimer dans un ABR
L'arbre des solutions et l'élagage
Pourquoi construire un tas coûte $O(n)$
La médiane d'un flux avec deux tas
Un ABR de hauteur minimale

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Arbre de Huffman : construction, codes, compression et décompression
CNC 2017, filières MP, PSI et TSI, épreuve d'informatique, partie II « Programmation Python : la compression de Huffman », questions II.5-b, II.6, II.7 et II.8, complétée
L'arbre des suffixes d'une séquence d'ADN
CNC 2018, filière MP, épreuve d'informatique, partie II « Bioinformatique : Recherche d'un motif », questions 9 et 10, complétée
L'arbre binaire de recherche d'un mot
CCINP 2021, filière MP, option informatique, partie III « Étude des classes sylvestres », questions 19 à 24, transposée en Python, complétée

Questions fréquentes

Comment calculer la hauteur d'un arbre binaire ?

La hauteur est la plus grande profondeur d'un nœud, la profondeur étant le nombre d'arêtes depuis la racine. Avec cette convention, une feuille a la hauteur 0 et l'arbre vide $-1$ : hauteur(A) renvoie $-1$ si A est vide, sinon $1 + \max$ des hauteurs des deux sous-arbres, en $O(n)$ . Certains énoncés comptent les niveaux, ce qui ajoute 1 : au concours, on applique la définition de l'énoncé.

Quelle est la différence entre parcours préfixe, infixe et postfixe ?

Les trois visitent le sous-arbre gauche avant le droit ; ils diffèrent par le moment où l'on note la racine : avant ses sous-arbres (préfixe), entre les deux (infixe), après (postfixe). Le parcours infixe d'un arbre binaire de recherche donne ses valeurs dans l'ordre croissant. On les écrit avec une liste accumulateur remplie par append, en $O(n)$ ; des concaténations répétées coûteraient $O(nh)$ .

Comment faire un parcours en largeur d'un arbre binaire en Python ?

On utilise une file : F = deque() du module collections, on y met l'arbre, puis, tant qu'elle n'est pas vide, on retire le plus ancien sous-arbre par F.popleft(), on note sa racine et on ajoute ses sous-arbres non vides, le gauche d'abord. Le parcours est en $O(n)$ . Avec une liste et pop(0), chaque retrait décale toute la file et le parcours devient quadratique.

Quelle est la complexité de la recherche dans un arbre binaire de recherche ?

Elle est en $O(h)$ : chaque comparaison fait descendre d'un niveau. C'est $O(\log n)$ seulement si la hauteur est minimale, et $O(n)$ pour un peigne, obtenu en insérant des données déjà triées. Construire un ABR par $n$ insertions coûte $O(n^2)$ au pire et $O(n \log n)$ au meilleur : la construction n'est jamais linéaire.

Comment insérer et extraire dans un tas ?

Dans un tas-max rangé dans une liste, les fils de l'indice $i$ sont en $2i + 1$ et $2i + 2$ , son père en $(i - 1) // 2$ . Pour insérer, on ajoute l'élément en fin de liste et on le fait remonter tant qu'il dépasse son père. Pour extraire le maximum, on met le dernier élément à la racine et on le fait descendre vers le plus grand de ses fils. Chaque opération coûte $O(\log n)$ au pire et $O(1)$ au meilleur.

Comment utiliser un tas comme file de priorité ?

On range des couples (priorité, numéro d'arrivée) et l'on retire toujours la racine. Dans le tas-max du cours, on range (priorité, $-$ numéro) : à priorité égale, c'est le premier arrivé qui sort, et l'on ne compare jamais les données elles-mêmes. Dans un tas-min, on range (priorité, numéro). Ajouts et retraits coûtent $O(\log n)$ , et l'on construit un tas à partir d'une liste en $O(n)$ par descentes.

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.