Fiche de révision : Structures hiérarchiques et parcours d'arbres

📋 Plan du Cours

1. Définition arbre
2. Nœuds et racine
3. Feuilles et nœuds internes
4. Arbre binaire
5. Profondeur et hauteur
6. Sous-arbre enraciné
7. Inégalités hauteur/nœuds
8. Transformation en arbre binaire
9. Arbres en informatique
10. Parcours en profondeur
11. Parcours en largeur
12. Complexité tri par comparaison

📖 1. Définition arbre

🔑 Notions clés & Définitions

• Arbre (A) : Ensemble non vide muni d’une relation binaire R vérifiant l’unicité de la racine et la relation de parenté.
  Définition : Un arbre est un ensemble non vide où il existe un unique élément racine r tel que tout autre élément x est relié à r via une chaîne de relations parent-enfant.

• Racine (r) : Élément de l’arbre qui n’a pas de parent.
  Point essentiel : La racine est le point de départ de toutes les relations dans l’arbre.

• Nœud (ou sommet) : Élément de l’arbre, pouvant être une feuille ou un nœud interne.
  Définition : Un nœud est un élément de l’arbre, avec une arité correspondant au nombre de ses fils.

• Feuille : Nœud sans fils, de arité 0.
  Point clé : Les feuilles représentent les extrémités de l’arbre, souvent des éléments terminaux.

• Nœud interne : Nœud avec au moins un fils, arité ≥ 1.
  Point essentiel : Ces nœuds permettent de relier différentes parties de l’arbre et de structurer l’information.

• Profondeur (x) : Distance de la racine à un nœud x, mesurée par le nombre d’arêtes sur le chemin.
  Point à retenir : La profondeur indique la position relative d’un nœud dans l’arbre.

📝 Points essentiels

• La relation binaire R exprime la filiation parent-enfant, avec chaque nœud (sauf la racine) ayant un parent unique.
• La hauteur d’un arbre est la profondeur maximale de ses nœuds, représentant la longueur du plus long chemin de la racine à une feuille.
• La transformation d’un arbre quelconque en arbre binaire se fait en structurant ses fils en une chaîne, permettant une représentation uniforme.
• La représentation visuelle d’un arbre place la racine en haut, avec les fils descendant vers le bas.
• La relation entre nombre de nœuds, hauteur et arité maximale est encadrée par des inégalités, notamment pour les arbres binaires.

💡 À retenir

Un arbre est une structure hiérarchique non vide où chaque élément, sauf la racine, possède un parent unique, et où la hauteur et le nombre de nœuds sont liés par des inégalités fondamentales.

📖 2. Nœuds et racine

🔑 Notions clés & Définitions

Arbre (A) : Ensemble non vide muni d’une relation binaire R vérifiant :

• Il existe un unique élément r ∈ A appelé racine, tel que pour tout x ∈ A, r n’est pas enfant de x (¬(r R x)).
• Tout autre x ≠ r possède un unique parent y ∈ A, tel que x R y.
• En suivant la relation de parenté, on aboutit toujours à la racine.

Racine (r) : Élément particulier d’un arbre, racine de l’arbre, sans parent.

Nœud : Élément de l’arbre, pouvant être une feuille ou un nœud interne.

• Feuille : Nœud d’arité 0 (pas d’enfant).
• Nœud interne : Nœud avec au moins un fils.

Profondeur d’un nœud (x) : Distance en nombre d’arêtes entre la racine et le nœud x. La racine a une profondeur 0.
Hauteur d’un arbre : Profondeur maximale parmi tous ses nœuds.

Sous-arbre enraciné en x : Sous-arbre constitué de tous les descendants de x, avec x comme racine.

📝 Points essentiels

• La racine est l’unique nœud sans parent, située en haut de l’arbre.
• Chaque nœud (sauf la racine) possède un parent unique, garantissant une structure hiérarchique.
• La profondeur d’un nœud indique sa distance à la racine, la hauteur d’un arbre correspond à la profondeur du nœud le plus éloigné.
• La représentation visuelle d’un arbre montre la racine en haut, les nœuds reliés par des arêtes, avec les feuilles en bas.
• La relation entre hauteur et nombre de nœuds dépend de l’arité maximale des nœuds : plus l’arité est grande, plus l’arbre peut être dense.

