Ch. 5 - Arbres : Cours - Partie 1

1. Introduction

1.1. Vocabulaire

NoteDéfinition

En informatique, un arbre est une structure de données hiérarchique (non linéaire). Elle est composée de nœuds.

  • Le nœud initial est appelé racine.
  • Il existe un chemin unique de la racine à n’importe quel autre nœud.

graph TD
    D((D)) --- U((U))
    D --- L((L))
    D --- A((A))
    A --- V((V))
    U --- C((C))
    L --- X((X))
    style D fill:#f9f,stroke:#333,stroke-width:4px

Vocabulaire détaillé :

  • Père / Fils : Chaque nœud a exactement un nœud père, sauf la racine qui n’en a pas. Un nœud peut avoir un nombre quelconque de fils.
  • Feuille : Un nœud qui n’a aucun fils est appelé une feuille (ou nœud externe).
  • Nœud interne : Un nœud qui n’est pas une feuille.
  • Étiquette (ou Clé) : La valeur portée par le nœud.
  • Arête : Le lien reliant deux nœuds.
AstuceExemple sur l’arbre ci-dessus
  • La racine est D.
  • D a trois fils : U, L et A.
  • V est un fils de A. A est le père de V.
  • Les feuilles sont C, X et V.

1.2. Exemples d’utilisation

Les structures arborescentes sont omniprésentes en informatique :

  1. Systèmes de fichiers : Dossiers et fichiers sur un disque dur.

  1. DOM (Document Object Model) : Structure d’une page HTML. Par exemple, le code HTML ci-dessous sera modélisé par l’arbre ci-dessous (source : w3.org).
<TABLE>
    <ROWS> 
      <TR> 
        <TD>Shady Grove</TD>
        <TD>Aeolian</TD> 
      </TR> 
      <TR>
        <TD>Over the River, Charlie</TD>
        <TD>Dorian</TD> 
      </TR> 
    </ROWS>
</TABLE>

  1. Arbres syntaxiques : Utilisés par les compilateurs pour analyser le code source (ex: \(3 \times (4 + 5)\)).

graph TD
    M((x)) --- T(3)
    M --- P((\+))
    P --- Q(4)
    P --- C(5)

  1. Arbres généalogiques (ascendants ou descendants).

1.3. Caractéristiques numériques

NoteDéfinitions
  • Taille : Le nombre total de nœuds de l’arbre.
  • Profondeur d’un nœud : Le nombre de nœuds sur le chemin de la racine à ce nœud (inclus).
    • Convention : La profondeur de la racine est 1. (Certaines sources utilisent 0, attention aux conventions).
  • Hauteur de l’arbre : La profondeur maximale parmi tous les nœuds de l’arbre.
    • Convention : Arbre vide = hauteur 0. Arbre réduit à la racine = hauteur 1.
AstuceExemple

Considérons l’arbre ci-dessous :

  • La taille de cet arbre est égale à 7.
  • La profondeur du nœud C est égale à 3, celle de X est égale à 4.
  • La hauteur de cet arbre est égale à 4 : X est le nœud le plus profond.

2. Arbres Binaires

2.1. Définition

NoteDéfinition

Un arbre binaire est un arbre dans lequel chaque nœud possède au plus deux fils. On distingue le fils gauche et le fils droit.

L’arbre donné en exemple ci-dessus n’est pas un arbre binaire car le nœud D possède 3 fils.

L’arbre ci-dessous est un arbre binaire :

2.2. Structure récursive

Un arbre binaire est une structure de données récursive. Un arbre binaire est :

  • Soit un arbre vide (noté souvent \(\emptyset\) ou None).
  • Soit un nœud (la racine) associé à deux arbres binaires disjoints appelés sous-arbre gauche et sous-arbre droit.

AstuceExemple

Pour l’arbre représenté ci-dessous, nous avons mis en évidence le sous-arbre gauche et le sous-arbre droit du nœud racine C.

Le nœud Q admet comme sous-arbre gauche le nœud H et comme sous-arbre droit, l’arbre vide.

Cette notion de sous arbre permet de mettre en évidence la structure récursive d’un arbre binaire : un arbre binaire est un arbre dans lequel chaque nœud possède un arbre fils gauche et un arbre fils droit qui sont tous deux des arbres binaires.

2.3. Types d’arbres binaires particuliers

Il est important de distinguer ces cas particuliers pour les calculs de complexité.

  • Arbre Filiforme (ou Dégénéré) : Chaque nœud n’a qu’un seul fils (sauf la feuille unique). L’arbre ressemble à une liste chaînée.
    • Sa hauteur \(h\) est égale à sa taille \(n\).
  • Arbre Binaire Parfait (souvent appelé “Complet” par abus de langage) : Tous les niveaux sont remplis. Toutes les feuilles sont à la même profondeur.
    • C’est l’arbre le plus “tassé” possible.
  • Arbre Binaire Complet : Tous les niveaux sont remplis excepté éventuellement le dernier, qui est rempli de la gauche vers la droite.

2.4. Relation entre Taille et Hauteur

Soit un arbre binaire de taille \(n\) et de hauteur \(h\).

  1. Cas le moins favorable (Arbre filiforme) : \[h = n\]

  2. Cas le plus favorable (Arbre parfait) : Dans un arbre parfait de hauteur \(h\), le nombre de nœuds est la somme des puissances de 2 : \[n = 1 + 2 + 4 + ... + 2^{h-1} = \sum_{i=0}^{h-1} 2^i = 2^h - 1\]

    On a donc \(n = 2^h - 1\), ce qui équivaut à \(h = \log_2(n+1)\).

ImportantEncadrement de la hauteur

Pour tout arbre binaire de taille \(n\) et de hauteur \(h\) : \[ \log_2(n+1) \leqslant h \leqslant n \]

Cette propriété est fondamentale : elle signifie que si un arbre est bien équilibré (proche d’un arbre parfait), sa hauteur est très petite par rapport à sa taille (logarithmique). Cela rendra les algorithmes de recherche très efficaces.

3. Arbres Binaires de Recherche (ABR)

3.1. Définition

NoteDéfinition

Un Arbre Binaire de Recherche (ABR) est un arbre binaire dont les clés vérifient la propriété suivante pour tout nœud :

  • Toutes les clés du sous-arbre gauche sont inférieures ou égales à la clé du nœud.
  • Toutes les clés du sous-arbre droit sont supérieures à la clé du nœud.

(Note : On suppose souvent que les clés sont distinctes, auquel cas les inégalités sont strictes).

3.2. Intérêt

La structure d’ABR permet d’effectuer des recherches très rapides, similaires à la recherche dichotomique dans un tableau trié. Si l’arbre est équilibré, la complexité de la recherche est en \(\mathcal{O}(\log_2 n)\).