Arbre de recherche binaire (BST) avec exemple

Qu’est-ce qu’un arbre de recherche binaire ?

L'arbre binaire de recherche (ABR) est un algorithme avancé permettant d'analyser un nœud, ses branches gauche et droite (représentées sous forme d'arbre) et d'en renvoyer la valeur. L'ABR est conçu sur le modèle d'un algorithme de recherche binaire classique ; il permet ainsi des recherches, des insertions et des suppressions de nœuds plus rapides. Le programme s'en trouve ainsi particulièrement performant et précis.

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 selon 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 gauche sont plus courtes que les clés de leur nœud parent.
• De même, les clés des nœuds présents sur le sous-arbre droit sont supérieures aux clés 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 droite avec leurs propres valeurs clés.
2. Le sous-arbre droit possède des valeurs clés supérieures à celles du nœud parent.
3. Le sous-arbre gauche possède des valeurs clés inférieures à celles du nœud parent.

Pourquoi avons-nous besoin d’un arbre de recherche binaire ?

• Les deux principaux facteurs qui font d'un arbre de recherche binaire une solution optimale à tout problème 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 recherché est supérieur ou inférieur au nœud parent, le nœud sait de quel côté de l'arbre effectuer la recherche. En effet, le sous-arbre gauche contient toujours des valeurs inférieures à celles du nœud parent, tandis que le sous-arbre droit contient toujours des valeurs supérieures ou égales à 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 de l'arbre sont saturés, à l'exception possible du dernier niveau. De même, tous les nœuds sont saturés, pointant vers 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, chaque nœud possède deux enfants. De plus, chaque sous-nœud est au même niveau.

En savoir plus sur le 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.

Selon 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 :

• Chercher: recherche l'élément dans l'arbre binaire.
• Insérer: ajoute un élément à l'arbre binaire.
• Effacer: 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

Il faut toujours commencer l'analyse de l'arbre par le nœud racine, puis se déplacer vers le sous-arbre droit ou gauche de ce nœud, selon que l'élément à localiser 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 passez donc au sous-arbre gauche. Il est inutile d'analyser le sous-arbre droit.
3. Maintenant, comparez 10 avec le nœud 7, 10 > 7, donc déplacez-vous vers le sous-arbre droit.
4. Comparez ensuite 10 avec le nœud suivant, qui est 9, 10 > 9, regardez dans l'enfant du sous-arbre droit.
5. 10 correspond à la valeur dans le nœud, 10 = 10, renvoie la valeur à l'utilisateur.

Faux 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. On insère d'abord le nœud racine, puis on compare la valeur suivante à celle du nœud racine. Si la valeur est supérieure à celle de la racine, elle est ajoutée au sous-arbre droit ; si elle est inférieure, elle est ajoutée au sous-arbre gauche.

1. Il existe une liste de 6 éléments qui doivent être insérés dans un arbre binaire de recherche, 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 le sous-arbre 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 < 12, 10 > 7 et 10 > 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

Lorsqu'on supprime un nœud d'un arbre binaire de recherche (BST), il existe plusieurs cas : la suppression de la racine ou celle d'une feuille. Après la suppression de la racine, il convient également de prendre en compte le nœud racine lui-même.

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 sans enfant : C'est le cas le plus simple : il suffit de supprimer le nœud qui n'a plus d'enfants à droite ni à gauche.
• Cas 2 – Nœud avec un enfant : Une fois le nœud supprimé, il suffit de connecter son nœud enfant au nœud parent de la valeur supprimée.
• Cas 3 – Nœud avec deux enfants : Il s'agit de la situation la plus difficile, et elle repose sur les deux règles suivantes :
  • 3a – Antécédent dans l'ordre : Vous devez supprimer le nœud ayant deux enfants et le remplacer par la plus grande valeur du sous-arbre gauche du nœud supprimé.
  • 3b – Successeur en ordre : Vous devez supprimer le nœud ayant deux enfants et le remplacer par la plus petite valeur du sous-arbre droit du nœud supprimé.

1. Il s'agit du premier cas de suppression, où l'on supprime un nœud sans enfant. Comme vous pouvez le voir sur le schéma, les nœuds 19, 10 et 5 n'ont pas d'enfant. Nous allons donc supprimer le nœud 19.
2. Supprimez la valeur 19 et supprimez le lien du nœud.
3. Visualisez la nouvelle structure du BST sans 19.

1. Il s'agit du deuxième cas de suppression, où vous supprimez un nœud qui possède un seul enfant. Comme vous pouvez le voir sur le diagramme, le nœud 9 possède un seul enfant.
2. Supprimez le nœud 9 et remplacez-le par son enfant 10, et ajoutez un lien de 7 à 10.
3. Visualisez la nouvelle structure du BST sans 9.

1. Vous allez ici supprimer le nœud 12 qui possède deux enfants.
2. La suppression du nœud s'effectuera selon la règle du prédécesseur en 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 il s'agit de la plus grande valeur du sous-arbre gauche.
4. Visualisez la nouvelle structure du BST après la suppression de 12.

1. Supprimez le nœud 12 qui possède deux enfants.
2. La suppression du nœud s'effectuera selon la règle du successeur en ordre, ce qui signifie que le plus petit é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 petite valeur sur le sous-arbre droit.
4. Visualisez la nouvelle structure du BST après la suppression de 12.

Faux 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, delete the successor
        free(newNode)
    else
        free(y)

Conditions importantes

• Insérer: Insère un élément dans un arbre / crée un arbre.
• Chercher: Recherche un élément dans un arbre.
• Parcours pré-ordre : Parcourt un arbre en suivant un ordre préfixe.
• Parcours infixe : Parcourt un arbre de manière séquentielle.
• Parcours post-ordre : Parcourt un arbre en suivant l'ordre indiqué.

FAQ