💡 À retenir

L’arbre est une structure hiérarchique caractérisée par une racine unique, où chaque nœud a un parent unique (sauf la racine), et la profondeur et la hauteur permettent de mesurer la distance et la taille de la structure.

📖 3. Feuilles et nœuds internes

🔑 Notions clés & Définitions

• Nœud : Élément d’un arbre, représentant une unité de donnée ou de structure, relié à ses fils par des arêtes.
• Feuille : Nœud d’un arbre dont l’arité (nombre de fils) est zéro, c’est-à-dire sans enfant.
• Nœud interne : Nœud d’un arbre dont l’arité est au moins 1, c’est-à-dire ayant au moins un fils.
• Arité d’un nœud : Nombre de fils (ou enfants) d’un nœud dans un arbre.
• Racine : Nœud de départ d’un arbre, sans parent, généralement situé en haut de la représentation.
• Feuilles et nœuds internes dans un arbre binaire : Dans un arbre binaire, une feuille a arité 0, un nœud interne a arité 2 (ou 1 dans certains cas).

📝 Points essentiels

• La feuille est un nœud terminal, sans fils, souvent représentant une donnée finale ou une absence de sous-structure.
• Un nœud interne possède au moins un fils, servant de point de branchement ou de décision dans la structure arborescente.
• La distinction entre feuilles et nœuds internes permet de définir la structure et la complexité d’un arbre, notamment en termes de nombre total de nœuds et de profondeur.
• Dans un arbre binaire, la relation entre le nombre de nœuds internes $p$ et le nombre de feuilles est donnée par $p + 1$ pour un arbre entier.
• La hauteur d’un arbre est liée au nombre de niveaux, où la racine est à la profondeur 0, et les feuilles ont une profondeur maximale.

💡 À retenir

Les feuilles représentent les extrémités sans enfant d’un arbre, tandis que les nœuds internes structurent la hiérarchie ; leur nombre et leur disposition déterminent la forme et la complexité de l’arbre.

📖 4. Arbre binaire

🔑 Notions clés & Définitions

• Arbre : Ensemble non vide A muni d’une relation binaire R vérifiant l’existence d’un unique élément racine r, et pour chaque autre x, un parent unique y tel que x R y, formant une structure hiérarchique sans cycle.

• Racine : Élément racine r d’un arbre, point de départ de la hiérarchie, sans parent.

• Nœud : Élément de l’arbre, pouvant être une feuille (sans fils) ou un nœud interne (avec fils).

• Feuille : Nœud d’arité 0, sans fils, généralement en fin de branche.

• Hauteur : Longueur maximale d’un chemin du nœud racine à une feuille, correspondant à la profondeur maximale.

• Sous-arbre enraciné : Partie de l’arbre à partir d’un nœud x, formant un arbre à racine x, constitué de tous ses descendants.

📝 Points essentiels

• La relation binaire R indique la filiation parent-enfant, chaque nœud sauf la racine ayant un parent unique.

• La représentation graphique d’un arbre place la racine en haut, avec des branches vers ses fils.

• Les arbres binaires sont des arbres où chaque nœud a au plus deux fils : gauche et droit.

• La hauteur h d’un arbre à n nœuds d’arité maximale a des bornes : $\log_2(n+1) - 1 \leq h \leq n - 1$ pour un arbre binaire.

• Dans un arbre binaire entier, le nombre de feuilles est égal au nombre de nœuds internes plus un.

• La transformation d’un arbre d’arité quelconque en arbre binaire permet de standardiser la structure pour certains traitements.

• Les parcours (préfixe, infixe, postfixe, largeur) permettent d’énumérer tous les nœuds selon différents ordres, essentiels pour la reconstruction ou l’évaluation.

💡 À retenir

