Arborescence - Définition

Introduction

En mathématiques, plus précisément en théorie des graphes, une arborescence est un arbre comportant un sommet particulier r, nommé racine de l'arborescence à partir duquel il existe un chemin unique vers tout les autres sommets.

En informatique, cette notion désigne souvent celle d'arbre de la théorie des graphes. Une arborescence désigne alors généralement une organisation des données en mémoire, de manière logique et hiérarchisée utilisant une structure algorithmique d'arbre. Cette organisation rend plus efficaces la consultation et la manipulation des données stockées. Les usages les plus courants en sont :

• l'arborescence de fichiers, qui est l'organisation hiérarchique des fichiers sur une partition, et dans certains cas de partitions entre elles, par exemple: partitions virtuelles (« lecteurs logiques ») dans des partitions réelles.
• le tri arborescent en mémoire
• les fichiers en mode séquentiel indexé

La logique générale de l'arborescence coïncide avec le modèle relationnel du SQL : 1 vers N et réciproquement 1 vers 1. Un noeud peut posséder N feuilles, mais chaque feuille ne possède qu'un seul noeud.

Usage pour la gestion des disques

À la base d'une arborescence se trouve un répertoire appelé la racine. Ce répertoire peut contenir des fichiers et des répertoires, qui eux-mêmes peuvent contenir la même chose.

Si les fichiers et les répertoires sont placés de manière cohérente, la recherche de fichier est relativement aisé et rapide.

Arité

Plus simplement, l'arité indique le nombre d'arguments ou d'enfants utiles ou nécessaires à une fonction ou un parent. Ainsi dans 10+20, l'addition (+) a besoin d'un terme à gauche (10) puis d'un autre à droite (20), son arité est donc de 2. Dans abs(mavar), la valeur absolue n'a besoin que d'un seul argument (mavar), son arité est de 1. En Prolog, la clause pere(alain,bernard). a une arité de 2 car la relation "pere" exige un parent et fatalement un enfant.

L'arité peut être fixe comme elle peut être variable. Ainsi l'opérateur * est d'arité fixe à 2 dans la plupart des langages informatiques, on écrit 2*3 pour exprimer un calcul. Par contre, en Lisp, on peut écrire (* 2 3 4) pour exprimer 2*3*4 ou bien (* 2 3 4 5) ce qui est une arité variable.

Les différentes façons de linéariser une arborescence

Le gros problème est qu'une arborescence est souvent représentée sous la forme d'un arbre graphique et que le langage et l'écriture classique sont linéaires. Depuis longtemps, différents types de représentation co-existent, selon la méthode de parcours utilisée et le domaine d'application.

Notation

Arité fixe

• Préfixe, arité fixe
  • + 2 3
  • père Alain Bernard
  • mange chat souris
• Infixe, arité fixe
  • 2 + 3
  • Alain est_le_père_de Bernard
  • chat mange souris
• Suffixe, arité fixe
  • 2 3 +
  • Alain Bernard père
  • chat souris mange

Arité variable

• Préfixe, arité variable
  • (+ 2 3 4)
  • add(2,3,4)
  • printf("%d %d %s",n,m,t)
  • begin ... end
  • add:3 20 30 40 (on indique le nombre d'arguments)
  • add 3 20 30 40 (le 1^er argument indique l'arité utile)
• Infixe, arité variable
  • a-b (soustraction) -b (négatif)
  • a*b (multiplication) *b (contenu du pointeur en langage C)
• Suffixe, arité variable
  • (2 3 4 +)
  • marqueurpile 2 3 4 add
  • 20 30 40 add:3
  • 20 30 40 3 add (le dernier argument indique l'arité utile)
• Autre système - Arbo graphique
  • \ : descendre, indique le 1^er enfant
  • / : remonter, indique le dernier enfant
  • - : rester sur le même niveau, les enfants intermédiaires, implicitement le 1^er parent
  • | : arité 1, descendre puis remonter (en cas d'enfant unique)
  • Exemple : 2*3*4+5*6 → préfixage -add\mul\2-3/4\mul\5/6
• Autre système - Taaluketti (langue artificielle; ce système est très proche du précédent dans sa logique)
  • Mécanisme suffixé, avec des suffixes pour indiquer l'arité.
  • aucun suffixe : élément seul
  • -s : élément le plus à gauche et non unique
  • -n : élément le plus à droite et non unique
  • -k : élément médiant, ni le plus à gauche, ni le plus à droite
  • ba be → (ba)be • bas ben bi → (ba be)bi • bas bek bin bo → (ba be bi)bo • bas bek bik bon bu → (ba be bi bo)bu
• Autre système - Infixe+niveau
  • On ajoute le numéro de niveau avant ou après
  • 0 signifie que c'est une feuille ou un symbole terminal
  • deux plus trois → deux0 plus1 trois0
  • deux plus (trois fois quatre) → deux0 plus2 trois0 fois1 quatre
  • (deux plus trois) fois quatre → deux0 plus1 trois0 fois2 quatre0