|
Publié le par Chloé MAHALIN

Structure de données

Qu'est-ce qu'un arbre ?

Définition

Un arbre est composé d'éléments appelés :

  • Noeuds pour les éléments ayant des enfants (Node en anglais)
  • Feuilles pour les éléments n'ayant pas d'enfant (Leaf en anglais).

Par défaut, tous les éléments d'un arbre sont catégorisés par le mot noeud. Les noeuds sont reliés par des arêtes, en programmation, ce sont des pointeurs.

L'arbre part d'un noeud racine (root) unique. Ce noeud connaît les enfants qui sont en-dessous de lui. Ces enfants connaissent à leur tour les enfants en-dessous, et ainsi de suite.

arbre

La profondeur d'un noeud caractérise le nombre de noeuds entre la racine et le noeud en question. La hauteur de l'arbre est la plus grande des profondeur de l'arbre.

Dans certaines implémentations, un noeud connaît également son prédécesseur.

Bien entendu, pour que l'arbre fonctionne, il est raisonnable de créer une relation entre les différents noeuds, qu'elle soit en profondeur, ou architecturale.

Exemple : On pourrait imaginer un noeud animal, qui contiendrait deux noeuds mammifères et oiseaux. Le noeud mammifère aurait pour enfants : chien et chat.

Dans quels cas

C'est le mécanisme par défaut des systèmes de fichiers (fileSystem).

L'arbre est une structure couramment utilisée au niveau de l'indexation, notamment dans les bases de données. En équilibrant l'arbre au niveau des valeurs, il est possible de retrouver une valeur en O(log(n)) au lieu de O(n).