Arbre binaire

Un arbre binaire est un arbre structure de données dans lequel chaque noeud a au plus deux enfants, qui sont appelés l’enfant gauche et droit de l’enfant . Une définition récursive en utilisant simplement la théorie des ensembles notions est qu'un (non vide) arbre binaire est un tuple (L, S, R), où L et R sont des arbres binaires ou l’ensemble vide et S est un si ensemble Singleton.

Certains auteurs permettent également que l’arbre binaire soit l’ensemble vide.

Du point de vue de la théorie des graphes, les arbres binaires (et K-aires) définis ici sont en réalité des arborescences .  Un arbre binaire peut ainsi être également appelé arborescence bifurquante, terme qui apparaît dans certains livres de programmation très anciens, avant la terminologie de l'informatique moderne a prévalu. Il est également possible d'interpréter une arborescence binaire sous forme de graphe non orienté plutôt que dirigé, auquel cas un temps binaire est une arborescence ordonnée et enracinée.  Certains auteurs utilisent l’arbre binaire enraciné au lieu de l’arbre binaire pour souligner le fait que l’arbre est enraciné, mais comme défini ci-dessus, un arbre binaire est toujours enraciné. Un arbre binaire est un cas particulier d'un arbre K-aire ordonné, où k vaut 2.
En mathématiques, ce que l’on appelle arbre binaire peut varier considérablement d’un auteur à l’autre. Certains utilisent la définition couramment utilisée en informatique , mais d’autres le définissent comme tout non-feuille ayant exactement deux enfants et n’ordonnant pas nécessairement (à gauche ou à droite) les enfants non plus.
En intelligence artificelle, les arbres binaires sont utilisés de deux manières très différentes:
•                        Tout d'abord, comme moyen d'accéder aux nœuds en fonction d'une valeur ou d'une étiquette associée à chaque nœud.  arbres binaires marqués de cette manière sont utilisés pour mettre en œuvre les arbres binaires de recherche et bi tas naire, et sont utilisés pour l’efficacité la recherche et le tri . La désignation de nœuds non racine en tant qu'enfant gauche ou droit, même s'il n'y a qu'un seul enfant présent, importe dans certaines de ces applications, en particulier dans les arborescences de recherche binaires.  Cependant, la disposition des nœuds particuliers dans l’arbre ne fait pas partie des informations conceptuelles. Par exemple, dans un arbre de recherche binaire normal, le placement des noeuds dépend presque entièrement de l'ordre dans lequel ils ont été mis à jour et peut être réorganisé (par exemple par équilibrage) sans en changer le sens.
•                        Deuxièmement, en tant que représentation de données avec une structure bifurcante pertinente . Dans de tels cas, la disposition particulière des nœuds situés sous et / ou à gauche ou à droite des autres nœuds fait partie des informations (en d’autres termes, sa modification modifierait la signification). Des exemples courants se produisent avec le codage de Huffman et les cladogrammes . La division quotidienne des documents en chapitres, sections, paragraphes, etc., est un exemple analogue avec des arborescences naires plutôt que des arbres binaires.