L’arbre binaire est une structure hiérarchique fondamentale en informatique, caractérisée par sa racine, ses nœuds, et ses fils, dont la hauteur et la forme influencent la complexité des algorithmes qui l’utilisent, notamment dans le tri ou l’évaluation d’expressions.

📖 5. Profondeur et hauteur

🔑 Notions clés & Définitions

• Profondeur d’un nœud :
  L’entier n ≥ 0 représentant la distance entre ce nœud et la racine, comptée en nombre d’arêtes sur le chemin le reliant à la racine. La racine a une profondeur 0.

• Hauteur d’un arbre :
  La profondeur maximale parmi tous ses nœuds. C’est la longueur du plus long chemin de la racine à une feuille.

• Sous-arbre enraciné :
  Un sous-ensemble d’un arbre, formé d’un nœud donné et de tous ses descendants, muni de la relation d’arête restreinte, qui constitue un arbre à part entière.

• Feuille :
  Nœud sans fils (arité 0). La racine d’un arbre peut aussi être une feuille si elle n’a pas de fils.

• Nœud interne :
  Nœud ayant au moins un fils (arité ≥ 1). Dans un arbre binaire, un nœud interne possède exactement deux fils ou un seul.

• Arbre binaire :
  Un arbre où chaque nœud a au plus deux fils, généralement appelés fils gauche et droit.

📝 Points essentiels

• La profondeur d’un nœud est unique et se calcule en comptant le nombre d’arêtes entre la racine et ce nœud.
• La hauteur d’un arbre est déterminée par la profondeur du nœud le plus éloigné de la racine.
• La relation entre nombre de nœuds, hauteur et arité maximale est encadrée par des inégalités :
  Pour un arbre de hauteur h et arité maximale a > 1, le nombre de nœuds n vérifie :
  $h + 1 \leq n \leq \frac{a^{h+1} - 1}{a - 1}$
• En arbre binaire, la hauteur h d’un arbre à n nœuds est bornée par :
  $\lfloor \log_2(n) \rfloor \leq h \leq n - 1$
• La transformation d’un arbre d’arité quelconque en arbre binaire permet de représenter toute structure arborescente dans un format binaire.

💡 À retenir

La profondeur d’un nœud mesure sa distance à la racine, tandis que la hauteur d’un arbre indique la longueur du plus long chemin de la racine à une feuille. Ces notions permettent d’évaluer la complexité et la structure des arbres, notamment en relation avec leur nombre de nœuds et leur arité.

📖 6. Sous-arbre enraciné

🔑 Notions clés & Définitions

• Arbre (A) : Ensemble non vide muni d’une relation binaire R vérifiant l’unicité de la racine et la relation de parenté. La racine r est l’élément sans parent, et chaque autre nœud possède un parent unique.
  Point essentiel : La structure garantit une hiérarchie où chaque nœud descend d’un seul parent, aboutissant à la racine.

• Sous-arbre enraciné en x : Ensemble Ax constitué de tous les nœuds y pour lesquels il existe un chemin de y à la racine x suivant la relation R, avec x comme racine.
  Point essentiel : Représente la descendance de x, formant un arbre à racine x.

• Profondeur d’un nœud x : Nombre d’arcs entre x et la racine r, c’est-à-dire la distance hiérarchique de x à la racine.
  Point essentiel : La racine a une profondeur 0, et chaque niveau descendant augmente la profondeur.

• Hauteur d’un arbre : La profondeur maximale parmi tous ses nœuds.
  Point essentiel : Indicateur de la profondeur la plus grande dans l’arbre, représentant sa taille verticale.

• Arbre binaire : Arbre où chaque nœud a au plus deux fils (gauche et droit). Un arbre binaire entier a tous ses nœuds d’arité 0 ou 2.
  Point essentiel : Structure simplifiée permettant une gestion efficace, notamment dans le tri et la recherche.

• Inégalités entre hauteur et nombre de nœuds : Relations mathématiques liant la hauteur h, le nombre de nœuds n, et l’arité maximale a, par des bornes inférieures et supérieures.
  Point essentiel : Permettent d’évaluer la complexité et la taille d’un arbre en fonction de ses caractéristiques.

