Arbre (informatique)

Généralités

En informatique, un arbre est une structure de données récursive générale, représentant un arbre au sens mathématique. C'est un cas particulier de graphe qui n'a qu'une seule source et aucun cycle.

Dans un arbre, on distingue deux catégories d'éléments :

les feuilles, éléments ne possédant pas de fils dans l'arbre ;
les nœuds internes, éléments possédant des fils (sous-branches).

La racine de l'arbre est le nœud ne possédant pas de parent.

La hauteur d'un arbre est la longueur du plus grand chemin de la racine à une feuille.

Chaque nœud possède une étiquette, qui est en quelque sorte le « contenu » de l'arbre. L'étiquette peut être très simple: un nombre entier, par exemple. Elle peut également être aussi complexe que l'on veut: un objet, une instance d'une structure de données, un pointeur, etc. Il est presque toujours obligatoire de pouvoir comparer les étiquettes selon une relation d'ordre total, afin d'implanter les algorithmes sur les arbres.

Par exemple, les répertoires sous la plupart des systèmes d'exploitation actuels (Microsoft Windows, Unix dont Linux et Mac OS X...) forment un arbre.

Les arbres sont en fait rarement utilisés en tant que tels, mais de nombreux types d'arbres avec une structure plus restrictive existent et sont couramment utilisés en algorithmique, notamment pour gérer des bases de données. Nous vous en donnons ici les principaux exemples:

les arbres binaires dont chaque noeud a au plus deux fils: ils sont en fait utilisés sous forme d'arbres binaires de recherche, de tas, d'AVL, ou encore d'arbres rouge-noir. Les deux derniers exemples sont des cas particuliers d'arbres balancés, c'est à dire d'arbres dont les sous-branches ont environ la même hauteur.
les arbres n-aires qui sont une généralisation des arbres binaires: chaque noeud a au plus n fils. Les arbre 2-3-4 et les arbres B en sont des exemples d'utilisation et sont eux aussi des arbres balancés.

Construction

Pour construire un arbre à partir de cases ne contenant que des informations, on procède généralement ainsi:

Créer une structure de données composée de l'étiquette (la valeur contenue dans le nœud),
D'un lien vers chacun des nœud fils
D'un arbre particulier, l'arbre vide, qui permettra de caractériser les feuilles: une feuille a pour fils des arbres vides uniquement

On peut également procéder comme suit :

Créer une structure de données composée de l'étiquette (la valeur contenue dans le nœud),
D'un lien vers le nœud fils
D'un autre lien vers le nœud frère

Une autre manière est de disposer

D'une structure de données composée de l'étiquette (la valeur contenue dans le nœud),
D'un lien vers le nœud père

On notera qu'il existe d'autres types de représentation propres à des cas particuliers d'arbes: par exemple le tas est représenté par un tableau d'étiquettes.

Parcours

Parcours en largeur

Le parcours en largeur parcourt un arbre par niveau. Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, C, D, E, F puis G.

Parcours en profondeur

Le parcours en profondeur est un un parcours récursif sur un arbre. Il existe trois ordres pour cette méthode de parcours.

Parcours en profondeur préfixé

Dans ce mode de parcours, le nœud courant est traité avant le traitement des nœuds gauches et droites. Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, D, E, C, F puis G.

Parcours en profondeur infixé

Dans ce mode de parcours, le nœud courant est traité entre le traitement des nœuds gauches et droites. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, B, E, A, F, C puis G.

Parcours en profondeur suffixé

Dans ce mode de parcours, le nœud courant est traité après le traitement des nœuds gauches et droites Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C puis A. Ce mode de parcours correspond à une notation polonaise inversée.

Exemples d'arbres

Algorithmique

Gourt Home::Gourt :: Arbre (informatique)