NSI (Spé) — Structures de données
Arbres binaires et arbres binaires de recherche
Arbres binaires, vocabulaire, arbres binaires de recherche (ABR), opérations et propriétés
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Après les structures linéaires, voici les structures **hiérarchiques**. Un **arbre binaire** organise les données comme un arbre généalogique inversé : une **racine** en haut, et chaque nœud possède **au plus deux fils** (gauche et droit). Les nœuds sans fils sont les **feuilles**. L'**arbre binaire de recherche (ABR)** ajoute une règle d'or : à gauche, tout est **plus petit** que le nœud ; à droite, tout est **plus grand**. Cette discipline transforme la recherche en une **dichotomie** : à chaque comparaison, on élimine la moitié des candidats. Résultat : recherche, insertion et suppression en $O(\log n)$… **à condition que l'arbre reste équilibré**. Mal construit (un « peigne »), il dégénère en liste chaînée et retombe à $O(n)$.
Un **arbre binaire** est un ensemble de **nœuds** reliés hiérarchiquement : un nœud **parent** pointe vers au plus deux **fils** (gauche et droit). Tout part de la **racine** ; les nœuds terminaux, sans fils, sont les **feuilles**. Maîtriser ce vocabulaire est indispensable avant d'écrire le moindre algorithme.
- **Racine :** l'unique nœud sans parent, au sommet. Un arbre **vide** n'a pas de racine.
- **Feuille :** nœud sans aucun fils. **Nœud interne :** nœud ayant au moins un fils.
- **Profondeur** d'un nœud : nombre d'arêtes jusqu'à la racine (la racine est à la profondeur $0$).
- **Hauteur** de l'arbre : profondeur maximale d'une feuille. Une racine seule a une hauteur de $0$ ; un arbre vide, $-1$ (convention).
- **Taille :** nombre total de nœuds. Un arbre de hauteur $h$ a entre $h+1$ et $2^{h+1}-1$ nœuds.
Exemple
Arbre de racine 5, fils gauche 3, fils droit 7, et 3 a pour fils 1 et 4. Taille $= 5$ nœuds, feuilles $= \{1, 4, 7\}$, hauteur $= 2$ (le chemin 5 → 3 → 1 traverse 2 arêtes).
Piège à éviter
Ne confonds pas **profondeur** (propriété d'un nœud) et **hauteur** (propriété de l'arbre entier). Et attention : une racine seule a une hauteur de $0$, pas de $1$.
On représente un arbre par une **classe Noeud** portant une valeur et ses deux sous-arbres ; un arbre **vide** vaut None. Comme la structure est récursive (un arbre contient des sous-arbres), presque tous les algorithmes le sont aussi : un **cas de base** (arbre vide) et deux **appels récursifs** sur les fils.
- class Noeud avec valeur, gauche=None, droit=None ; un **arbre vide** vaut None.
- **Taille :** 0 si vide, sinon 1 + taille(gauche) + taille(droit).
- **Hauteur :** -1 si vide, sinon 1 + max(hauteur(gauche), hauteur(droit)).
- Un nœud est une **feuille** si gauche is None et droit is None.
- Tout algorithme suit le **même schéma récursif** : traiter le cas vide, puis combiner les résultats des deux fils.
Exemple
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def taille(a):
if a is None:
return 0
return 1 + taille(a.gauche) + taille(a.droit)
Piège à éviter
**Oublier le cas de base** (a is None) provoque une AttributeError (on lit .gauche sur None) ou une récursion sans fin. Le test du vide vient toujours en premier.
Un **ABR** est un arbre binaire **ordonné** : pour chaque nœud, toutes les valeurs à **gauche** sont inférieures, toutes celles à **droite** sont supérieures. Cet invariant, vrai à chaque niveau, permet de chercher une valeur sans explorer tout l'arbre.
- **Propriété ABR :** pour tout nœud $n$, sous-arbre gauche $<$ $n$.valeur $<$ sous-arbre droit.
- **Recherche :** comparer à la racine, puis descendre à gauche (si plus petit) ou à droite (si plus grand).
- **Insertion :** on descend comme pour une recherche, puis on crée une **feuille** à la place vide trouvée.
- Le **parcours infixe** (gauche, racine, droit) restitue les valeurs **dans l'ordre croissant**.
- **Suppression**, 3 cas : feuille (on retire) ; un fils (on le remonte) ; deux fils (on remplace par le min du sous-arbre droit).
Exemple
Dans l'ABR (racine 5, à gauche 3 avec fils 1 et 4, à droite 7 avec fils 6 et 9), chercher 4 : 4 < 5 → gauche (3), 4 > 3 → droite (4) → trouvé en 3 comparaisons au lieu de parcourir les 7 nœuds.
Piège à éviter
Un **arbre binaire** quelconque n'est **pas** un ABR : sans la contrainte d'ordre, le parcours infixe ne donne pas de tri et la recherche dichotomique est impossible.
Toute la performance d'un ABR tient à sa **hauteur** : la recherche descend d'un niveau par comparaison. Bien équilibré, il offre $O(\log n)$ ; dégénéré en « peigne », il retombe à $O(n)$. L'**ordre d'insertion** décide de tout.
- **ABR équilibré :** hauteur $\approx \log_2 n$, donc recherche et insertion en $O(\log n)$.
- **ABR dégénéré (peigne) :** hauteur $= n-1$, recherche en $O(n)$ — autant qu'une liste chaînée.
- Insérer $1, 2, 3, 4, 5$ dans l'ordre crée un **peigne droit** (le pire cas).
- Insérer $3, 1, 5, 2, 4$ crée un arbre **bien mieux équilibré**.
- Pour garantir l'équilibre, on utilise des arbres **AVL** ou **rouge-noir** (hors programme, mais à connaître de nom).
- Un arbre binaire **parfait** de hauteur $h$ contient exactement $2^{h+1}-1$ nœuds.
Exemple
Avec $n = 1\,000\,000$ : un ABR équilibré a une hauteur $\approx 20$ (car $\log_2 10^6 \approx 20$), donc $\approx 20$ comparaisons ; un peigne en demanderait jusqu'à un million.
Piège à éviter
Insérer des données **déjà triées** dans un ABR simple est le **pire scénario** : on obtient un peigne et on perd tout l'avantage du $O(\log n)$.
Quiz - Arbres binaires et ABR
10 questions
Questions fréquentes
Les points clés à retenir sur Arbres binaires et arbres binaires de recherche, extraits du quiz de révision.
Qu'est-ce qu'une feuille dans un arbre binaire ?
Réponse :
Un nœud sans fils
Une feuille est un nœud sans fils (ni fils gauche, ni fils droit). C'est un nœud terminal de l'arbre.
Quelle est la hauteur d'un arbre réduit à sa racine ?
Réponse :
0
Un arbre réduit à sa racine a une hauteur de 0 : la profondeur maximale est celle de la racine, qui est 0.
Dans un ABR, où se trouvent les valeurs plus grandes que la racine ?
Réponse :
Dans le sous-arbre droit
Par définition d'un ABR, toutes les valeurs supérieures à la racine se trouvent dans le sous-arbre droit.
Quel parcours d'un ABR donne les valeurs triées en ordre croissant ?
Réponse :
Infixe
Le parcours infixe (gauche, racine, droit) visite les nœuds d'un ABR dans l'ordre croissant de leurs valeurs.