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

Quel est 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 noeud de la structure de données est directement connecté à un nombre arbitraire de noeuds de chaque côté, appelés enfants. Un pointeur nul représente l'arborescence binaire. Il n'y a pas d'ordre particulier sur l'organisation des nœuds dans l'arborescence binaire. Les nœuds sans enfants sont appelés des nœuds feuille ou externes..

En termes simples, il définit une fonction d'étiquetage organisée sur les nœuds, qui attribue à son tour 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 ne limitent pas le nombre de nœuds, car ils sont liés à l'aide de pointeurs, comme les listes liées. Les principales fonctions de l’arbre binaire sont notamment la représentation des données hiérarchiques, le tri des listes de données, l’efficacité des opérations d’insertion / suppression, etc. Les nœuds d’arbre sont représentés à l’aide de 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 rangés dans l'ordre, d'où le nom de «arbre binaire ordonné». C'est une structure de données basée sur des nœuds qui fournit un moyen efficace et rapide de trier, de récupérer et de rechercher des données. Pour chaque nœud, les éléments du sous-arbre de gauche doivent être inférieurs ou égaux à la clé de son nœud parent (LP). Il ne devrait y avoir aucune clé en double. En termes simples, il s'agit d'un type particulier de structure de données d'arborescence binaire 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 de données, ainsi que la mise en œuvre de tables de consultation permettant de rechercher des éléments à l’aide de leurs clés uniques, comme la recherche du numéro de téléphone d’une personne par son nom. Les clés uniques sont triées de manière organisée, de sorte 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 de récupérer rapidement les éléments stockés dans l'arborescence, chaque clé de nœud étant minutieusement comparée au nœud racine, ce qui supprime la moitié de l'arborescence..

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 deux noeuds enfant au maximum. chaque noeud contient un pointeur gauche, un pointeur droit et un élément de données. Il n'y a pas d'ordre particulier sur l'organisation des nœuds dans l'arborescence. L'arbre de recherche binaire, en revanche, est un arbre binaire ordonné dans lequel il existe un ordre relatif à la manière dont les nœuds doivent être organisés..
2. Structure  de Arbre binaire et arbre de recherche binaire- Le nœud le plus haut dans l'arborescence représente le pointeur racine dans une arborescence binaire, tandis que les pointeurs gauche et droit représentent les plus petits arbres de chaque côté. C'est une forme d'arborescence spécialisée qui représente les données dans une arborescence. L'arbre de recherche binaire, par contre, est un type d'arbre binaire dans lequel tous les noeuds du sous-arbre de gauche sont inférieurs ou égaux à la valeur du noeud racine et ceux du sous-arbre de droite sont supérieurs ou égaux à la valeur. du noeud racine.
3. Opération de Arbre binaire et arbre de recherche binaire- Un arbre binaire peut être tout ce qui a deux enfants et un parent. Les opérations courantes pouvant être effectuées sur une arborescence binaire sont l'insertion, la suppression et la traversée. Les arbres de recherche binaires sont davantage des arbres binaires triés permettant une recherche, une insertion et une suppression rapides et efficaces des éléments. Contrairement aux arbres binaires, les arbres de recherche binaires gardent leurs clés triées, de sorte que recherche met généralement en œuvre la recherche binaire pour les opérations..
4. Les types de Arbre binaire et arbre de recherche binaire- Il existe différents types d'arbres binaires, le plus commun étant “Arbre binaire complet”, “Arbre binaire complet”, “Arbre binaire parfait” et “Arbre binaire étendu”. Certains types d’arbres de recherche binaires courants incluent les arbres en T, les arbres en AVL, les arbres Splay, les arbres Tango, les arbres rouges-noirs, etc..

Arbre binaire et arbre de recherche binaire: Tableau comparatif

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

Alors que les deux simulent une structure arborescente hiérarchique représentant une collection de nœuds avec chaque nœud représentant une valeur, ils sont assez différents les uns des autres en termes de mise en œuvre et d'utilisation. Une arborescence binaire suit une règle simple selon laquelle chaque nœud parent n'a pas plus de deux nœuds enfants, alors qu'une arborescence de recherche binaire n'est qu'une variante de l'arborescence binaire qui suit un ordre relatif à la manière dont les nœuds doivent être organisés dans une arborescence..