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 d'arbres, mais sont très utiles et faciles à mettre en œuvre.Une implémentation typique d'un arbre binaire repose sur un nœud racine lié à une série de nœuds qui composent l'arbre lui-même par des variables de pointeur.Ce type d'arbre tire son nom du fait qu'aucun nœud dans l'arbre ne peut avoir plus de deux enfants.
Les structures de données de l'arborescence sont disponibles dans de nombreuses variétés.Ils sont composés de différents nœuds, qui sont organisés dans un motif hiérarchique.Un seul nœud, la racine, est le point d'accès par lequel l'ensemble de l'arborescence de données peut être recherché ou autrement manipulé.Ce nœud racine pointe vers le nœud supérieur de l'arbre lui-même.
Tout nœud dans un arbre, à l'exception du nœud le plus haut, aura un nœud parent qui est situé au-dessus de lui dans la hiérarchie de l'arbre.Il peut également avoir des nœuds enfants, situés en dessous.Un nœud donné est accessible par le biais de ceux au-dessus de celle-ci dans l'arborescence et donne accès à ceux en dessous.
Les structures de données d'arbre binaire permettent à chaque nœud d'avoir plus de deux enfants.Un nœud donné peut donc avoir zéro, un ou deux nœuds pour enfants qui y sont attachés.Les arbres binaires ordinaires permettent aux nœuds avec un certain nombre d'enfants à tout moment de l'arbre.Ils ne placent également aucune restriction sur la façon dont les valeurs stockées dans les nœuds qui composent une arbre sont disposés.
Les structures de données sont les plus utiles lorsqu'ils améliorent la vitesse à laquelle les données peuvent être accessibles par un ordinateur, et les versions modifiées des arbres binaires sont utilisées pouraméliorer leur efficacité.Un arbre de recherche binaire est celui dans lequel toutes les valeurs de données situées sur la branche descendante gauche à partir d'un nœud donné ont des valeurs égales ou inférieures à la valeur stockée dans ce nœud.Les valeurs sur le côté droit d'un nœud dans un arbre binaire ordonné doivent, à leur tour, être supérieures à la valeur dans le nœud de base.Cette commande 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 dans toute l'arborescence pour localiser une seule information dans cette configuration.L'arbre binaire le plus efficace, en revanche, est celui dans lequel chaque nœud sauf pour ceux au bas de l'arbre a deux enfants et où tous les nœuds de feuilles, les nœuds inférieurs de l'arbre, sont à la même distance de la racine.