Différence entre l'arbre binaire et l'arbre de recherche binaire

Qu'est-ce que l'arbre binaire?

L'arbre binaire est une structure de données hiérarchique dans laquelle chaque nœud a zéro, un ou au plus, deux enfants. Chaque nœud contient un pointeur «gauche», un pointeur «droit» et un élément de données. Le pointeur «racine» représente le nœud le plus haut de l'arbre. Chaque nœud de la structure de données est directement connecté au nombre arbitraire de nœuds de chaque côté, appelés enfants. Un pointeur nul représente l'arbre binaire. Il n'y a pas d'ordre particulier sur la façon dont les nœuds doivent être organisés dans l'arbre binaire. Les nœuds sans enfants sont appelés nœuds de feuilles ou nœuds externes.

En termes simples, il définit une fonction d'étiquetage organisée sur les nœuds, qui à son tour attribue une valeur aléatoire à chaque nœud. Tout ce qui a deux enfants et un nœud parent est un arbre binaire. Les arbres binaires sont utilisés pour stocker des informations qui forment une hiérarchie comme le système de fichiers sur votre ordinateur personnel. Contrairement aux tableaux, les arbres n'ont pas de limite supérieure sur le nombre de nœuds car ils sont liés à l'aide de pointeurs, comme des listes liées. Les principales fonctions de l'arbre binaire comprennent la représentation de données hiérarchiques, les listes de données de tri, la fourniture d'opérations d'insertion / supprimer efficaces, etc. Les nœuds d'arborescence sont représentés en utilisant des structures en C.

Qu'est-ce que l'arbre de recherche binaire?

Un arbre de recherche binaire est un type de structure de données d'arbre binaire dans lequel les nœuds sont disposés dans l'ordre, donc également appelés «arbre binaire ordonné». Il s'agit d'une structure de données basée sur des nœuds qui fournit un moyen efficace et rapide de trier, récupérer, rechercher des données. Pour chaque nœud, les éléments du sous-arbre gauche doivent être inférieurs ou égaux à la clé de son nœud parent (LP). Il ne devrait pas y avoir de clés en double. En termes simples, c'est un type spécial de structure de données d'arbres binaires qui stocke et gère efficacement les éléments en mémoire.

Il permet un accès rapide aux informations, à l'insertion et à la suppression des données, et il peut être utilisé pour implémenter des tables de recherche qui permettent la recherche d'éléments par leurs clés uniques, comme la recherche de numéro de téléphone d'une personne. Les clés uniques sont triées de manière organisée, afin que la recherche et d'autres opérations dynamiques puissent être effectuées à l'aide de la recherche binaire. Il prend en charge trois opérations principales: la recherche d'éléments, l'insertion d'éléments et la suppression d'éléments. L'arbre de recherche binaire permet une récupération rapide des éléments stockés dans l'arbre car chaque clé de nœud est complètement comparée au nœud racine, qui rejette la moitié de l'arbre.

Différence entre l'arbre binaire et l'arbre de recherche binaire

1. Définition de l'arbre binaire et de l'arbre de recherche binaire - L'arbre binaire est une structure de données hiérarchique dans laquelle un enfant peut avoir zéro, un ou un maximum de deux nœuds enfants; Chaque nœud contient un pointeur gauche, un pointeur droit et un élément de données. Il n'y a pas d'ordre particulier sur la façon dont les nœuds doivent être organisés dans l'arbre. L'arbre de recherche binaire, en revanche, est un arbre binaire ordonné dans lequel il y a un ordre relatif à la façon dont les nœuds doivent être organisés.
2. Structure de Arbre binaire et arbre de recherche binaire- Le nœud le plus haut de l'arbre représente le pointeur racinaire dans un arbre binaire, et les pointeurs gauche et droit représentent les plus petits arbres de chaque côté. C'est une forme d'arbre spécialisée qui représente les données dans une structure d'arbre. L'arbre de recherche binaire, en revanche, est un type d'arbre binaire dans lequel tous les nœuds du sous-arbre gauche sont inférieurs ou égaux à la valeur du nœud racine et de celui du sous-arbre droit sont supérieurs ou égaux à la valeur du nœud racine.
3. Opération de Arbre binaire et arbre de recherche binaire- L'arbre binaire peut être tout ce qui a deux enfants et un parent. Les opérations communes qui peuvent être effectuées sur un arbre binaire sont l'insertion, la suppression et la traversée. Les arbres de recherche binaires sont des arbres binaires plus triés qui permettent une recherche, une insertion et une suppression rapides et efficaces. Contrairement aux arbres binaires, les arbres de recherche binaires gardent leurs clés triées, donc la recherche implémente généralement la recherche binaire d'opérations.
4. Les types de Arbre binaire et arbre de recherche binaire- Il existe différents types d'arbres binaires, le commun étant «l'arbre binaire complet», «arbre binaire complet», «arbre binaire parfait» et «arbre binaire étendu». Certains types courants d'arbres de recherche binaires comprennent des arbres T, des arbres AVL, des arbres évasés, des tango, des arbres rouges-noir, etc.

Arbre binaire vs. Arbre de recherche binaire: graphique de comparaison

Résumé de l'arbre binaire et de l'arbre de recherche binaire

Alors que les deux simulent une structure d'arbre hiérarchique représentant une collection de nœuds avec chaque nœud représentant une valeur, ils sont très différents les uns des autres en termes de façon dont ils peuvent être implémentés et utilisés. Un arbre binaire suit une règle simple selon laquelle chaque nœud parent n'a pas plus de deux nœuds enfants, tandis qu'un arbre de recherche binaire n'est qu'une variante de l'arbre binaire qui suit un ordre relatif sur la façon dont les nœuds doivent être organisés dans un arbre.