Algorithmique · Écoles d'ingénieurs — ENSIAS

Arbres binaires et arbres de recherche

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

Un arbre binaire est une structure de données hiérarchique où chaque nœud possède au plus deux enfants (gauche et droite).

Hauteur ( $h$ ) : Nombre de niveaux de l'arbre.
ABR (Arbre Binaire de Recherche) : Pour tout nœud $N$ , les valeurs du sous-arbre gauche sont inférieures à $N$ et celles du sous-arbre droit sont supérieures à $N$ .
Parcours :
- Préfixe (NLR) : Racine $\rightarrow$ Gauche $\rightarrow$ Droite.
- Infixe (LNR) : Gauche $\rightarrow$ Racine $\rightarrow$ Droite (donne les valeurs triées dans un ABR).
- Postfixe (LRN) : Gauche $\rightarrow$ Droite $\rightarrow$ Racine.

Méthodes à maîtriser

Insertion : Comparer la valeur à insérer avec la racine, descendre à gauche si plus petite, à droite si plus grande.
Recherche : Algorithme récursif en $O(h)$ .
Suppression :
1. Feuille : Supprimer simplement.
2. Un enfant : Remplacer par son enfant.
3. Deux enfants : Remplacer par le successeur immédiat (le plus petit du sous-arbre droit).

Exemples corrigés

Insertion de 15 dans un ABR : Si 15 < racine, aller à gauche, sinon à droite, répéter jusqu'à trouver un emplacement vide.
Parcours infixe : Permet de vérifier si un arbre est un ABR (la liste doit être triée).

Erreurs fréquentes

Confondre la hauteur (nombre de niveaux) et le nombre de nœuds.
Oublier le cas de base dans les fonctions récursives (arbre vide).
Dans la suppression, oublier de réorganiser les liens après avoir trouvé le successeur.

L'essentiel du cours

Un arbre binaire est une structure de données hiérarchique où chaque nœud possède au plus deux enfants (gauche et droite).

Hauteur ($h$) : Nombre de niveaux de l'arbre.
ABR (Arbre Binaire de Recherche) : Pour tout nœud $N$, les valeurs du sous-arbre gauche sont inférieures à $N$ et celles du sous-arbre droit sont supérieures à $N$.
Parcours :
- Préfixe (NLR) : Racine $\rightarrow$ Gauche $\rightarrow$ Droite.
- Infixe (LNR) : Gauche $\rightarrow$ Racine $\rightarrow$ Droite (donne les valeurs triées dans un ABR).
- Postfixe (LRN) : Gauche $\rightarrow$ Droite $\rightarrow$ Racine.

Méthodes à maîtriser

Insertion : Comparer la valeur à insérer avec la racine, descendre à gauche si plus petite, à droite si plus grande.
Recherche : Algorithme récursif en $O(h)$.
Suppression :
1. Feuille : Supprimer simplement.
2. Un enfant : Remplacer par son enfant.
3. Deux enfants : Remplacer par le successeur immédiat (le plus petit du sous-arbre droit).

Exemples corrigés

Insertion de 15 dans un ABR : Si 15 < racine, aller à gauche, sinon à droite, répéter jusqu'à trouver un emplacement vide.
Parcours infixe : Permet de vérifier si un arbre est un ABR (la liste doit être triée).

Erreurs fréquentes

Confondre la hauteur (nombre de niveaux) et le nombre de nœuds.
Oublier le cas de base dans les fonctions récursives (arbre vide).
Dans la suppression, oublier de réorganiser les liens après avoir trouvé le successeur.

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Arbres binaires et arbres de recherche

1/4

Quel est le parcours qui visite la racine en dernier ?

❓ Questions fréquentes

Qu'est-ce qu'un arbre binaire complet ?

Un arbre binaire est dit complet si tous ses niveaux sont remplis, à l'exception éventuellement du dernier qui doit être rempli de gauche à droite.

💡 À retenir : Un arbre complet optimise l'espace mémoire et garantit une hauteur minimale de $\log_2(n)$ .

Un arbre binaire est dit complet si tous ses niveaux sont remplis, à l'exception éventuellement du dernier qui doit être rempli de gauche à droite.

💡 À retenir : Un arbre complet optimise l'espace mémoire et garantit une hauteur minimale de $\log_2(n)$.

Kifach n-3ref wach chajara ABR awla la?

Applique le parcours infixe sur ta structure.
Si la liste des valeurs obtenue est strictement triée par ordre croissant, alors c'est un ABR.
Sinon, ce n'est pas un ABR.

💡 À retenir : Le parcours infixe d'un ABR donne toujours une suite triée.

Quelle est la complexité de la recherche dans un ABR ?

