Cours Terminale NSI : Les arbres

Introduction aux arbres

Un arbre est une structure de données qui permet d’organiser des informations sous une forme hiérarchique. Contrairement aux structures linéaires comme les listes ou les tableaux, les arbres se caractérisent par leur structure ramifiée, composée de nœuds reliés par des liens appelés arêtes.

Un arbre commence par un nœud principal appelé racine. Depuis la racine, chaque nœud peut avoir des sous-nœuds, appelés enfants, formant ainsi des ramifications. Les nœuds qui n'ont pas d'enfants sont appelés feuilles. Les arbres sont utilisés dans de nombreux domaines de l’informatique en raison de leur efficacité pour représenter des données hiérarchiques ou effectuer des recherches rapides.

Exemple d'arbres dans le monde réel

  • Arbre généalogique : Un individu représente un nœud, et ses descendants sont les enfants de ce nœud.
  • Structure de fichiers : La racine représente le répertoire principal, et les sous-dossiers ou fichiers en sont les enfants.
  • Organisation d'une entreprise : Chaque employé peut être relié à son supérieur, créant ainsi une structure hiérarchique.

Terminologie

Pour bien comprendre les arbres, il est essentiel de maîtriser leur terminologie. Voici quelques notions fondamentales :

  • Nœud : Élément principal d’un arbre contenant une donnée et des références vers d’autres nœuds.
  • Racine : Premier nœud de l’arbre, à partir duquel tout le reste est construit. Chaque arbre a une unique racine.
  • Parent : Nœud directement au-dessus d’un autre nœud.
  • Enfant : Nœud directement sous un autre nœud. Un parent peut avoir plusieurs enfants.
  • Feuille : Nœud sans enfants, situé à l’extrémité de l’arbre.
  • Arête : Connexion ou lien entre deux nœuds.
  • Profondeur : Distance entre un nœud donné et la racine de l’arbre.
  • Hauteur : Longueur maximale entre la racine et l’une des feuilles.
  • Degré : Nombre d’enfants d’un nœud.
  • Chemin : Séquence de nœuds permettant de relier deux nœuds.

Types d'arbres

Arbre binaire

Un arbre binaire est un type particulier d’arbre où chaque nœud a au maximum deux enfants, appelés souvent sous-arbre gauche et sous-arbre droit. Cette structure est largement utilisée en informatique grâce à sa simplicité et à ses nombreuses applications, notamment dans les algorithmes de recherche et les tris.

Arbre binaire de recherche (ABR)

Un arbre binaire de recherche est un arbre binaire où les données sont organisées selon une règle précise :
- Les valeurs des nœuds du sous-arbre gauche sont toujours inférieures à la valeur du nœud racine.
- Les valeurs des nœuds du sous-arbre droit sont toujours supérieures à la valeur du nœud racine.

Ce type d’arbre permet d’effectuer des recherches, des insertions et des suppressions en temps relativement court (complexité logarithmique dans le meilleur cas).

Autres types d’arbres

  • Arbre n-aire : Chaque nœud peut avoir un nombre quelconque d’enfants, limité à une valeur fixe (n).
  • Arbre équilibré : Arbre où la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud est minimale.
  • Arbre Trie : Utilisé pour organiser des données textuelles, comme dans les moteurs de recherche ou les dictionnaires électroniques.
  • Arbre de Huffman : Utilisé en compression de données pour créer des codes optimaux.

Représentation des arbres en informatique

Les arbres peuvent être représentés de plusieurs manières en mémoire. Voici les deux approches les plus courantes :

Représentation par listes imbriquées

Dans cette méthode, chaque nœud est représenté par une liste. La première valeur correspond au nœud actuel, et les deux listes suivantes représentent les sous-arbres gauche et droit.
Exemple :

arbre = [1, [2, [], []], [3, [], []]]

Ici, le nœud racine est 1, il a deux enfants : 2 (sous-arbre gauche) et 3 (sous-arbre droit).

Représentation par classe

Cette méthode repose sur une classe définissant un nœud et ses relations avec les autres nœuds.
Exemple en Python :

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

Parcours d'un arbre

Parcourir un arbre consiste à visiter tous ses nœuds selon un ordre particulier. Voici les deux principales catégories de parcours :

Parcours en profondeur (DFS)

  1. Préfixe : On visite le nœud actuel, puis le sous-arbre gauche, puis le sous-arbre droit.
  2. Infixe : On visite le sous-arbre gauche, puis le nœud actuel, puis le sous-arbre droit. Ce type de parcours est particulièrement utile pour les arbres binaires de recherche.
  3. Postfixe : On visite le sous-arbre gauche, puis le sous-arbre droit, et enfin le nœud actuel.

Parcours en largeur (BFS)

Ce type de parcours explore les nœuds niveau par niveau, en partant de la racine. Il est souvent mis en œuvre à l’aide d’une file (queue).

Exemple de parcours préfixe en Python :

def parcours_prefixe(noeud):
    if noeud is not None:
        print(noeud.valeur)
        parcours_prefixe(noeud.gauche)
        parcours_prefixe(noeud.droite)

Applications des arbres

Les arbres sont omniprésents en informatique et trouvent des applications dans de nombreux domaines :
- Arbres de décision : Utilisés dans les systèmes d’intelligence artificielle pour modéliser des choix.
- Analyse syntaxique : Les compilateurs utilisent des arbres pour analyser la structure des programmes.
- Bases de données : Les arbres équilibrés (comme les arbres B+) permettent des recherches efficaces.
- Compression de données : L’arbre de Huffman est utilisé pour réduire la taille des fichiers.

Exercices proposés

Exercice 1 : Représentation

Représenter un arbre donné sous la forme d'une liste imbriquée et d'une classe Python.

Exercice 2 : Parcours

Implémenter les trois types de parcours en profondeur (préfixe, infixe, postfixe) et tester sur un arbre simple.

Exercice 3 : Insertion dans un ABR

Écrire une fonction permettant d’insérer une nouvelle valeur dans un arbre binaire de recherche.