Qu’est-ce qu’un arbre en informatique ? #

Arbre :

Les arbres sont des structures de données

hiérarchiques,

naturellement récursives,

utilisées pour représenter des ensembles de données structurées hiérarchiquement.

Les dossiers d’un ordinateur forment un arbre

.
Les balises d’une page html forment un arbre.

Particularité de la structure des arbres #

Elle non linéaire (par opposition aux listes, files, piles, tableaux)
Elle peut être définie récursivement :
- L’arbre est un ensemble de nœuds accessibles depuis un nœud racine
- Chaque nœud étant une structure composée d’une valeur et d’une liste de références vers d’autres nœuds
- contraintes :
  1. aucune référence n’est dupliquée (chaque nœud a un unique parent),
  2. aucune référence ne désigne le nœud racine (qui n’a donc pas de parent).

Arbres binaires #

On se restreint aux arbres binaires pour lesquels la liste des références vers d’autres nœuds comporte au plus deux éléments.

Vocabulaire #

un nœud est caractérisé par
- une donnée (on parle aussi d’étiquette),
- un nombre fini de fils.
une arête relie deux nœuds. Chaque nœud, à l’exception de la racine, est relié à un autre nœud, son père, par exactement une arête entrante. Chaque nœud peut avoir une ou plusieurs arêtes sortantes le reliant à ses fils. On parle aussi de lien.
la racine d’un arbre est le seul nœud sans père.
un chemin est une liste de nœuds reliés par des arêtes.
une branche est le chemin le plus court reliant un nœud à la racine.
les fils sont l’ensemble des nœuds reliés à un même nœud par des arêtes entrantes.
le père ou parent est le nœud relié à ses nœuds fils par une arête sortante.
un sous-arbre est l’ensemble des nœuds et arêtes d’un nœud parent et de ses descendants.
une feuille est un nœud sans fils.
un nœud interne est un nœud qui n’est pas une feuille.

Pour assurer la cohérence de ces définitions, on considère que l’arbre vide n’est pas un nœud.

→ Quelques mesures sur les arbres #

la taille d’un arbre est le nombre de nœuds de l’arbre.
la profondeur d’un nœud est le nombre d’arêtes sur la branche qui le relie à la racine. Racine : profondeur nulle.
la hauteur d’un arbre est la profondeur maximale de l’ensemble des nœuds de l’arbre.
l’arité d’un nœud est le nombre de fils du nœud.
l’arité d’un arbre est le nombre maximal de fils des nœuds de l’arbre.

→ Définition. Arbre binaire #

Un arbre binaire est donc un arbre d’arité deux.

Un arbre binaire est

soit l’arbre vide, noté $\Delta$ ;
soit un triplet (e, g, d), appelée nœud, dans lequel
- e est l’élément, ou encore étiquette, de la racine de l’arbre,
- g est le sous-arbre gauche de l’arbre, et
- d est le sous-arbre droit de l’arbre.

Les sous-arbres gauche et droit d’un arbre binaire non vide sont eux-mêmes des arbres binaires. La structure d’arbre binaire est donc une structure récursive.

on appelle fils gauche, resp. fils droit, le sous-arbre gauche, resp. droit, d’un nœud.

Caractériser les arbres binaires #

Les arbres binaires sont caractérisés par le fait que chaque nœud possède au plus deux fils.

Autres caractéristiques, permettant d’identifier des arbres pour lesquels le coût de certaines opérations sera minimal, ou de définir des algorithmes spécifiques.

Un arbre binaire filiforme ou dégénéré est un arbre dans lequel tous les nœuds internes n’ont qu’un seul fils.
(Un arbre filiforme ne possède donc qu’une unique feuille.)
Un arbre binaire localement complet ou arbre binaire strict est un arbre dont tous les nœuds internes possèdent exactement deux fils.
(Autrement dit, un arbre binaire localement complet est un arbre dont chaque nœud possède zéro ou 2 fils. L’arbre vide n’est pas localement complet.)
Un arbre binaire complet est un arbre binaire localement complet dans lequel toutes les feuilles sont à la même profondeur. (Il s’agit d’un arbre dont tous les niveaux sont remplis.)
Un arbre binaire parfait est un arbre dans lequel tous les niveaux sont remplis à l’exception éventuelle du dernier, et dans ce cas les feuilles du dernier niveau sont alignées à gauche.
Un arbre binaire équilibré est un arbre dont les deux fils sont des arbres équilibrés dont les hauteurs diffèrent d’au plus une unité.
Ainsi, l’accès à n’importe lequel des nœuds est en moyenne minimisé.

Arbres - résumé