Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Arbre enraciné
Résumé
En théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent.
En informatique, c'est également une structure de données récursive utilisée pour représenter ce type de graphes.
Dans un arbre, on distingue deux catégories d'éléments :
les feuilles (ou nœuds externes), é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 l'unique nœud ne possédant pas de parent. Les nœuds (les pères avec leurs fils) sont reliés entre eux par une arête. Selon le contexte, un nœud peut désigner un nœud interne ou externe (feuille) de l'arbre.
La profondeur d'un nœud est la distance, i.e. le nombre d'arêtes, de la racine au nœud. La hauteur d'un arbre est la plus grande profondeur d'une feuille de l'arbre. La taille d'un arbre est son nombre de nœuds (en comptant les feuilles ou non), la longueur de cheminement est la somme des profondeurs de chacune des feuilles.
Les arbres peuvent être étiquetés. Dans ce cas, chaque nœud possède une étiquette, qui est en quelque sorte le « contenu » du nœud. 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.
Les fichiers et dossiers dans un système de fichiers sont généralement organisés sous forme arborescente. Voir par exemple la .
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, ou pour l'indexation de fichiers. Ils permettent alors des recherches rapides et efficaces.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.