Qu'est-ce qu'un arbre de recherche binaire?
L'arbre de recherche binaire est un algorithme avancé utilisé pour analyser le nœud, ses branches gauche et droite, qui sont modélisées dans une structure arborescente et retournent la valeur. Le BST est conçu sur l'architecture d'un algorithme de recherche binaire de base; par conséquent, il permet des recherches, des insertions et des suppressions de nœuds plus rapides. Cela rend le programme vraiment rapide et précis.
Dans ce didacticiel sur la structure des données, vous apprendrez:
- Qu'est-ce qu'un arbre de recherche binaire?
- Attributs de l'arborescence de recherche binaire
- Pourquoi avons-nous besoin d'un arbre de recherche binaire?
- Types d'arbres binaires
- Comment fonctionne l'arbre de recherche binaire?
- Termes importants
Attributs de l'arborescence de recherche binaire
Un BST est composé de plusieurs nœuds et se compose des attributs suivants:
- Les nœuds de l'arborescence sont représentés dans une relation parent-enfant
- Chaque nœud parent peut avoir zéro nœud enfant ou un maximum de deux sous-nœuds ou sous-arbres sur les côtés gauche et droit.
- Chaque sous-arbre, également connu sous le nom d'arbre de recherche binaire, a des sous-branches à droite et à gauche d'elles-mêmes.
- Tous les nœuds sont liés par des paires clé-valeur.
- Les clés des nœuds présents sur le sous-arbre de gauche sont plus petites que les clés de leur nœud parent
- De même, les clés des nœuds de sous-arborescence de gauche ont des valeurs inférieures à celles de leurs nœuds parent.
- Il y a le nœud principal ou le niveau parent 11. En dessous, il y a des nœuds / branches gauche et droit avec leurs propres valeurs de clé
- Le sous-arbre de droite a des valeurs de clé supérieures au nœud parent
- Le sous-arbre de gauche a des valeurs que le nœud parent
Pourquoi avons-nous besoin d'un arbre de recherche binaire?
- Les deux principaux facteurs qui font de l'arbre de recherche binaire une solution optimale à tous les problèmes du monde réel sont la vitesse et la précision.
- Du fait que la recherche binaire est dans un format de type branche avec des relations parent-enfant, l'algorithme sait dans quel emplacement de l'arbre les éléments doivent être recherchés. Cela diminue le nombre de comparaisons clé-valeur que le programme doit effectuer pour localiser l'élément souhaité.
- De plus, dans le cas où l'élément à rechercher est supérieur ou inférieur au nœud parent, le nœud sait quel côté de l'arborescence rechercher. La raison en est que le sous-arbre gauche est toujours inférieur au nœud parent, et le sous-arbre droit a des valeurs toujours égales ou supérieures au nœud parent.
- BST est couramment utilisé pour mettre en œuvre des recherches complexes, des logiques de jeu robustes, des activités de saisie semi-automatique et des graphiques.
- L'algorithme prend en charge efficacement des opérations telles que la recherche, l'insertion et la suppression.
Types d'arbres binaires
Trois types d'arbres binaires sont:
- Arbre binaire complet: Tous les niveaux des arbres sont pleins d'exceptions possibles du dernier niveau. De même, tous les nœuds sont pleins, dirigeant l'extrême gauche.
- Arbre binaire complet: tous les nœuds ont 2 nœuds enfants à l'exception de la feuille.
- Arbre binaire équilibré ou parfait: Dans l'arborescence, tous les nœuds ont deux enfants. De plus, il y a le même niveau de chaque sous-nœud.
Comment fonctionne l'arbre de recherche binaire?
L'arbre a toujours un nœud racine et d'autres nœuds enfants, que ce soit à gauche ou à droite. L'algorithme effectue toutes les opérations en comparant les valeurs avec la racine et ses autres nœuds enfants dans le sous-arbre gauche ou droit en conséquence.
Dépend de l'élément à insérer, rechercher ou supprimer, après la comparaison, l'algorithme peut facilement supprimer le sous-arbre gauche ou droit du nœud racine.
BST propose principalement les trois types d'opérations suivants pour votre utilisation:
- Recherche: recherche l'élément dans l'arborescence binaire
- Insérer: ajoute un élément à l'arborescence binaire
- Supprimer: supprimer l'élément d'une arborescence binaire
Chaque opération a sa propre structure et méthode d'exécution / d'analyse, mais la plus complexe de toutes est l'opération de suppression.
Opération de recherche
Commencez toujours l'analyse de l'arborescence au niveau du nœud racine, puis déplacez-vous plus loin vers le sous-arbre droit ou gauche du nœud racine selon que l'élément à localiser est inférieur ou supérieur à la racine.
- L'élément à rechercher est 10
- Comparez l'élément avec le nœud racine 12, 10 <12, par conséquent vous vous déplacez vers le sous-arbre de gauche. Pas besoin d'analyser le bon sous-arbre
- Maintenant, comparez 10 avec le nœud 7, 10> 7, alors passez au sous-arbre de droite
- Ensuite, comparez 10 avec le nœud suivant, qui est 9, 10> 9, regardez dans le bon sous-arbre enfant
- 10 correspond à la valeur du nœud, 10 = 10, renvoie la valeur à l'utilisateur.
Insérer une opération
C'est une opération très simple. Tout d'abord, le nœud racine est inséré, puis la valeur suivante est comparée au nœud racine. Si la valeur est supérieure à la racine, elle est ajoutée au sous-arbre de droite, et si elle est inférieure à la racine, elle est ajoutée au sous-arbre de gauche.
- Il y a une liste de 6 éléments qui doivent être insérés dans un BST dans l'ordre de gauche à droite
- Insérez 12 comme nœud racine et comparez les valeurs suivantes 7 et 9 pour l'insérer en conséquence dans le sous-arbre droit et gauche
- Comparez les valeurs restantes 19, 5 et 10 avec le nœud racine 12 et placez-les en conséquence. 19> 12 placez-le comme l'enfant droit de 12, 5 <12 & 5 <7, donc placez-le comme enfant gauche de 7.
- Maintenant, comparez 10, 10 est <12 et 10 est> 7 et 10 est> 9, placez 10 comme sous-arbre de droite de 9.
Supprimer des opérations
La suppression est la plus avancée et la plus complexe parmi toutes les autres opérations. Il existe plusieurs cas traités pour suppression dans le BST.
- Cas 1 - Nœud sans enfant: c'est la situation la plus simple, il vous suffit de supprimer le nœud qui n'a plus d'enfants à droite ou à gauche.
- Cas 2 - Nœud avec un enfant: une fois que vous supprimez le nœud, connectez simplement son nœud enfant avec le nœud parent de la valeur supprimée.
- Cas 3 Nœud avec deux enfants: c'est la situation la plus difficile, et cela fonctionne sur les deux règles suivantes
- 3a - Prédécesseur dans l'ordre: vous devez supprimer le nœud avec deux enfants et le remplacer par la plus grande valeur sur le sous-arbre gauche du nœud supprimé
- 3b - Successeur dans l'ordre: vous devez supprimer le nœud avec deux enfants et le remplacer par la plus grande valeur sur le sous-arbre de droite du nœud supprimé
- Il s'agit du premier cas de suppression dans lequel vous supprimez un nœud qui n'a pas d'enfants. Comme vous pouvez le voir sur le diagramme, 19, 10 et 5 n'ont pas d'enfants. Mais nous supprimerons 19.
- Supprimez la valeur 19 et supprimez le lien du nœud.
- Voir la nouvelle structure du BST sans 19
- C'est le deuxième cas de suppression dans lequel vous supprimez un nœud qui a 1 enfant, comme vous pouvez le voir dans le diagramme que 9 a un enfant.
- Supprimez le nœud 9 et remplacez-le par son enfant 10 et ajoutez un lien de 7 à 10
- Voir la nouvelle structure du BST sans 9
- Ici, vous supprimerez le nœud 12 qui a deux enfants
- La suppression du nœud se produira sur la base de la règle du prédécesseur dans l'ordre, ce qui signifie que le plus grand élément du sous-arbre gauche de 12 le remplacera.
- Supprimez le nœud 12 et remplacez-le par 10 car il s'agit de la plus grande valeur du sous-arbre de gauche
- Afficher la nouvelle structure du BST après la suppression de 12
- 1 Supprimez un nœud 12 qui a deux enfants
- 2 La suppression du nœud se produira sur la base de la règle In Order Successor, ce qui signifie que le plus grand élément du sous-arbre droit de 12 le remplacera
- 3 Supprimez le nœud 12 et remplacez-le par 19 car il s'agit de la plus grande valeur du sous-arbre de droite
- 4 Afficher la nouvelle structure du BST après la suppression 12
Termes importants
- Insérer - Insère un élément dans une arborescence / crée une arborescence.
- Rechercher - Recherche un élément dans une arborescence.
- Preorder Traversal - Traverse un arbre en précommande.
- Inorder Traversal - Traverse un arbre dans l'ordre.
- Traversée post-ordre - Traverse un arbre de manière post-commande.
Résumé
- BST est un algorithme de niveau avancé qui effectue diverses opérations basées sur la comparaison des valeurs de nœud avec le nœud racine.
- L'un des points d'une hiérarchie parent-enfant représente le nœud. Au moins un nœud parent ou racine reste présent tout le temps.
- Il existe un sous-arbre gauche et un sous-arbre droit. Le sous-arbre de gauche contient des valeurs inférieures au nœud racine. Cependant, le sous-arbre droit contient une valeur supérieure au nœud racine.
- Chaque nœud peut avoir zéro, un ou deux enfants.
- Un arbre de recherche binaire facilite les opérations principales telles que la recherche, l'insertion et la suppression.
- La suppression étant la plus complexe, a plusieurs cas, par exemple, un nœud sans enfant, un nœud avec un enfant et un nœud avec deux enfants.
- L'algorithme est utilisé dans des solutions du monde réel telles que des jeux, des données de saisie semi-automatique et des graphiques.