Arborescence

Un article de Wikipédia, l'encyclopédie libre.

Une arborescence permet d'organiser les données en mémoire ou sur disque, de manière logique et hiérarchisée. C'est un cas pratique d'utilisation de la 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é

Sommaire 1 Usage pour la gestion des disques 2 Les différentes façons de linéariser une arborescence 3 Arité 4 Types de parcours 4.1 Préfixe 4.2 Infixe 4.3 Suffixe 5 Notation 6 Voir aussi

[modifier] 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.

[modifier] 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.

[modifier] 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 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 90% 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.

[modifier] Types de parcours

[modifier] 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.

[modifier] Infixe

Dans ce mécanisme, le parent est inséré entre ses enfants. Les Mathématiques et la logique humaine procèdent souvent ainsi. Sujet Verbe Complément. Exemple : 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.

[modifier] Suffixe

Le parent est mis après ses enfants. Cette logique semble bien peu humaine mais elle est très utilisée en informatique, pile, Forth, machine virtuelle Java, Postscript et autres. Exemple : 2 3 +

Cette notation est ardue pour l'être humain mais très facile à mettre en place d'un point de vue informatique ou automate.

[modifier] 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
  • \ : 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

[modifier] Voir aussi

• Théorie des graphes

• Portail de l’informatique