📝 Points essentiels

• La racine est l’unique nœud sans parent, et tous les autres ont un parent unique, permettant une représentation hiérarchique claire.
• Le sous-arbre enraciné en x inclut tous les descendants de x, formant un arbre à racine x.
• La profondeur d’un nœud mesure sa distance à la racine, tandis que la hauteur de l’arbre reflète la profondeur maximale.
• La transformation d’un arbre d’arité quelconque en arbre binaire se fait en replaçant les frères droits comme fils droits, conservant la hiérarchie.
• Les inégalités entre hauteur et nombre de nœuds permettent d’estimer la taille d’un arbre en fonction de sa profondeur et de son arité.

💡 À retenir

Le sous-arbre enraciné en x est une structure hiérarchique essentielle pour analyser la descendance dans un arbre, et la relation entre hauteur, nombre de nœuds, et arité permet d’évaluer la complexité et la taille de cette structure.

📖 7. Inégalités hauteur/nœuds

🔑 Notions clés & Définitions

• Hauteur d’un arbre : La hauteur d’un arbre est la longueur du plus long chemin du nœud racine à une feuille, c’est-à-dire le nombre maximal de niveaux dans l’arbre.
  Point essentiel : Elle mesure la profondeur maximale de l’arbre.

• Nombre de nœuds : La quantité totale de nœuds (feuilles + nœuds internes) présents dans un arbre.
  Point essentiel : Indicateur de la taille globale de l’arbre.

• Arité maximale (a) : Le nombre maximum de fils qu’un nœud peut avoir dans un arbre.
  Point essentiel : Influence directement les bornes sur le nombre total de nœuds en fonction de la hauteur.

• Inégalité entre hauteur et nombre de nœuds : Encadrements qui relient la hauteur h d’un arbre, son arité maximale a, et son nombre total de nœuds n, selon la formule :
  $h + 1 \leq n \leq \frac{a^{h+1} - 1}{a - 1} \quad \text{pour } a > 1$
  Point essentiel : Permet d’évaluer la taille ou la profondeur d’un arbre en fonction de l’autre.

• Arbre filiforme : Arbre dont chaque nœud a arité 1, caractérisé par une hauteur h égale à n - 1, où n est le nombre de nœuds.
  Point essentiel : Cas particulier où l’arbre est le plus “long” pour un nombre donné de nœuds.

📝 Points essentiels

• La relation entre la hauteur h et le nombre de nœuds n dépend de l’arité maximale a de l’arbre.
• Pour un arbre d’arité a > 1, le nombre de nœuds est borné par une croissance géométrique :
  $n \leq \frac{a^{h+1} - 1}{a - 1}$
• La hauteur minimale d’un arbre à n nœuds et arité a est approximée par :
  $h \geq \log_a \left( (a - 1)n + 1 \right) - 1$
• En cas d’arbre binaire (a=2), la hauteur h vérifie :
  $\lfloor \log_2(n) \rfloor \leq h \leq n - 1$
• La croissance géométrique limite la possibilité de réduire la hauteur pour un nombre donné de nœuds, ce qui a des implications en complexité algorithmique.

💡 À retenir

Les inégalités entre hauteur et nombre de nœuds permettent d’évaluer la structure d’un arbre en fonction de sa taille ou de sa profondeur, illustrant que pour un arbre donné, sa hauteur ne peut pas être inférieure à un logarithme de son nombre total de nœuds (pour arité > 1), ce qui est crucial pour analyser la complexité des algorithmes utilisant des arbres.

📖 8. Transformation en arbre binaire

🔑 Notions clés & Définitions

• Arbre : Ensemble non vide A muni d’une relation binaire R vérifiant l’existence d’une racine r unique, et pour chaque autre nœud x, un parent y tel que x R y, formant une structure hiérarchique sans cycle.

• Nœud interne : Nœud de l’arbre ayant au moins un fils (arité ≥ 1). Il est appelé feuille si son arité est 0, c’est-à-dire sans fils.

