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

Différence clé - arbre binaire contre Arbre de recherche binaire
 

Une structure de données est un moyen systématique d'organiser des données pour les utiliser efficacement. L'organisation des données à l'aide de la structure de données devrait réduire le temps d'exécution ou le temps d'exécution. De plus, la structure des données doit nécessiter une quantité minimale de mémoire. Parfois, les données peuvent être disposées dans une structure d'arbre. Un arbre représente un nœud connecté par des bords. Le nœud le plus haut est le racine. Chaque nœud peut avoir un maximum de deux nœuds. Ils sont connus comme nœuds enfants. Le nœud à gauche du nœud parent est le nœud enfant gauche tandis que le nœud à droite du nœud parent est le nœud droit.   L'arbre binaire et l'arbre de recherche binaire sont deux structures de données d'arbre. Un arbre binaire est un type de structure de données où chaque nœud parent peut avoir au plus deux nœuds enfants. L'arbre de recherche binaire est un arbre binaire où l'enfant gauche ne contient que des nœuds avec des valeurs inférieures ou égales au nœud parent, et où l'enfant droit ne contient que des nœuds avec des valeurs supérieures à celle du nœud parent. C'est le différence clé. Contrairement aux structures de données telles que les tableaux, l'arbre binaire et l'arbre de recherche binaire n'ont pas de limite supérieure pour stocker les données.

CONTENU

1. Aperçu et différence clé
2. Qu'est-ce que l'arbre binaire
3. Qu'est-ce que l'arbre de recherche binaire
4. Similitudes entre l'arbre binaire et l'arbre de recherche binaire
5. Comparaison côte à côte - arbre binaire vs arbre de recherche binaire sous forme tabulaire
6. Résumé

Qu'est-ce que l'arbre binaire?

Lors de la disposition des données dans une structure d'arbre, le nœud en haut de l'arbre est connu sous le nom de nœud racine. Il ne peut y avoir qu'une seule racine pour tout l'arbre. Tout nœud sauf que le nœud racine a un bord vers le haut vers un nœud. Il s'appelle le nœud parent. Le nœud sous le code parent est appelé son nœud enfant. Chaque nœud parent peut avoir un maximum de deux nœuds enfants. Ils sont appelés nœud enfant gauche et nœud enfant droit. Un nœud sans nœud enfant est appelé un noeud feuille. Il n'y a aucun moyen spécifique d'organiser des données dans l'arbre binaire. Il y a un chemin du nœud racine à chaque nœud.

Figure 01: Exemple d'arbre binaire

Ci-dessus est un exemple d'arbre binaire. L'élément 2, en haut de l'arbre, est la racine. Chaque nœud a un maximum de deux nœuds. Si un arbre contient des boucles ou si un nœud contient plus de deux nœuds, il ne peut pas être classé comme un arbre binaire. Pour passer d'un nœud à l'autre, il y a toujours un chemin. Les nœuds enfants du nœud racine 2 sont 7 et 5. Il est également possible pour un nœud de n'avoir pas de nœuds.  Mais aucun nœud ne peut avoir plus de deux nœuds. Le bon élément de la racine est 5. Cet élément 5 est le nœud parent pour le nœud enfant 9. Les nœuds 4 et 11 n'ont pas d'éléments enfants. Par conséquent, ce sont des nœuds de feuilles.

L'arbre binaire est utilisé pour stocker des données dans l'ordre hiérarchique. Il est similaire à la structure de fichiers de l'ordinateur. La structure de données comme un tableau peut stocker une quantité spécifique de données. Mais dans un arbre binaire, il n'y a pas de limite supérieure sur le nombre de nœuds.

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

Un arbre de recherche binaire est une structure de données d'arbre binaire. Semblable à un arbre binaire, l'arbre de recherche binaire peut également avoir deux nœuds. Tout nœud sauf que le nœud racine a un bord vers le haut vers un nœud. Il s'appelle le nœud parent. Le nœud sous un lien donné par son bord vers le bas est appelé son nœud enfant. Un nœud sans nœud enfant est appelé nœud feuille. Chaque nœud parent peut avoir un maximum de deux nœuds. Il y a des nœuds enfants faisant référence à un nœud enfant gauche et au nœud enfant droit. L'élément le plus haut est appelé le nœud racine. L'enfant gauche ne contient que des nœuds avec des valeurs inférieures ou égales au nœud parent. Le bon enfant ne contient que des nœuds avec des valeurs supérieures ou égales au nœud parent.

Figure 02: Exemple d'arbre de recherche binaire

L'élément 8 est l'élément le plus haut. Par conséquent, c'est le nœud racine. Si 3 est un nœud parent, alors 1 et 6 sont des nœuds enfants. Le 1 est le nœud enfant gauche tandis que 6 est le nœud enfant droit. L'enfant gauche contient des valeurs inférieures ou égales au nœud parent. Lorsque 3 est le nœud parent, le côté gauche doit avoir un élément inférieur ou égal à 3. Dans cet exemple, c'est 1. Le bon enfant ne contient que des nœuds avec des valeurs supérieures au nœud parent. Lorsque 3 est le nœud parent, le bon nœud enfant doit avoir une valeur plus élevée que 3. Dans cet exemple, il est 6. De même, il existe un certain ordre pour organiser chaque élément de données un arbre de recherche binaire. Il s'agit d'une structure de données fournit un moyen efficace d'effectuer des données de tri, de récupération et de recherche.

Quelles sont les similitudes entre l'arbre binaire et l'arbre de recherche binaire?

• L'arbre binaire et l'arbre de recherche binaire sont des structures de données hiérarchiques.
• L'arbre binaire et l'arbre de recherche binaire ont une racine.
• L'arbre binaire et l'arbre de recherche binaire peuvent avoir un maximum de deux nœuds enfants.

Quelle est la différence entre l'arbre binaire et l'arbre de recherche binaire?

Résumé - Arbre binaire contre Arbre de recherche binaire 

Une structure de données est un moyen d'organiser les données. Parfois, les données peuvent être disposées dans une structure d'arbre. Deux d'entre eux sont un arbre binaire et l'arbre de recherche binaire. Cet article a discuté de la différence entre l'arbre binaire et l'arbre de recherche binaire. Un arbre binaire est un type de structure de données où chaque nœud parent peut avoir au plus deux nœuds enfants. L'arbre de recherche binaire est un arbre binaire où l'enfant gauche ne contient que des nœuds avec des valeurs inférieures ou égales au nœud parent, et où l'enfant droit ne contient que des nœuds avec des valeurs supérieures au nœud parent.

Téléchargez le PDF de l'arbre binaire contre l'arbre de recherche binaire

Vous pouvez télécharger la version PDF de cet article et l'utiliser à des fins hors ligne selon la note de citation. Veuillez télécharger la version PDF ici: différence entre l'arbre binaire et l'arbre de recherche binaire

Référence:

1.Point, tutoriels. «Arbre de structures de données et d'algorithmes.», Tutorials Point, 8 janvier. 2018. Disponible ici
2.Différence entre l'arbre binaire et l'arbre de recherche binaire. | javapedia.Net, javapedia.net, 15 février. 2017. Disponible ici

Image gracieuseté:

1.«Arbre binaire» Derrick Coetzee - propre travail, (domaine public) via Commons Wikimedia
2.'Binary Search Tree' par aucun auteur lisible par machine fourni.  (basé sur les réclamations du droit d'auteur)., (Domaine public) via Commons Wikimedia