Table des matières

Arbres

Arbres

Il s'agit d'un structure de données hiérarchique.

Par opposition aux structures linéaires que sont les tableaux, listes, piles et files

Définitions

Nœud

Élément constitutif de l'arbre. Les nœuds sont liés les uns aux autres par un lien de parenté. En général, un nœud à des enfants et un parent.

On peut parler de descendants pour l'ensemble des enfants d'un nœud, des enfants des enfants, etc.
On peut également parler d'ancêtres d'un nœud.

Arbre

Un arbre peut-être vide. Sinon il contient des nœuds. L'un de ces nœuds est la racine de l'arbre, il n'a pas de parent. Tous les autres nœuds ont exactement un parent.

Racine

C'est un nœud sans parent. Il doit y avoir exactement une racine dans un arbre non vide.

Dans l'exemple, la racine est le nœud A

Feuille

C'est un nœud sans enfant. La feuille est au bout d'une branche d'arbre.

Dans l'exemple, les nœuds D, E, C sont des feuilles

Profondeur d'un nœud

Pour un nœud donné, c'est le nombre de liens le séparant de la racine.

Dans l'exemple,

A a une profondeur de 0 ;
B une profondeur de 1 ;
D une profondeur de 2

On trouve des définitions contradictoires sur internet. Certains comptent une profondeur de 1 pour la racine et d'autres 0… Rien de grave, au besoin on précisera toujours quelle définition on choisit.

Hauteur d'un arbre

profondeur maximale dans l'arbre.

L'arbre ci-dessus a une hauteur de 2.

Là encore, on pourra trouver des définitions qui donnent à cet arbre une hauteur de 3.

Sous arbre

arbre formé en prenant un certain nœud comme racine et en ne conservant que ses descendants

Par exemple, considérons l'arbre formé par un système de fichier :

On peut considérer le sous arbre issu de Users\ :

Exemples d'arbres

Les arbres sont courants en informatique et ailleurs. En mathématique on connaît les arbres de probabilités et on pense bien sûr aux arbres généalogiques.

un arbre généalogique est un exemple qui peut être trompeur. Pour que l'arbre généalogique soit un arbre au sens qui m'intéresse, il faut que les racine soit moi et que mes nœuds enfants soient mes parents…

Adresse dans une rue

arborescence du système de fichier

dom d'une page html

dom du html avec javascript

<!-- exemple.html -->
<html>
  <head>
    <title>Page exemple</title>
    <script>
      window.onload = function() {
        //exécute la fonction lorsque le document est chargé
        var heading = document.createElement("h1");
        var heading_text = document.createTextNode("Un beau titre !");
        heading.appendChild(heading_text);
        document.body.appendChild(heading);
      }
    </script>
  </head>
  <body>
    <div>
      <p>Premier paragraphe</p>
      <p>Deuxième paragraphe avec <b>mot en gras</b></p>
    </div>
    <div>
      Deuxième bloc.
    </div>
  </body>
</html>

Cette page html a une structure hiérarchique. Remarquez l'indentation – non obligatoire – qui permet de bien voir cette hiérarchie.

Le script javascript qui s'exécute après chargement de la page utilise la variable document pour ajouter un enfant – appendChild – à l'élément document.body.

successions de coups possibles au échecs

Arbres binaires

Dans un arbre binaire, chaque nœud ne peut avoir que 0, 1 ou 2 enfants.

Exemple :

On pourra alors parler d'enfant gauche et enfant droit, de sous-arbre gauche sous-arbre droit :

L'enfant gauche de A est B, l'enfant droit de A est C
Les sous-arbres gauche et droit de A sont :

Arbre binaire de recherche (ABR)

On définit un critère d'ordre entre les nœuds. On peut dire qu'un nœud a une valeur supérieur à celle d'un autre selon ce critère.

Dans un ABR, pour un nœud donné, tous les nœuds du sous-arbre gauche ont une valeur inférieure et tous les nœuds du sous-arbre droit ont une valeur supérieure.

Par exemple, ici, les nœuds contiennent des doublets (nom, numéro). Il faudra donc préciser comment on choisit de trier.

Recherche d'un nœud

L'arbre est trié selon l'ordre alphabétique du nom. L'organisation de l'ABR facilite la recherche d'un nom.

Exemple : On cherche le numéro de "Malefoy Drago".

La simplicité de cet exemple peut tromper : Nous voyons sur la figure la totalité de l'arbre et nous voyons instantanément où se trouve Drago Malefoy. Il peut nous sembler inutile de chercher une organisation particulière. Mais gardez à l'esprit qu'en situation réelle, nous aurions un annuaire contenant des centaines de milliers de noms ! Aucun nom n'apparaîtra instantanément, il faudra chercher et il vaudrait mieux que l'on s'y prenne de façon efficace.

On commence par la racine, "Harry Potter".
Puisque "Malefoy Drago" est situé avant "Harry Potter" dans l'ordre alphabétique, on sait que l'on doit chercher dans le sous-arbre gauche.
On arrive à "Granger Hermione". Elle est inférieure à "Malefoy Drago" dans l'ordre alphabétique, on continue vers le sous arbre droit de "Granger Hermione".
On arrive à "Lovegood Luna". Elle est inférieure à "Malefoy Drago" dans l'ordre alphabétique, on continue vers le sous arbre droit de "Lovegood Luna".
On a trouvé le nœud de "Malefoy Drago".

Insertion d'un nœud

On cherche à insérer un nouvel item.

On crée un nœud contenant l'item,
on cherche l'endroit approprié pour inséré ce nouveau nœud,
on insère le nœud à l'emplacement trouvé.

Par exemple, supposons que l'on veuille insérer "Patil Parvati", "07.85.41.19.77",

On crée le nœud contenant le doublet,
on cherche un point d'insertion : "Patil Parvati" est
- à gauche de "Potter Harry",
- à droite de "Granger Hermione",
- à droite de "Lovegood Luna",
- à droite de "Malefoy Drago",
- mais "Malefoy Drago" n'a pas d'enfant droit, donc on peut insérer "Patil Parvati" comme enfant droit de "Malefoy Drago".

Suivant l'ordre d'insertion, l'arbre n'aura pas la même structure. Ce serait par exemple une mauvaise idée que d'insérer les noms par ordre alphabétique. En effet, un ABR est intéressant si la plupart des nœuds ont deux enfants. On pourrait imaginer un algorithme visant à réorganiser un arbre mal structuré mais on ne le fera pas ici.

Définition plus générale ?

Nous avons donné ici une première définition des arbres. Certains (informatique théorique, mathématique…) utilisent parfois une version plus générale : Ils disent qu'un arbre est un Graphe connexe et sans cycle.

Comme en mathématiques, les définitions peuvent être adaptées selon le besoin. Dans le cadre de la NSI, nous utilisons la définition plus simple qui a été donnée dans ce cours.