• Arbre binaire : Arbre dont chaque nœud a au plus deux fils (arité ≤ 2). Un arbre binaire entier a tous ses nœuds d’arité 0 ou 2.

• Profondeur et Hauteur : La profondeur d’un nœud x est la distance de la racine à x (entier ≥ 0). La hauteur d’un arbre est la profondeur maximale de ses nœuds.

• Transformation en arbre binaire : Processus consistant à convertir un arbre quelconque en un arbre binaire en réorganisant ses fils, en laissant la racine inchangée, et en déplaçant les frères droits en fils droits.

📝 Points essentiels

• La relation binaire R indique la filiation parent-enfant, avec la racine unique r. Chaque nœud (sauf la racine) possède un parent unique, et en suivant la relation, on atteint la racine.

• La représentation visuelle d’un arbre est souvent sous forme de nœuds reliés par des arêtes, la racine étant en haut.

• La transformation d’un arbre d’arité quelconque en arbre binaire se fait en déplaçant les frères droits d’un nœud en fils droits, tout en conservant la racine.

• La hauteur h d’un arbre à n nœuds et arité maximale a une borne inférieure logarithmique : $\log_a((a-1)n + 1) - 1$, et une borne supérieure linéaire en n.

• La conversion en arbre binaire permet d’utiliser des algorithmes classiques (parcours, évaluation) en structurant l’arbre selon des règles précises.

💡 À retenir

La transformation d’un arbre quelconque en arbre binaire consiste à réorganiser ses fils pour respecter la limite de deux fils par nœud, ce qui facilite leur traitement algorithmique tout en conservant leur hiérarchie.

📖 9. Arbres en informatique

🔑 Notions clés & Définitions

• Arbre : Structure mathématique non vide constitué d’un ensemble de nœuds reliés par une relation binaire R, vérifiant qu’il existe une racine unique (élément r tel que tous les autres sont accessibles par des relations parent-enfant) et que chaque nœud (sauf la racine) possède un parent unique.

• Nœud interne : Nœud ayant au moins un fils (arité > 0). Dans un arbre binaire, un nœud interne a exactement deux fils ou aucun.

• Feuille : Nœud sans fils (arité = 0). Elle représente la terminaison d’un chemin dans l’arbre.

• Profondeur et Hauteur : La profondeur d’un nœud est la distance (nombre d’arêtes) entre ce nœud et la racine. La hauteur d’un arbre est la profondeur maximale parmi tous ses nœuds.

• Sous-arbre enraciné : Partie d’un arbre comprenant un nœud donné et tous ses descendants, formant un arbre à racine ce nœud.

• Arbre binaire : Arbre où chaque nœud a au plus deux fils, souvent appelés fils gauche et droit. Un arbre binaire entier a tous ses nœuds d’arité 0 ou 2.

📝 Points essentiels

• La relation binaire R définit la structure parent-enfant, avec une racine unique. Chaque nœud (sauf la racine) a un parent unique, garantissant une hiérarchie claire.

• La représentation visuelle d’un arbre place la racine en haut, avec des branches descendant vers les nœuds fils. La profondeur et la hauteur permettent de mesurer la taille et la complexité de l’arbre.

• Les arbres binaires sont souvent utilisés en informatique pour représenter des expressions, des structures de données (ex : systèmes de fichiers, arbres syntaxiques, XML), et sont manipulés via des parcours (préfixe, infixe, postfixe, largeur).

• Les inégalités entre hauteur et nombre de nœuds dépendent de l’arité maximale. Par exemple, dans un arbre binaire, la hauteur h vérifie : ⌊log₂(n)⌋ ≤ h ≤ n−1.

• La transformation d’un arbre d’arité quelconque en arbre binaire permet une gestion uniforme dans certains algorithmes.

💡 À retenir

Les arbres sont des structures hiérarchiques fondamentales en informatique, permettant de modéliser et de manipuler efficacement des données structurées, avec des propriétés clés comme la racine, les nœuds internes, les feuilles, et des parcours variés pour explorer leur contenu.

