Arbre enraciné - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Un arbre binaire

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 (L´informatique - contraction d´information et automatique - est le domaine...), c'est également une structure de données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent...) récursive utilisée pour représenter ce type de graphes.

Vocabulaire

Dans un arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en...), 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 (Le contexte d'un évènement inclut les circonstances et conditions qui l'entourent; le...), un nœud peut désigner soit un nœud interne (En France, ce nom désigne un médecin, un pharmacien ou un chirurgien-dentiste, à la...), soit un nœud interne ou externe (feuille) de l'arbre.

La profondeur d'un nœud est la distance, i.e. le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) d'arêtes, de la racine au nœud. La hauteur d'un arbre est la plus grande profondeur d'une feuille (La feuille est l'organe spécialisé dans la photosynthèse chez les végétaux...) de l'arbre. La taille d'un arbre est son nombre de nœuds (en comptant les feuilles ou non), la longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus...) 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 (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans...), 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 ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un...), afin d'implanter les algorithmes sur les arbres.

Les fichiers et dossiers dans un système de fichiers (Un système de fichiers (file system ou filesystem en anglais) ou système de gestion de...) sont généralement organisés sous forme arborescente. Voir par exemple la FHS.

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 (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées...), notamment pour gérer des bases de données, ou pour l'indexation de fichiers. Ils permettent alors des recherches rapides et efficaces. Nous vous en donnons ici les principaux exemples :

  • Les arbres binaires dont chaque nœud a au plus deux fils : ils sont en fait utilisés sous forme d'arbres binaires de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue...), de tas, d'AVL, ou encore d'arbres rouge-noir. Les deux derniers exemples sont des cas particuliers d'arbres équilibrés, c'est-à-dire d'arbres dont les sous-branches ont presque la même hauteur.
  • Les arbres n-aires qui sont une généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de...) des arbres binaires : chaque nœud a au plus n fils. Les arbres 2-3-4 et les arbres B en sont des exemples d'utilisation et sont eux aussi des arbres équilibrés.

Parcours

Arbre d'exemple pour les parcours d'arbre

Parcours en largeur (La largeur d’un objet représente sa dimension perpendiculaire à sa longueur, soit...)

Le parcours en largeur correspond à un parcours par niveau de nœuds de l'arbre. Un niveau est un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) de nœuds internes ou de feuilles situés à la même profondeur — on parle aussi de nœud ou de feuille de même hauteur dans l'arbre considéré. L'ordre de parcours d'un niveau donné est habituellement conféré, de manière récursive, par l'ordre de parcours des nœuds parents — nœuds du niveau immédiatement supérieur.

Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, C, D, E, F puis G.

Parcours en profondeur

Le parcours en profondeur est un parcours récursif sur un arbre. Dans le cas général, deux ordres sont possibles :

  • Parcours en profondeur préfixe : dans ce mode de parcours, le nœud courant est traité avant ses descendants. Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, D, E, C, F puis G.
  • Parcours en profondeur suffixe : dans ce mode de parcours, le nœud courant est traité après ses descendants. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C puis A. Ce mode de parcours correspond à une notation polonaise inversée.

Pour les arbres binaires, on peut également faire un parcours infixe, c'est-à-dire traiter le nœud courant entre les nœuds gauche et droit. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, B, E, A, F, C puis G.

Page générée en 0.052 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique