Ê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 GraphSearch.
Concept
Arbre binaire
Résumé
En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père.
Au niveau le plus élevé, niveau 0, il y a un nœud racine. Au niveau directement inférieur, il y a au plus deux nœuds fils. En continuant à descendre aux niveaux inférieurs, on peut en avoir quatre, puis huit, seize, etc. c'est-à-dire la suite des puissances de deux. Un nœud n'ayant aucun fils est appelé feuille.
Le niveau d'un nœud, autrement dit la distance entre ce nœud et la racine, est appelé profondeur. La hauteur de l'arbre est la profondeur maximale d'un nœud. Un arbre réduit à un seul nœud est de hauteur 0.
Les arbres binaires peuvent notamment être utilisés en tant qu'arbre binaire de recherche ou en tant que tas binaire.
right|192px|thumb|Un exemple simple d'arbre binaire
La théorie des graphes utilise la définition suivante : un arbre binaire est un graphe connexe acyclique, tel que le degré de chaque nœud (ou vertex) soit au plus 3.
La racine d'un arbre binaire est le nœud d'un graphe de degré maximum 2. Avec une racine ainsi choisie, chaque nœud aura un unique parent défini et deux fils ; toutefois, ces informations sont insuffisantes pour distinguer un fils droit d'un fils gauche. Si nous négligeons cette condition de connexité, et qu'il y a de multiples éléments connectés, on appellera cette structure une forêt.
Un arbre binaire (ou binaire-unaire) est un arbre avec une racine dans lequel chaque nœud a au plus deux fils.
Un arbre binaire strict ou localement complet est un arbre dont tous les nœuds possèdent zéro ou deux fils.
Un arbre binaire dégénéré est un arbre dans lequel tous les nœuds internes n'ont qu'un seul fils. Ce type d'arbre n'a qu'une unique feuille et peut être vu comme une liste chaînée.
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.