📖 10. Parcours en profondeur

🔑 Notions clés & Définitions

• Arbre : Objet mathématique constitué d’un ensemble non vide d’éléments (nœuds) reliés par une relation binaire vérifiant la propriété d’unicité du parent pour chaque nœud sauf la racine, et aboutissant à la racine en suivant ces relations.

• Racine : Élément unique d’un arbre qui ne possède pas de parent. Située en haut de la représentation graphique, elle sert de point de départ pour la structure de l’arbre.

• Nœud interne : Nœud ayant au moins un fils (arité ≥ 1). Il possède une étiquette et peut avoir des fils, contrairement aux feuilles.

• Feuille : Nœud sans fils (arité = 0). Elle représente une extrémité de l’arbre, souvent une donnée terminale.

• Parcours en profondeur : Méthode d’exploration d’un arbre consistant à descendre le plus profondément possible le long d’une branche avant de revenir en arrière pour explorer les autres branches. Il existe trois types principaux : préfixe, infixe, postfixe.

• Hauteur d’un arbre : Longueur maximale (en nombre de nœuds) entre la racine et une feuille. Elle mesure la profondeur maximale dans l’arbre.

📝 Points essentiels

• La relation binaire R définit la structure parent-enfant, avec chaque nœud (sauf la racine) ayant un parent unique et un ou plusieurs fils.

• La représentation graphique d’un arbre place la racine en haut, avec des branches descendant vers les fils, permettant une visualisation claire de la hiérarchie.

• La profondeur d’un nœud est l’entier n≥0 représentant la distance en nombre de liens depuis la racine. La hauteur de l’arbre est la profondeur maximale parmi tous ses nœuds.

• Les parcours en profondeur (préfixe, infixe, postfixe) permettent d’énumérer tous les nœuds selon un ordre précis, utile pour la reconstruction ou l’évaluation d’expressions.

• La complexité minimale pour trier par comparaison est de l’ordre de $\Theta(n \log n)$, liée à la structure d’un arbre binaire de décision.

💡 À retenir

Le parcours en profondeur explore systématiquement chaque branche de l’arbre jusqu’à ses extrémités avant de revenir en arrière, permettant une traversal exhaustive et ordonnée des nœuds selon différentes stratégies (préfixe, infixe, postfixe).

📖 11. Parcours en largeur

🔑 Notions clés & Définitions

• Parcours en largeur (ou BFS - Breadth-First Search) : méthode d'exploration d’un arbre ou d’un graphe consistant à visiter tous les nœuds d’un même niveau avant de passer au niveau suivant.
  Point essentiel : visite systématique par niveaux, en utilisant une file d’attente.

• Racines : nœuds de départ d’un arbre, situés au niveau 0.
  Point essentiel : point de départ du parcours.

• Forêt : ensemble d’arbres non reliés, que l’on peut explorer simultanément lors d’un parcours en largeur.

• Fonction racines(l) : retourne la liste des racines d’une forêt (liste de nœuds de niveau courant).
  Point essentiel : collecte les nœuds à traiter à chaque étape.

• Fonction ss_arbres(l) : extrait la liste des sous-arbres (fils) de tous les nœuds d’une forêt donnée.
  Point essentiel : prépare la liste des sous-nœuds pour le prochain niveau.

📝 Points essentiels

• Le parcours en largeur utilise une structure de file pour gérer l’ordre d’exploration, en insérant les nœuds des niveaux courants puis en traitant leurs enfants.
• La fonction principale largeur(a) commence par la racine de l’arbre, puis itère en ajoutant successivement tous les nœuds du niveau actuel, puis ceux du niveau suivant.
• La complexité de l’algorithme dépend du nombre total de nœuds, avec une exploration systématique par niveaux.
• La méthode est adaptée pour explorer tous les nœuds d’un arbre ou d’un graphe, notamment pour rechercher un élément ou parcourir la structure.

💡 À retenir

Le parcours en largeur explore systématiquement tous les nœuds par niveaux, garantissant une visite exhaustive et ordonnée, idéal pour la recherche du plus court chemin ou la traversée complète d’un arbre ou d’un graphe.

