Arbre binaire vs arbre de recherche binaire : différence entre l'arbre binaire et l'arbre de recherche binaire

introduction

Le tri est le processus consistant à organiser les données dans un ordre systématique afin qu'elles puissent être analysées plus efficacement. Le processus d'identification d'un enregistrement particulier est appelé recherche. Si les données sont correctement triées dans un ordre particulier, la recherche devient une tâche facile et efficace. Cet article traite de l'une des structures de données non linéaires les plus importantes, à savoir les arbres.

Les arbres sont principalement utilisés pour représenter des données en démontrant une relation hiérarchique entre les éléments. Par exemple, table des matières, arbre généalogique. Techniquement, un arbre peut être défini comme un ensemble fini 'T' d'un ou plusieurs nœuds tel qu'un nœud est désigné comme la racine de l'arbre et les autres nœuds sont divisés en n>=0 ensembles disjoints T1, T2, T3, T4 …. Tn et sont appelés sous-arbres ou enfants de ce nœud racine.

Qu'est-ce qu'un arbre binaire ?

Un arbre binaire est une structure de données non linéaire dans laquelle un nœud peut avoir 0, 1 ou 2 nœuds. Chaque nœud de l'arbre binaire est appelé nœud parent ou nœud enfant. Le nœud le plus haut de l'arbre binaire est appelé nœud racine. Chaque nœud parent peut avoir au plus 2 nœuds enfants qui sont le nœud enfant gauche et le nœud enfant droit.

Un nœud dans un arbre binaire a trois champs :

1. Élément de données - Il stocke la valeur de données qui doit être stockée par le nœud.
2. Pointeur vers l'enfant gauche - Il stocke la référence (ou l'adresse) du nœud enfant gauche.
3. Pointeur vers l'enfant droit - Il stocke la référence au nœud enfant droit.

De cette manière, plusieurs nœuds sont combinés pour construire un arbre binaire.

Un arbre binaire peut être représenté comme :

La source

D'après la figure ci-dessus, le nœud racine 2 a deux enfants (ou nœuds enfants), 7 et 5. 7 est appelé nœud enfant gauche et 5 est appelé nœud enfant droit. De cette manière, chacun des nœuds enfants agit comme un nœud parent pour plusieurs autres nœuds et représente ensemble l'arbre binaire.

Découvrez: Types d'arbre binaire

Terminologies utilisées dans l'arbre binaire

Nœud : La représentation de base d'un point de terminaison dans un arbre.

Nœud racine : le nœud le plus élevé d'un arbre binaire.

Nœud parent : Si un nœud est connecté à un autre nœud par des arêtes, il est appelé nœud parent. Dans un arbre binaire, un nœud parent peut avoir un maximum de 2 nœuds enfants.

Nœud enfant : Si un nœud a un prédécesseur, il est appelé nœud enfant.

Nœud feuille : un nœud qui n'a pas de nœud enfant est appelé nœud feuille.

Profondeur d'un nœud : C'est la distance entre le nœud racine et ce nœud particulier dont la profondeur doit être mesurée.

Hauteur de l'arbre : C'est la distance la plus longue entre le nœud racine et le nœud feuille.

Ce sont quelques terminologies de base d'un arbre binaire. Avec cette compréhension de base d'un arbre binaire, passons à un avancement de l'arbre binaire connu sous le nom d'arbre de recherche binaire.

Lisez aussi : Algorithme de recherche binaire : fonction, avantages, complexité temporelle et spatiale

Qu'est-ce qu'un arbre de recherche binaire

Comme son nom l'indique, un arbre de recherche binaire ou BST est un arbre utilisé pour trier, récupérer et rechercher des données. C'est aussi un type de structure de données non linéaire dans laquelle les nœuds sont disposés dans un ordre particulier. Par conséquent, il est également appelé « arbre binaire ordonné ». Il a les propriétés suivantes :

• Le sous-arbre gauche d'un nœud a des nœuds qui sont seulement inférieurs à la clé de ce nœud.
• Le sous-arbre droit d'un nœud a des nœuds qui sont seulement supérieurs à la clé de ce nœud.
• Chaque nœud a des clés distinctes et les doublons ne sont pas autorisés dans l'arborescence de recherche binaire.
• Les sous-arbres gauche et droit doivent également être un arbre de recherche binaire.

Visualisons ce concept pour avoir une compréhension claire des arbres de recherche binaires.

La source

Dans la figure ci-dessus, nous voyons que la valeur du nœud racine est 8. Avec un examen plus approfondi, on observe que toutes les valeurs du sous-arbre de gauche sont inférieures à la valeur du nœud racine et toutes les valeurs du sous-arbre de droite ont valeurs supérieures au nœud racine. De plus, il est à noter que chaque valeur dans l'arbre de recherche binaire est unique et qu'il n'y a pas de doublons. Ainsi, les propriétés de l'arbre de recherche binaire indiquées ci-dessus sont vérifiées.

Dans encore un autre exemple, nous voyons que bien que les sous-arbres gauche et droit soient des arbres de recherche binaires avec des valeurs uniques dans tout l'arbre. La valeur au nœud feuille dans le sous-arbre de gauche est 12, ce qui est supérieur à la valeur du nœud racine qui est 12. Ainsi, cela ne satisfait pas la propriété de la BST et, par conséquent, ce n'est pas un arbre de recherche binaire.

Opération de recherche dans un BST –

Considérez un arbre de recherche binaire avec les valeurs indiquées ci-dessous. Comprenons comment l'opération de recherche est effectuée pour obtenir 9 à partir de l'arbre de recherche binaire.

La source

Afin d'effectuer la recherche binaire, nous allons d'abord ranger tous les entiers dans un tableau trié. C'est ce qu'on appelle l'espace de recherche. Cet espace de recherche se compose de deux pointeurs, appelés pointeurs de début et de fin. Le tableau de l'arbre de recherche binaire donné ci-dessus est représenté par :

La première étape consiste à calculer la valeur médiane du tableau et à la comparer avec la valeur à rechercher, 9 dans notre cas. Ceci est fait en calculant n/2, où n est le nombre total d'éléments dans le tableau (BST) et c'est 6. Ainsi, le 3ème élément est l'élément du milieu qui est 5.

Maintenant que l'élément du milieu est comparé à 9 et qu'il n'est pas égal (supérieur), l'opération de recherche va s'effectuer sur le tableau de droite. De cette manière, l'opération de recherche est réduite de moitié, comme indiqué ci-dessous :

Dans l'étape suivante, l'élément du milieu est calculé et s'avère être 9, ce qui correspond à notre élément à rechercher.

Arbre binaire vs arbre de recherche binaire -

Maintenant que nous avons une compréhension de base de l'arbre binaire et des arbres de recherche binaires, résumons rapidement certaines des différences entre les deux.

Conclusion

Ainsi, nous en déduisons que bien que l'arbre binaire et l'arbre de recherche binaire aient une structure hiérarchique commune avec une collection de nœuds, ils présentent plusieurs différences dans leur application. Un arbre binaire est une structure de base avec une règle simple selon laquelle aucun parent ne doit avoir plus de 2 enfants, tandis que l'arbre de recherche binaire est une variante de l'arbre binaire suivant un ordre particulier avec lequel les nœuds doivent être organisés.

Si vous êtes curieux d'en savoir plus sur l'arbre binaire par rapport à l'arbre de recherche binaire, consultez le diplôme PG de IIIT-B & upGrad en science des données qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, du mentorat avec l'industrie experts, 1-on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.

Apprenez des cours de science des données en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.