Différence clé - Arbre binaire vs arbre de recherche binaire
Une structure de données est un moyen systématique d'organiser les 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. En outre, la structure de données doit nécessiter une quantité minimale de mémoire. Parfois, les données peuvent être organisées dans une structure arborescente. Un arbre représente un nœud relié par des arêtes. Le nœud le plus haut est la racine. Chaque nœud peut avoir un maximum de deux nœuds. Ils sont appelés 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 arborescentes. 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 de gauche ne contient que des nœuds avec des valeurs inférieures ou égales au nœud parent, et où l'enfant de droite ne contient que des nœuds avec des valeurs supérieures au nœud parent. C'est la principale différence. 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 des données.
Qu'est-ce que l'arbre binaire ?
Lorsque vous organisez les données dans une structure arborescente, le nœud au sommet de l'arbre est appelé nœud racine. Il ne peut y avoir qu'une seule racine pour tout l'arbre. Tout nœud, à l'exception du 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 nœud feuille. Il n'y a pas de manière spécifique d'organiser les données dans l'arbre binaire. Il existe 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 arbre binaire. Pour aller 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 qu'un nœud n'ait aucun nœud. Mais un nœud ne peut pas avoir plus de deux nœuds. L'élément droit de la racine est 5. Cet élément 5 est le nœud parent du 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 feuilles.
L'arbre binaire est utilisé pour stocker les 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 au 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, à l'exception du 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 donné connecté par son bord vers le bas est appelé son nœud enfant. Un nœud sans nœud enfant est appelé un nœud feuille. Chaque nœud parent peut avoir un maximum de deux nœuds. Il existe des nœuds enfants référençant un nœud enfant gauche et un nœud enfant droit. L'élément le plus haut est appelé le nœud racine. L'enfant de gauche ne contient que des nœuds avec des valeurs inférieures ou égales au nœud parent. L'enfant droit 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. C'est donc 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 de 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, il s'agit de 1. L'enfant droit ne contient que des nœuds avec des valeurs supérieures au nœud parent. Lorsque 3 est le nœud parent, le nœud enfant droit doit avoir une valeur supérieure à 3. Dans cet exemple, il s'agit de 6. De même, il existe un certain ordre pour organiser chaque élément de données dans un arbre de recherche binaire. C'est une structure de données qui fournit un moyen efficace d'effectuer le tri, la récupération et la recherche de données.
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 ?
Arbre binaire vs arbre de recherche binaire |
|
| Un arbre binaire est un type de structure de données où chaque nœud parent peut avoir au maximum deux nœuds enfants. | L'arbre de recherche binaire est un arbre binaire où l'enfant de gauche ne contient que des nœuds avec des valeurs inférieures ou égales au nœud parent, et où l'enfant de droite ne contient que des nœuds avec des valeurs supérieures au nœud parent. |
| Ordre d'organisation des données | |
| Un arbre binaire n'a pas d'ordre spécifique pour organiser les éléments de données. | Un arbre de recherche binaire a un ordre spécifique pour organiser les éléments de données. |
| Utilisation | |
| Un arbre binaire est utilisé comme une recherche efficace de données et d'informations dans une structure arborescente. | Un arbre de recherche binaire est utilisé pour insérer, supprimer et rechercher les données. |
Résumé - Arbre binaire vs arbre de recherche binaire
Une structure de données est une façon d'organiser les données. Parfois, les données peuvent être organisées dans une structure arborescente. Deux d'entre eux sont l'arbre binaire et l'arbre de recherche binaire. Cet article traite 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 de gauche ne contient que des nœuds avec des valeurs inférieures ou égales au nœud parent, et où l'enfant de droite ne contient que des nœuds avec des valeurs supérieures au nœud parent.
Télécharger le PDF de Binary Tree vs Binary Search Tree
Vous pouvez télécharger la version PDF de cet article et l'utiliser à des fins hors ligne conformément à la note de citation. Veuillez télécharger la version PDF ici: Différence entre l'arbre binaire et l'arbre de recherche binaire
