Qu'est-ce qu'un arbre binaire?
Un arbre binaire est un type de structure de données utilisé dans la programmation informatique pour stocker, trier et accéder aux informations. Les arbres binaires sont la variété la plus simple des arbres, mais ils sont très utiles et faciles à mettre en œuvre. Une implémentation typique d’une arborescence binaire repose sur un nœud racine lié à une série de nœuds qui constituent l’arborescence elle-même par des variables de pointeur. Ce type d'arbre tire son nom du fait qu'aucun nœud de l'arborescence ne peut avoir plus de deux enfants.
Les structures de données arborescentes sont nombreuses. Ils sont constitués de différents nœuds, organisés selon un schéma hiérarchique. Un seul nœud, la racine, est le point d'accès à travers lequel toute l'arborescence de données peut être recherchée ou manipulée. Ce nœud racine pointe vers le nœud supérieur de l’arborescence.
Tout nœud dans une arborescence, à l'exception du nœud le plus haut, aura un nœud parent situé au-dessus de celui-ci dans la hiérarchie de l'arborescence. Il peut également avoir des nœuds enfants, situés en dessous. Un nœud donné est accessible via ceux situés au-dessus de celui-ci dans l'arborescence et permet d'accéder à ceux situés au-dessous de celui-ci.
Les structures de données d'arborescence binaire permettent à chaque nœud de ne pas avoir plus de deux enfants. Un nœud donné peut donc être associé à zéro, un ou deux nœuds enfants. Les arbres binaires ordinaires autorisent les nœuds avec un nombre quelconque d'enfants à n'importe quel point de l'arbre. Ils n'imposent aucune restriction sur la manière dont les valeurs stockées dans les nœuds qui composent une arborescence sont organisées.
Les structures de données sont particulièrement utiles lorsqu'elles accélèrent l'accès aux données par un ordinateur et que des versions modifiées des arbres binaires sont utilisées pour améliorer leur efficacité. Un arbre de recherche binaire est un arbre dans lequel toutes les valeurs de données situées sur la branche descendante de gauche d'un noeud donné ont des valeurs égales ou inférieures à la valeur stockée dans ce noeud. Les valeurs situées à droite d'un nœud dans une arborescence binaire ordonnée doivent, à leur tour, être supérieures à la valeur du nœud de base. Cet ordre de données permet d'écrire un algorithme de recherche beaucoup plus efficace.
La forme d'un arbre binaire est également importante pour déterminer l'efficacité d'un algorithme de recherche. La variété la moins efficace d'un arbre binaire est celle dans laquelle chaque nœud n'a qu'un seul enfant. Un ordinateur peut avoir besoin d'examiner chaque élément de données de toute l'arborescence pour localiser une seule information dans cette configuration. L’arbre binaire le plus efficace, en revanche, est un arbre dans lequel chaque noeud, à l’exception de ceux du bas de l’arbre, a deux enfants et où tous les noeuds feuille, les noeuds du bas de l’arbre, sont à la même distance de la racine.