Arbre de recherche binaire (BST) avec exemple

Attributs de l'arbre de recherche binaire

Un BST est composé de plusieurs nœuds et se compose des attributs suivants :

• Les nœuds de l'arbre 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 appelé arbre de recherche binaire, possède des sous-branches à droite et à gauche.
• 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 du sous-arbre gauche ont des valeurs inférieures à celles de leur nœud parent.

1. Il y a le nœud principal ou niveau parent 11. En dessous, il y a des nœuds/branches gauche et droit avec leurs propres valeurs clés
2. Le sous-arbre de droite a des valeurs de clé supérieures à celles du nœud parent
3. Le sous-arbre de gauche a des valeurs supérieures à celles du 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 se fait sous la forme d'une branche avec des relations parent-enfant, l'algorithme sait à quel endroit de l'arborescence les éléments doivent être recherchés. Cela réduit le nombre de comparaisons clé-valeur que le programme doit effectuer pour localiser l'élément souhaité.
• De plus, si 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 de gauche est toujours inférieur au nœud parent et que le sous-arbre de droite a toujours des valeurs égales ou supérieures à celles du 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

Il existe trois types d'arbres binaires :

• Arbre binaire complet : Tous les niveaux des arbres sont remplis 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 sauf la feuille.
• Arbre binaire équilibré ou parfait : Dans l'arbre, tous les nœuds ont deux enfants. De plus, il y a le même niveau pour chaque sous-nœud.

En savoir plus sur Arbre binaire dans la structure des données Si tu es intéressé.

Comment fonctionne l’arbre de recherche binaire ?

L'arborescence 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.

En fonction 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 :

• Rechercher : recherche l'élément dans l'arbre binaire
• Insérer : ajoute un élément à l'arbre binaire
• Supprimer : supprime l'élément d'un arbre binaire

Chaque opération a sa propre structure et méthode d’exécution/analyse, mais la plus complexe de toutes est l’opération Supprimer.

Rechercher Operaproduction

Commencez toujours l'analyse de l'arbre au niveau du nœud racine, puis déplacez-vous plus loin vers le sous-arbre droit ou gauche du nœud racine en fonction de l'élément à localiser qui est inférieur ou supérieur à la racine.

1. L'élément à rechercher est 10
2. Comparez l'élément avec le nœud racine 12, 10 <12, vous vous déplacez donc vers le sous-arbre de gauche. Pas besoin d'analyser le sous-arbre droit
3. Comparez maintenant 10 avec le nœud 7, 10 > 7, alors déplacez-vous vers le sous-arbre de droite
4. Comparez ensuite 10 avec le nœud suivant, qui est 9, 10 > 9, regardez dans le sous-arbre enfant de droite
5. 10 correspond à la valeur dans le nœud, 10 = 10, renvoie la valeur à l'utilisateur.

Pseudo-code pour la recherche dans BST

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

insérer Operaproduction

Il s’agit d’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.

1. Il existe une liste de 6 éléments qui doivent être insérés dans un BST dans l'ordre de gauche à droite
2. Insérez 12 comme nœud racine et comparez les valeurs suivantes 7 et 9 pour les insérer en conséquence dans les sous-arbres droit et gauche.
3. 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 enfant droit de 12, 5 < 12 et 5 < 7, placez-le donc comme enfant gauche de 7. Comparez maintenant 10, 10 est < 12 et 10 est > 7 et 10 est > 9, placez 10. comme sous-arbre droit de 9.

Pseudocode pour l'insertion d'un nœud dans BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Supprimer Operations

Pour supprimer un nœud d'un BST, il existe certains cas, par exemple la suppression d'une racine ou la suppression d'un nœud feuille. De plus, après avoir supprimé une racine, nous devons penser au nœud racine.

Supposons que nous voulions supprimer un nœud feuille, nous pouvons simplement le supprimer, mais si nous voulons supprimer une racine, nous devons remplacer la valeur de la racine par un autre nœud. Prenons l'exemple suivant :

• Cas 1- Nœud avec zéro enfant : c'est la situation la plus simple, il suffit de supprimer le nœud qui n'a plus d'enfant à droite ou à gauche.
• Cas 2 – Nœud avec un enfant : une fois le nœud supprimé, connectez simplement son nœud enfant au nœud parent de la valeur supprimée.
• Cas 3 Nœud avec deux enfants : c'est la situation la plus difficile, et elle fonctionne selon les deux règles suivantes
• 3a – Dans l'ordre prédécesseur : vous devez supprimer le nœud avec deux enfants et le remplacer par la plus grande valeur du sous-arbre gauche du nœud supprimé
• 3b – Dans l'ordre successeur : vous devez supprimer le nœud avec deux enfants et le remplacer par la plus grande valeur dans le sous-arbre droit du nœud supprimé.

1. Il s'agit du premier cas de suppression dans lequel vous supprimez un nœud qui n'a pas d'enfant. Comme vous pouvez le voir sur le diagramme, 19, 10 et 5 n’ont pas d’enfants. Mais nous supprimerons le 19.
2. Supprimez la valeur 19 et supprimez le lien du nœud.
3. Voir la nouvelle structure du BST sans 19

1. Il s'agit du deuxième cas de suppression dans lequel vous supprimez un nœud qui a 1 enfant, comme vous pouvez le voir sur le diagramme que 9 a un enfant.
2. Supprimez le nœud 9 et remplacez-le par son enfant 10 et ajoutez un lien de 7 à 10
3. Voir la nouvelle structure du BST sans 9

1. Ici, vous supprimerez le nœud 12 qui a deux enfants
2. 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.
3. Supprimez le nœud 12 et remplacez-le par 10 car c'est la plus grande valeur du sous-arbre de gauche
4. Visualiser la nouvelle structure du BST après suppression 12

1. 1 Supprimer un nœud 12 qui a deux enfants
2. 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. 3 Supprimez le nœud 12 et remplacez-le par 19 car c'est la plus grande valeur du sous-arbre de droite
4. 4 Visualisez la nouvelle structure du BST après suppression 12

Pseudo-code pour supprimer un nœud

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Conditions importantes

• Insérer : Insère un élément dans un arbre/crée un arbre.
• Rechercher : recherche un élément dans une arborescence.
• Traversée de précommande : parcourt un arbre de manière précommandée.
• Traversée dans l'ordre : parcourt un arbre dans l'ordre.
• Traversée post-commande : 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 des nœuds avec le nœud racine.
• N'importe quel point d'une hiérarchie parent-enfant représente le nœud. Au moins un nœud parent ou racine reste présent à tout moment.
• Il y a un sous-arbre gauche et un sous-arbre droit. Le sous-arbre de gauche contient des valeurs inférieures à celles du nœud racine. Cependant, le sous-arbre de droite contient une valeur supérieure à celle du nœud racine.
• Chaque nœud peut avoir zéro, un ou deux enfants.
• Un arbre de recherche binaire facilite les opérations primaires telles que la recherche, l'insertion et la suppression.
• La suppression étant la plus complexe, elle comporte 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 les jeux, les données de saisie semi-automatique et les graphiques.