Arborescence

En mathématiques, plus précisément dans la théorie des graphes : une arborescence est un arbre comportant un sommet particulier , nommé racine de l'arborescence, à partir duquel il existe un chemin unique vers tous 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 efficace 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 nœud peut posséder N feuilles, mais chaque feuille n'est possédée que par un seul nœud.

En informatique, elle désigne aussi un composant d'interface graphique qui présente une vue hiérarchique de l'information. Chaque élément (souvent appelé branche ou nœud) peut avoir un certain nombre de sous-éléments. Ceci est souvent représenté sous forme d'une liste indentée.

Un élément peut être déplié pour révéler des sous-éléments, s'ils existent, et replié pour cacher des sous-éléments.

La vue en arborescence apparaît souvent dans les applications de gestion de fichiers, où elle permet à l'utilisateur de naviguer dans les répertoires du système de fichiers. Elle est également utilisée pour présenter les données hiérarchiques, comme un document XML.

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ée et rapide.

Linéarisation 
Du fait qu'une arborescence est souvent représentée sous la forme d'un arbre graphique et que les systèmes d'écriture classique sont linéaires, différents types de représentation sont utilisés et coexistent, selon la méthode de parcours utilisée et le domaine d'application.

Arités 
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.

Types de parcours

Préfixe 
Dans ce mécanisme, le parent est mis en premier, puis suivent ses enfants. L'ordre/commande est par devant, les éléments complémentaires ensuite. Voir aussi l'exemple linguistique VSO. Exemple : + 2 3

Cette notation est simple à comprendre pour l'être humain et se programme facilement.

Infixe 
Dans ce mécanisme, le parent est inséré entre ses enfants, comme c'est par exemple le cas en mathématiques : 2 + 3.

Le gros problème de l'infixe est l'ambiguïté et on doit souvent recourir à des parenthèses. Ainsi 10+20*30 doit-il s'analyser comme (10+20)*30 ou comme 10+(20*30) ? Pour lever une partie des difficultés, il existe une priorité des opérateurs dans bon nombre de langages.

Suffixe 
Le parent est mis après ses enfants. Cette logique est fréquemment utilisée en informatique (pile, Forth, machine virtuelle Java, Postscript et autres) : 2 3 +

Le langage des sourds-muets possède une syntaxe assez proche de ce type de notation : il plante le décor avant, positionne les acteurs puis indique l'action en dernier.

Circonfixe 
Le parent se met devant et derrière ses enfants. Il peut s'agir du même mot (add...add), de deux mots totalement distincts (for...next / begin...end) ou de deux mots dont l'un est forgé sur la base de l'autre (while...wend / while...endwhile / for...rof). Les symboles circonfixes les plus courants sont : (...), [...], {...}, <...>, "..." et '...'

Notation 

 Arité fixe
 Préfixe, arité fixe
 + 2 3
 père Alain Bernard
 mange chat souris
 Infixe, arité fixe
 2 + 3
 Alain estLePèreDe 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  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 
 / : remonter, indique le dernier enfant
 - : rester sur le même niveau, les enfants intermédiaires, implicitement le 
 | : 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 - l'affixe indique le 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 quatre0
 (deux plus trois) fois quatre → deux0 plus1 trois0 fois2 quatre0

Notes et références

Voir aussi

Articles connexes 
 Arbre enraciné
 Théorie des graphes
 Répertoire (informatique)
 Gestionnaire de fichiers
 Logiciel de généalogie
 Nombre de Strahler

Système de fichiers
Arbre (structure de données)