<page> <title>Arbre (informatique)</title> <id>86120</id> <revision> <id>28586794</id> <timestamp>2008-04-12T19:37:49Z</timestamp> <contributor> <username>Tucsouffle</username> <id>98793</id> </contributor> <comment>/* Exemples d'arbres */ +arbre bicolore</comment> <text xml:space="preserve">{{Voir homonymes| Arbre (homonymie) }} [[Image:binary_tree.svg|right|200px|thumb|Un [[arbre binaire]]]] == Généralités == En [[informatique]], un '''arbre''' est une [[structure de données]] récursive générale, représentant un [[arbre (mathématiques)|arbre au sens mathématique]]. C'est un cas particulier de [[graphe (théorie des graphes)|graphe]] qui n'a qu'une seule source et aucun cycle. Dans un arbre, on distingue deux catégories d'éléments : * les <font id="feuille">'''feuilles'''</font>, éléments ne possédant pas de fils dans l'arbre ; * les <font id="noeud">'''nÅ“uds'''</font> internes, éléments possédant des fils (sous-branches). La '''racine''' de l'arbre est le nÅ“ud ne possédant pas de parent. La hauteur d'un arbre est la longueur du plus grand chemin de la racine à une feuille. Chaque nÅ“ud possède une <font id="étiquette">'''étiquette'''</font>, qui est en quelque sorte le « contenu » de l'arbre. 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. Par exemple, les dossiers de [[Windows 98]] et [[MS-DOS]] forment un arbre. 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 [[base de données|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 [[arbre binaire|arbres binaires]] dont chaque nÅ“ud a au plus deux fils : ils sont en fait utilisés sous forme d'[[arbre binaire de recherche|arbres binaires de recherche]], de [[Tas_(informatique)|tas]], d'[[Arbre_AVL|AVL]], ou encore d'[[arbre rouge-noir|arbres rouge-noir]]. Les deux derniers exemples sont des cas particuliers d'[[arbre équilibré|arbres équilibrés]], c'est-à -dire d'arbres dont les sous-branches ont environ la même hauteur. *Les arbres n-aires qui sont une généralisation des arbres binaires : chaque nÅ“ud a au plus n fils. Les [[arbre 2-3-4|arbres 2-3-4]] et les [[arbre B|arbres B]] en sont des exemples d'utilisation et sont eux aussi des [[arbre balancé|arbres balancés]]. == Construction == Pour construire un arbre à partir de cases ne contenant que des informations, on peut procéder de l'une des trois façons suivantes : # Créer une structure de données composée de : ## l'étiquette (la valeur contenue dans le nÅ“ud), ## un lien vers ''chaque'' nÅ“ud fils, ## un arbre particulier, l'arbre vide, qui permettra de caractériser les feuilles. Une feuille a pour fils des arbres vides uniquement. # Créer une structure de données composée de : ## l'étiquette (la valeur contenue dans le nÅ“ud), ## un lien vers le « premier » nÅ“ud fils (nÅ“ud fils gauche le cas échéant), ## un autre lien vers le nÅ“ud frère (le « premier » nÅ“ud frère sur la droite le cas échéant). # Créer une structure de données composée de : ## l'étiquette (la valeur contenue dans le nÅ“ud), ## un lien vers le nÅ“ud père. On note qu'il existe d'autres types de représentation propres à des cas particuliers d'arbres. Par exemple, le [[tas]] est représenté par un tableau d'étiquettes. == Parcours== [[image:Boretti_Arbre_niveau.png|thumb|Arbre d'exemple pour les parcours d'arbre]] ===Parcours en largeur=== Le <b>parcours en largeur</b> correspond à un parcours par ''niveau'' de nÅ“uds de l'arbre. Un niveau est un ensemble de nÅ“uds internes ou<ref>Le « ou » est large : un ''niveau'' peut recouvrir à la fois des nÅ“uds et des feuilles ; en effet, toutes les feuilles d'un arbre ne sont pas nécessairement situées à la même « distance » du nÅ“ud racine.</ref> de feuilles situés à la même « distance »<ref>La notion de ''distance'' est relative dans ce contexte : elle correspond usuellement au nombre d'arcs — ou d'arêtes — composant le plus court chemin depuis le nÅ“ud racine jusqu'au nÅ“ud considéré, interne ou feuille. En théorie, elle peut être plus élaborée. Un arbre étant un graphe particulier, ses arcs ou arêtes peuvent être pondérés. Cette pondération peut servir à l'évaluation d'une mesure entre deux nÅ“uds quelconques de l'arbre. On parle de ''longueur'' du (plus court) chemin entre deux nÅ“uds d'un arbre, la longueur étant distincte de la différence des hauteurs respectives.</ref> du nÅ“ud racine — 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 <tt>A</tt>, <tt>B</tt>, <tt>C</tt>, <tt>D</tt>, <tt>E</tt>, <tt>F</tt> puis <tt>G</tt>. <!-- Balise à déplacer dans une section ad hoc (section Références ou Notes) si d'autres notes sont créées. --> <references /> ===Parcours en profondeur=== Le <b>parcours en profondeur</b> est un parcours [[récursif]] sur un arbre. Il existe trois ordres pour cette méthode de parcours. ====Parcours en profondeur préfixé==== Dans ce mode de parcours, le nÅ“ud courant est traité avant le traitement des nÅ“uds gauches et droits. Ainsi, si l'arbre précédent est utilisé, le parcours sera <tt>A</tt>, <tt>B</tt>, <tt>D</tt>, <tt>E</tt>, <tt>C</tt>, <tt>F</tt> puis <tt>G</tt>. ====Parcours en profondeur infixé==== Dans ce mode de parcours, le nÅ“ud courant est traité entre le traitement des nÅ“uds gauches et droits. Ainsi, si l'arbre précédent est utilisé, le parcours sera <tt>D</tt>, <tt>B</tt>, <tt>E</tt>, <tt>A</tt>, <tt>F</tt>, <tt>C</tt> puis <tt>G</tt>. ====Parcours en profondeur suffixé==== Dans ce mode de parcours, le nÅ“ud courant est traité après le traitement des nÅ“uds gauches et droits. Ainsi, si l'arbre précédent est utilisé, le parcours sera <tt>D</tt>, <tt>E</tt>, <tt>B</tt>, <tt>F</tt>, <tt>G</tt>, <tt>C</tt> puis <tt>A</tt>. Ce mode de parcours correspond à une [[notation polonaise inversée]]. == Exemples d'arbres == * Les [[Arbre binaire|arbres binaires]]; * Les [[Arbre B|arbres B]] (B-Tree); * Les [[Arbre équilibré|arbres équilibrés]]; * Les [[Arbre syntaxique|arbres syntaxiques]]; * Les [[tas]]; * Les [[arbre couvrant de poids minimal|arbres couvrants]]; * Les [[octree]]s; * Les [[Arbre AVL|Arbres AVL]]; * Les [[Arbre bicolore|Arbres bicolore]]. {{Wiktionnaire|arbre}} [[Catégorie:Arbre (structure de données)]] [[da:Træ (datastruktur)]] [[de:Baum (Graphentheorie)]] [[en:Tree (data structure)]] [[es:Ãrbol (estructura de datos)]] [[id:Pohon (struktur data)]] [[it:Albero (informatica)]] [[ja:æœ¨æ§‹é€ (ãƒ‡ãƒ¼ã‚¿æ§‹é€ )]] [[lt:Medis (duomenų struktÅ«ra)]] [[nl:Tree]] [[no:Tre (datastruktur)]] [[pl:Drzewo (informatyka)]] [[pt:Ãrvore (estrutura de dados)]] [[uk:Дерево (Ñтруктура даних)]] [[zh:æ ‘ (æ•°æ®ç»“æž„)]]</text> </revision> </page>