Arbres

Introduction

Vous avez déjà, pendant votre scolarité, vu ou utilisé des données structurées dans des arbres :

arbre généalogique

analyse de phrase

classement du vivant

Vous en avez peut-être même déjà croisés sans le savoir au fil de vos lectures...

Des gaffes et des dégâts (6)

Arbre représentant les papous

La structure d'arbre permet d'organiser des données de façon hiérarchique, ce qui simplifie ensuite la lecture et le traitement de ces données.
Il n'est pas facile de définir un arbre, car c'est en fait un cas particulier de graphe.

Quand nous aurons abordé les graphe nous pourrons dire qu'un arbre est un graphe connexe acyclique.

Nous retiendrons que dans un arbre il n'y a jamais de chemin d'un nœud vers lui même. Il n'y a jamais de cycle dans un arbre.

c'est un arbre

ce n'est PAS un arbre

D'après vous ce qui est représenté ci-dessous est-il un arbre ?
et si c'est le cas, que semble-t-il lui manquer ?

est-ce un arbre ???

SOLUTION

Les arbres sont très utilisés en informatique parce qu'ils permettent de stocker des données volumineuses et de rendre efficace l'accès à ces données. Voici deux exemples d'applications :

Arbre lexicographique

Les arbres lexicographiques sont à la base des algorithmes de compression de données. Les préfixes communs à plusieurs mots n'apparaissent qu'une seule fois dans l’arbre.

arbre lexicographique

Recopiez cet arbre et ajoutez les mots "bordure" et "binaire".

SOLUTION

Arbre arithmétique

Les arbres sont également utilisés en analyse syntaxique. vous avez déjà vu ce genre de choses avec les piles (vérification du parenthésage).

Voici l'arbre arithmétique qui représente l'expression (x + 1)(3y + 2) :

arbre arithmétique

A vous de représenter l'arbre correspondant à l'expression : 3 + (x/2 + 1).

SOLUTION

Mais on retrouve les arbres dans de multiples applications en informatique :

les répertoires et les fichiers sont organisés sous forme d'arbre ( = le système de fichiers )
les processus sous Linux sont organisés de manière hiérarchique en "processus-père" et "processus-fils"
le DOM ( Document Objet Model ) d'une page HTML organise les balises sous forme d'un arbre ( le DOM-tree )
....

Un peu de vocabulaire

Comme pour tout nouveau domaine de l'informatique, il va falloir se mettre d'accord sur une série de termes nécessaire pour décrire les arbres.

Racine, nœud, branche, feuille, père, fils

Un arbre est un ensemble organisé de nœuds. Chaque nœud a un père, sauf le nœud appelé racine.

Un nœud peut avoir un certain nombre de fils ( ou enfants ). Si un nœud n'a aucun fils, on dit que c'est une feuille.

Les nœuds sont reliés entre eux par des branches ( appelées quelquefois arêtes, ce qui est la terminologie utilisée pour les graphes ).

On dit que si les informaticiens mettent les racines des arbres en haut et leurs feuilles en bas, c'est parce qu'ils ne sortent jamais et donc ne savent pas à quoi ressemble un "vrai" arbre...:-)

On appelle sous-arbre l'ensemble des nœuds "descendants" d'un nœud donné ( donc pas seulement le nœud-fils ) :

étiquette

Chaque nœud d'un arbre peut porter ou non une étiquette. Cette étiquette peut être un entier, un texte, ou quelque chose de beaucoup plus complexe...

Dans l'arbre ci-contre, seules les feuilles ont des étiquettes.