Informatique
Publié le 07/27/2017, rédigé par Chloé MAHALIN

Structure de données

Qu'est-ce qu'un arbre ?

Définition

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

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).

Sélection d'articles :

ITAMETIS

Bienvenue sur l'université d'ITAMETIS où ses membres s'expriment librement sur les sujets qui leur plaisent. C'est un lieu de partage et d'échanges afin de fournir à tous, une base de connaissances accessible de manière libre et gratuite.

Qui nous sommes

Politique de Confidentialité