🌳 Les Arbres
Maîtrisez les structures hiérarchiques pour organiser et traiter vos données efficacement
🎯 Définition Fondamentale
🌲 Structure arborescente
Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes, sans cycle. C'est un cas particulier de graphe connexe et acyclique, parfait pour représenter des relations hiérarchiques.
📊 Exemple d'arbre
A (racine)
/ \
B C
/ / \
D E F (feuilles)
Structure hiérarchique
Organisation en niveaux avec une racine unique et des relations parent-enfant clairement définies.
Sans cycle
Aucun chemin ne permet de revenir au point de départ, garantissant une structure claire et navigable.
Connexe
Tous les nœuds sont accessibles depuis la racine, assurant une cohérence structurelle.
📚 Vocabulaire Essentiel
Nœud (Sommet)
Élément fondamental de l'arbre contenant une valeur ou des données.
Racine
Nœud au sommet de l'arbre, point d'entrée unique sans parent.
Feuille
Nœud terminal sans enfants, extrémité de l'arbre.
Parent/Enfant
Relations directes : parent au-dessus, enfant en-dessous.
Frères
Nœuds partageant le même parent, au même niveau.
Sous-arbre
Arbre formé par un nœud et tous ses descendants.
📏 Propriétés Importantes
Hauteur
Longueur du plus long chemin de la racine à une feuille. Mesure la "profondeur" maximale de l'arbre.
Profondeur d'un nœud
Distance de la racine à ce nœud. La racine a une profondeur de 0.
Degré d'un nœud
Nombre d'enfants directs d'un nœud. Détermine la "largeur" locale.
Taille
Nombre total de nœuds dans l'arbre. Mesure la complexité globale.
💡 Important : Ces propriétés sont fondamentales pour analyser la complexité des algorithmes sur les arbres.
🌲 Arbres Binaires
🔀 Arbre binaire
Un arbre binaire est un arbre où chaque nœud a au maximum 2 enfants : un enfant gauche et un enfant droit. Cette contrainte simplifie les algorithmes et optimise les performances.
Structure équilibrée
Limitation à 2 enfants maximum permettant un équilibrage efficace et des opérations optimisées.
💻 Classe NoeudBinaire
class NoeudBinaire:
def __init__(self, valeur, gauche=None, droite=None):
self.valeur = valeur
self.gauche = gauche
self.droite = droite
def est_feuille(self):
return self.gauche is None and self.droite is NoneImplémentation Python
Structure de classe simple avec méthodes essentielles pour la manipulation et l'analyse.
💻 Classe ArbreBinaire
class ArbreBinaire:
def __init__(self, racine=None):
self.racine = racine
def est_vide(self):
return self.racine is None📏 Calcul de hauteur
Algorithme récursif pour déterminer la profondeur maximale de l'arbre.
💻 Méthode hauteur
def hauteur(self, noeud=None):
if noeud is None:
noeud = self.racine
if noeud is None:
return -1
if noeud.est_feuille():
return 0
hauteur_gauche = self.hauteur(noeud.gauche) if noeud.gauche else -1
hauteur_droite = self.hauteur(noeud.droite) if noeud.droite else -1
return 1 + max(hauteur_gauche, hauteur_droite)🔢 Calcul de taille
Comptage récursif du nombre total de nœuds dans l'arbre.
💻 Méthode taille
def taille(self, noeud=None):
if noeud is None:
noeud = self.racine
if noeud is None:
return 0
return 1 + self.taille(noeud.gauche) + self.taille(noeud.droite)🏗️ Exemple de construction
1
/ \
2 3
/ / \
4 5 6
💻 Construction manuelle
racine = NoeudBinaire(1)
racine.gauche = NoeudBinaire(2)
racine.droite = NoeudBinaire(3)
racine.gauche.gauche = NoeudBinaire(4)
racine.droite.gauche = NoeudBinaire(5)
racine.droite.droite = NoeudBinaire(6)
arbre = ArbreBinaire(racine)
print(f"Hauteur: {arbre.hauteur()}") # 2
print(f"Taille: {arbre.taille()}") # 6
⚡ Performance : Les arbres binaires équilibrés offrent une complexité O(log n) pour la plupart des opérations.