📖 12. Complexité tri par comparaison

🔑 Notions clés & Définitions

• Arbre de décision pour tri : Structure binaire représentant toutes les séquences de comparaisons possibles lors d’un tri par comparaison. Chaque feuille correspond à une permutation triée, chaque branche à une série de comparaisons.

• Feuille d’un arbre : Noeud terminal représentant une permutation spécifique de l’ensemble à trier. Le nombre de feuilles est au moins égal à n! (factorielle de n), pour n éléments.

• Hauteur d’un arbre binaire : Nombre maximal de comparaisons effectuées dans le pire cas lors du tri. Elle est liée à la profondeur maximale de l’arbre de décision.

• Borne inférieure de complexité : Limite théorique indiquant le nombre minimal de comparaisons nécessaires pour trier dans le pire cas, généralement proportionnelle à n log n.

• Approximation de Stirling : Formule asymptotique utilisée pour estimer n! (factorielle), essentielle pour démontrer la limite inférieure en complexité de tri.

📝 Points essentiels

• La construction d’un arbre de décision pour un tri par comparaison montre qu’il doit avoir au moins n! feuilles, correspondant à toutes les permutations possibles.

• La relation entre le nombre de feuilles et la hauteur de l’arbre binaire implique que la hauteur minimale (nombre de comparaisons dans le pire cas) est au moins log₂(n!).

• En utilisant l’approximation de Stirling, on montre que log₂(n!) est asymptotiquement équivalent à n log₂(n), établissant une borne inférieure pour la complexité.

• Ainsi, aucun algorithme de tri par comparaison ne peut faire mieux que Θ(n log n) dans le pire cas.

• Les tris rapides et fusion atteignent cette borne, ce qui prouve leur optimalité asymptotique.

💡 À retenir

La complexité minimale pour trier par comparaison est proportionnelle à n log n, ce qui établit une limite fondamentale que tout algorithme doit respecter dans le pire cas.

📊 Tableaux de Synthèse

⚠️ Pièges & Confusions Fréquentes

1. Confondre racine et nœud interne : la racine n’a pas de parent, un nœud interne a au moins un fils.
2. Faux-ami : penser que toutes les feuilles ont le même nombre de fils, alors qu’elles ont 0.
3. Erreur dans la relation parent-enfant : chaque nœud (sauf racine) a un seul parent, pas plusieurs.
4. Confusion entre profondeur et hauteur : profondeur d’un nœud ≠ hauteur de l’arbre.
5. Mauvaise interprétation de la transformation en arbre binaire : ne pas respecter la structure de chaînage des fils.
6. Oublier que la hauteur d’un arbre binaire est bornée par $\log_2(n+1)$ (pour un arbre parfait).
7. Confusion entre parcours en profondeur et parcours en largeur : ordre différent, usages spécifiques.

✅ Checklist Examen

• Maîtriser la définition précise d’un arbre, racine, nœud, feuille, nœud interne.
• Savoir différencier un nœud interne d’une feuille.
• Connaître la relation entre nombre de nœuds internes et feuilles dans un arbre binaire.
• Savoir représenter un arbre binaire et ses sous-arbres.
• Comprendre la notion de profondeur d’un nœud et de la hauteur de l’arbre.
• Être capable de transformer un arbre quelconque en arbre binaire.
• Connaître les parcours en profondeur (préfixe, infixe, postfixe) et en largeur.
• Savoir appliquer les inégalités sur la hauteur en fonction du nombre de nœuds.
• Identifier les erreurs fréquentes dans la lecture ou la représentation d’un arbre.
• Être capable d’évaluer la complexité d’un tri par comparaison en fonction du nombre de nœuds.
• Vérifier la compréhension des relations entre nombre de nœuds, hauteur et arité maximale.
• Vérifier la maîtrise du vocabulaire spécifique : racine, feuille, nœud interne, profondeur, hauteur.
• S’assurer de connaître la transformation d’un arbre en arbre binaire pour uniformiser la structure.