La complexité est $O(h)$ , où $h$ est la hauteur de l'arbre. Dans le meilleur des cas (arbre équilibré), $h = \log_2(n)$ , donc $O(\log_2(n))$ . Dans le pire des cas (arbre dégénéré en liste), $h = n$ , donc $O(n)$ .

💡 À retenir : L'équilibre de l'arbre est crucial pour la performance.

La complexité est $O(h)$, où $h$ est la hauteur de l'arbre. Dans le meilleur des cas (arbre équilibré), $h = \log_2(n)$, donc $O(\log_2(n))$. Dans le pire des cas (arbre dégénéré en liste), $h = n$, donc $O(n)$.

💡 À retenir : L'équilibre de l'arbre est crucial pour la performance.

Chno hiya l-farq bin arbre binaire w-ABR?

L'arbre binaire est juste une structure de stockage sans règle d'ordre. L'ABR impose que tout élément à gauche est plus petit que la racine et tout élément à droite est plus grand.

💡 À retenir : L'ABR est conçu spécifiquement pour accélérer la recherche.

Comment calculer la hauteur d'un arbre récursivement ?

Si l'arbre est vide, hauteur = 0.
Sinon, hauteur = 1 + max(hauteur(gauche), hauteur(droite)).

💡 À retenir : La récursivité est l'outil naturel pour parcourir les arbres.

Wach momkin n-lqaw 2 dyal les nœuds b-nafs l-valeur f-ABR?

En général, les ABR standards n'acceptent pas les doublons. Si tu dois en gérer, tu peux soit les ignorer, soit décider de les mettre toujours à droite (ou à gauche) de la racine.

💡 À retenir : La convention doit être cohérente dans tout l'algorithme.

Pourquoi utilise-t-on la récursivité pour les arbres ?

Parce qu'un arbre est une structure définie récursivement : un arbre est composé d'une racine et de deux sous-arbres qui sont eux-mêmes des arbres.

💡 À retenir : La récursivité simplifie l'écriture du code par rapport aux boucles itératives.

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

Le préfixe traite la racine avant les enfants (utile pour copier un arbre). Le postfixe traite la racine après les enfants (utile pour supprimer un arbre ou calculer sa taille).

💡 À retenir : L'ordre de visite change selon le besoin applicatif.

Kifach n-supprimiw 3oqda 3ndha 2 dyal l-wlad?

Trouve le successeur (le plus petit élément du sous-arbre droit).
Remplace la valeur du nœud à supprimer par celle du successeur.
Supprime le successeur (qui a au plus un enfant).

💡 À retenir : Cette méthode préserve la propriété ABR.

Est-ce qu'un arbre avec un seul nœud est un ABR ?

Oui, par définition, un arbre avec un seul nœud (la racine) respecte les conditions de l'ABR car il n'y a pas de sous-arbres à comparer.

💡 À retenir : La base de la récursivité est toujours l'arbre à un seul nœud.

C'est quoi un arbre dégénéré ?

C'est un arbre où chaque nœud n'a qu'un seul enfant, ce qui le fait ressembler à une liste chaînée.

💡 À retenir : Dans ce cas, la recherche devient $O(n)$ , ce qui annule l'avantage de l'ABR.

C'est un arbre où chaque nœud n'a qu'un seul enfant, ce qui le fait ressembler à une liste chaînée.

💡 À retenir : Dans ce cas, la recherche devient $O(n)$, ce qui annule l'avantage de l'ABR.

Comment parcourir un arbre en largeur (BFS) ?

On utilise une file (FIFO) : on insère la racine, puis tant que la file n'est pas vide, on retire un nœud, on le traite, et on ajoute ses enfants dans la file.

💡 À retenir : Le BFS explore l'arbre niveau par niveau.

✍️ Exercices type examen national

Exercice 1

Soit un ABR contenant les valeurs suivantes insérées dans cet ordre : 50, 30, 70, 20, 40, 60, 80.

Dessiner l'arbre résultant.
Donner le résultat du parcours infixe.
Si on supprime la racine (50), quel nœud prend sa place selon la règle du successeur ?

Voir la correction détaillée : inscription gratuite

Exercice 2

Écrire une fonction récursive hauteur(nœud) en pseudo-code qui calcule la hauteur d'un arbre binaire.

Voir la correction détaillée : inscription gratuite

Exercice 3

Expliquer pourquoi le parcours infixe d'un ABR est utile pour le tri.

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Algorithmique

Introduction à l'algorithmique et complexité Structures de données linéaires : Listes, Piles et Files Récursivité et méthodes de conception d'algorithmes Algorithmes de tri et de recherche Structures de données avancées : Tas (Heaps) et Files de priorité Tables de hachage (Hash Tables)Graphes : Représentations et parcours (BFS, DFS)Algorithmes sur les graphes : Plus courts chemins et arbres couvrants Programmation dynamique Algorithmes gloutons Introduction à la théorie de la complexité (P vs NP)