2.
Théorie des arbres
2.1. Définition et structure des arbres
Un arbre est une structure de données non linéaire organisée de manière hiérarchique. Il se compose :
• Nœuds : unités de base contenant des données.
• Racine : le nœud supérieur de l’arbre, sans parent.
• Branches : connexions entre les nœuds, représentant les relations.
• Feuilles : nœuds sans enfant, représentant les terminaisons.
• Profondeur : nombre de niveaux depuis la racine jusqu’à un nœud donné.
• Hauteur : distance maximale entre la racine et une feuille.
Types d’arbres
1. Arbre binaire :
• Chaque nœud a au maximum deux enfants.
• Utilisé pour organiser des données hiérarchiques simples.
2. Arbre de recherche binaire (Binary Search Tree, BST) :
• Les nœuds à gauche contiennent des valeurs inférieures au nœud parent, et ceux à
droite des valeurs supérieures.
• Optimisé pour les opérations de recherche, insertion et suppression en  dans le
meilleur cas.
3. Arbres équilibrés :
• Exemple : AVL (Adelson-Velsky-Landis) et Red-Black.
• Maintiennent une hauteur équilibrée pour éviter la dégradation des performances.
4. Arbres n-aires :
• Chaque nœud peut avoir jusqu’à  enfants.
• Souvent utilisés pour modéliser des hiérarchies complexes comme des systèmes de
fichiers.
2.2. Parcours des arbres
Les parcours d’arbres permettent d’explorer ou de traiter les données dans les nœuds de différentes
manières.
Parcours en profondeur :
• Préfixe (pré-ordre) : Visiter le nœud parent avant ses enfants.
• Infixe (in-ordre) : Visiter le sous-arbre gauche, le nœud parent, puis le sous-arbre droit
(utilisé pour trier un arbre binaire).
• Postfixe (post-ordre) : Visiter les enfants avant le parent.
Parcours en largeur :
• Exploration de l’arbre niveau par niveau, en commençant par la racine.
Exemple pratique :
Pour un arbre binaire où la racine est , avec  et  comme enfants :
• Préfixe : .
• Infixe : .
• Postfixe : .
Focus sur les arbres de décision
Un arbre de décision est une structure spécifique utilisée pour prendre des décisions basées sur des
conditions successives. C’est un sous-ensemble des arbres utilisés pour la classification, la prédiction et
l’analyse des données.
Structure d’un arbre de décision :
• Chaque nœud interne représente une question ou un test sur une caractéristique des
données (par exemple, “Le revenu annuel est-il supérieur à 30 000 euros ?”).
• Chaque branche correspond à une réponse (oui/non ou d’autres catégories).
• Chaque feuille représente une décision ou une prédiction (par exemple, “Approuvé” ou
“Refusé” dans une analyse de crédit).
Exemple :
Un arbre de décision pour classifier des emails en “Spam” ou “Non-Spam” pourrait avoir la structure
suivante :
1. Racine : “L’email contient-il le mot ‘gratuit’ ?”
• Oui → Branche gauche : “L’email contient-il un lien ?”
• Non → Branche droite : “L’email provient-il d’un contact connu ?”
2. Les feuilles contiennent les résultats : “Spam” ou “Non-Spam”.
Applications des arbres de décision :
1. Classification :
• Identifier des catégories ou classes dans les données.
• Exemple : Diagnostiquer une maladie sur la base des symptômes.
2. Régression :
• Faire des prédictions de valeurs continues.
• Exemple : Prédire le prix d’un bien immobilier en fonction de sa surface et de son
emplacement.
Forces des arbres de décision :
• Facilité d’interprétation : ils sont lisibles et intuitifs.
• Rapidité d’exécution sur des ensembles de données modestes.
• Utilisés dans des algorithmes avancés comme les forêts aléatoires et XGBoost.
Limites des arbres de décision :
• Sensibles aux petites variations dans les données (problème de surapprentissage).
• Moins performants que des modèles plus complexes comme les réseaux de neurones
sur de grands ensembles de données non structurés.
Les arbres, et en particulier les arbres de décision, constituent donc un outil polyvalent en algorithmique
et intelligence artificielle, capable d’adresser des problèmes de modélisation, d’optimisation et de prise
de décision. Leur simplicité conceptuelle masque cependant une grande richesse dans leurs applications,
notamment lorsqu’ils sont combinés avec d’autres techniques comme l’apprentissage profond ou les
algorithmes probabilistes.
