Aller au contenu

Structure arborescente (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Définition⚓︎

Point de cours

On a déjà présenté des types abstraits représentant des structures de données linéaires : Liste, Pile ou File. Ces structures sont adaptées au traitement séquentiel des données :

  • on ne peut accéder directement qu'à un (ou deux) éléments privilégiés (début ou fin de la séquence)
  • les éléments forment une chaîne : depuis chaque élément (sauf le dernier) un lien permet d'accéder au suivant
  • pour accéder à un élément il faut parcourir tous les éléments précédents dans la chaîne, ce qui donne une complexité moyenne linéaire (proportionnelle à la taille de la structure) pour effectuer un traitement.

Si on conserve une structure chaînée mais qu'on autorise plusieurs liens pour accéder aux éléments suivants (en interdisant les retours en arrière), alors on obtient une structure de données arborescente.

La terminologie des structures arborescentes s'inspire de celles des arbres de la nature. On désignera donc souvent une structure arborescente comme un arbre. La brique de base de stockage d'un élément s'appelle un noeud et un arbre est un ensemble de noeuds qui sont connectés entre eux. Le tableau ci-dessous fait correspondre les dénominations entre structures linéaire et arborescente. Comme dans les structures linéaires, une structure arborescente possède un seul point d'entrée, le noeud racine de l'arbre. En revanche, il peut exister plusieurs noeuds appelés feuilles qui n'ont pas de successeur.

Fonction Structure linéaire Structure arborescente
Stockage d'un élément cellule noeud
Premier élément Début ou tête noeud racine (unique)
Élément sans successeur Fin (unique) noeud feuille (eventuellement plusieurs)
Elément suivant une ou zéro cellule suivante un ou plusieurs noeud(s) fils
Elément précédent zéro ou un seul zéro ou un seul noeud père (dans les arbres que nous étudierons)
Nombre d'éléments Taille Taille
Distance entre un élément et le premier élément de la structure index profondeur

Un arbre avec 6 noeuds :

alt

Représentation en informatique

En informatique, les structures arborescentes sont représentées avec la racine en haut et les feuilles en bas !

Image empruntée à Gilles Lassus

alt

Applications⚓︎

Pour quelles applications est-il intéressant de choisir une structure de données arborescente ?

  1. Si plusieurs liens partent d'un élément, on peut espérer que le nombre de sauts pour accéder à un élément précis depuis la racine sera moindre que pour une structure linéaire. Avec une structure bien ordonnée et compacte (ce sera la difficulté), on aura donc une meilleure complexité pour l'accès à un élément que pour une structure linéaire. Ainsi, on peut organiser de façon efficace le nombre considérable de fichiers sur une mémoire non volatile à l'aide d'une arborescence .

    Arborescence d'un système de fichiers

    Un répertoire est un fichier pouvant contenir d'autres fichiers. Les fichiers sont les noeuds terminaux ou feuilles d'une structure arborescente dont les noeuds intérieurs sont des répertoires. On a représenté ci-dessous l'arborescence de ce site web, limitée à une profondeur de 2.

    alt

  2. La possibilité de définir plusieurs liens partant d'un élément permet de hiérarchiser les éléments. Dans un arbre généalogique, la hiérarchie sera définie par la distance (en nombre de liens) depuis la racine. On peut aussi définir des règles d'imbrication pour structurer des documents où des éléments peuvent contenir d'autres éléments :

    • un livre est constitué de chapitres, eux mêmes constitués de paragraphes : le format XML permet de décrire un document produit par un traitement de textes

      Arborescence d'un fichier XML de traitement de texte

      Le XML est un format de description de fichiers stadardisé par le W3C. A chaque document XML correspond une arborescence reflétant la structure du document. La structure arborescente permet de définir une API standardisée, le DOM qui permet aux langages de programmation de manipuler les fichiers XML. Par convention un noeud fictif est la racine de cette arborescence. Voici le code XML et l'arbre de représentation de ce document créé avec LibreOffice Writer

      XML
      <?xml version="1.0" encoding="UTF-8"?>
<indexing>
<paragraph index="9" node_type="writer">Titre 1</paragraph>
<paragraph index="10" node_type="writer">paragraphe</paragraph>
<paragraph index="11" node_type="writer">Titre 2</paragraph>
</indexing>

      alt

      • un page web en HTML est constituée d'éléments (ou balises) imbriqué(e)s
      Arborescence d'un fichier HTML

      HTML est un format de description de fichiers stadardisé par le W3C qui permet d'organiser une page Web dans une structure arborescente. HTML existe en plusieurs versions dont l'une reste compatible avec XML. L'API standardisée du DOM permet aux langages de programmation de manipuler les fichiers HTML.

      On donne ci-dessous le code HTML de cette page Web et sa représentation sous forme d'arbre.

      HTML
      <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html lang="en" xml:lang="en" xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>
Exemple HTML
</title>
<meta content="text/html;charset=utf-8" http-equiv="content-type"/>
<meta content="CC-by-nc" name="licence"/>
</head>
<body>
<div>
<h1>
    Partie 1
</h1>
<p>
    Paragraphe 1
</p>
</div>
<div>
<h1>
    Partie 2
</h1>
<ol>
    <li>
    un
    </li>
    <li>
    deux
    </li>
    <li>
    trois
    </li>
    <li>
    quatre
    </li>
</ol>
</div>
</body>
</html>

      alt

      • une image vectorielle au format SVG est constituée de figures géométriques, elles mêmes constitués d'éléments plus simples (lignes, points ...)
      Arborescence d'un fichier SVG

      SVG est un format de description d'image vectorielle basé sur XML.

      alt

      On donne ci-dessous le code SVG de l'image ci-dessus et sa représentation sous forme d'arbre.

      HTML
      <!DOCTYPE html>
<html>
<body>
<svg  xmlns="http://www.w3.org/2000/svg"   version="1." height="150" width="500">
<defs>
<radialGradient id="grad1" cx="50%" cy="50%" r="50%" fx="50%" fy="50%">
<stop offset="0%" style="stop-color:rgb(255,255,255);stop-opacity:0" />
<stop offset="100%" style="stop-color:rgb(0,0,255);stop-opacity:1" />
</radialGradient></defs><ellipse cx="200" cy="70" rx="85" ry="55" fill="url(#grad1)" />
Sorry, your browser does not support inline SVG.
</svg>
</body>
</html>

      alt

  3. Une structure arborescente permet de représenter les choix logiques successifs effectués au cours :

    • d'un calcul :

      Arbre syntaxique d'un calcul

      Les calculs arithmétiques mettant en jeu les quatre opérateurs binaires (+, -, *, /) peuvent être représentés sous la forme d'arbres binaires, c'est-à-dire d'arbres dont les noeuds ont tous exactement deux fils. Les opérateurs sont portés par les noeuds internes et les nombres par les feuilles. Par exemple le calcul noté \(((3\times(4 - 5)) + (5 \times (12 + 7)))\) peut être représenté par l'arbre ci-dessous. Cette notation habituelle, dite infixe, correspond à un parcours de l'arbre où on traite d'abord récursivement le fils gauche, puis le noeud, puis récursivement le fils droit.

      alt

    • d'un programme :

      Arbre syntaxique d'un programme

      Un arbre de syntaxe abstrait d'un programme est une représentation intermédiaire avant de générer le code compilé. Les nœuds internes sont marqués par des opérateurs et les feuilles représentent les opérandes. On donne ci-dessous l'arbre syntaxique en Python d'une fonction calculant le PGCD de deux entiers avec l'algorithme d'Euclide. On a utilisé le module ctree.

      🐍 Script Python
      def pgcd(a, b):
    while b != 0:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

      alt

    • ou de la résolution d'un problème : gestion de planning, jeu (échec, go, morpion) etc ...

      Arbre des configurations du jeu de Morpion

      A partir d'une situation de départ on peut représenter pour le jeu de Morpion les états du plateau en fonction des coups successifs des deux joueurs. Les noeuds portent les configurations du jeux et les transitions entre les noeuds correspondent aux coups possibles des joueurs. Si l'arbre est petit comme pour le morpion, on peut ainsi déterminer une stratégie optimale. Sinon, pour les jeux à deux joueurs, on peut sélectionner les prochains coups possibles en fonction de l'évaluation des configurations obtenues à une certaine profondeur dans l'arbre. On considère qu'un joueur cherche toujours à maximiser l'évaluation de la configuration pour son tour de jeu et son adversaire à la minimiser : c'est l'algorithme du min-max.

      alt

Au programme en terminale NSI⚓︎

On présente dans cette partie du programme trois types abstraits de structures de données arborescentes, de la plus simple à la plus complexe :