Implémentation d'un arbre binaire de recherche

Introduction

Dans ce laboratoire, nous allons apprendre à implémenter un arbre binaire de recherche en Java. Un arbre binaire de recherche est une structure de données d'arbre binaire dans laquelle la valeur de chaque nœud est supérieure ou égale aux valeurs de son sous-arbre gauche et inférieure ou égale aux valeurs de son sous-arbre droit.

Skills Graph

Création de la classe BSTNode

Tout d'abord, créons une classe Java représentant un nœud d'un arbre binaire de recherche et appelons-la BSTNode. Un nœud dans un arbre binaire de recherche devrait avoir une valeur et deux nœuds enfants - l'un à sa gauche et l'un à sa droite.

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

Insertion d'éléments dans l'arbre binaire de recherche

Pour insérer des éléments dans l'arbre binaire de recherche, nous suivons l'algorithme suivant :

• Si la nouvelle valeur est inférieure à la valeur du nœud actuel, alors on effectue une récursion sur l'enfant gauche.
• Si la nouvelle valeur est supérieure à la valeur du nœud actuel, alors on effectue une récursion sur son enfant droit.
• Si le nœud actuel est null, alors on ajoute la nouvelle valeur à cette position.

public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

Pour tester cette méthode, créons l'arbre binaire de recherche et insérons quelques éléments :

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Affiche l'arbre pour vérifier l'insertion
    System.out.println("Parcours après insertion : ");
    inorderTraversal(root);
}

// Fonction pour parcourir l'arbre en ordre
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

Sortie :

Parcours après insertion :
5 7 9 12 20 21

Recherche d'un élément dans l'arbre binaire de recherche

Pour rechercher un élément dans l'arbre binaire de recherche, nous suivons l'algorithme suivant :

• Si la valeur du nœud actuel correspond à la valeur que nous essayons de trouver, alors retourner true.
• Si la valeur du nœud actuel est supérieure à la valeur que nous essayons de trouver, alors effectuer une récursion sur l'enfant gauche.
• Si la valeur du nœud actuel est inférieure à la valeur que nous essayons de trouver, alors effectuer une récursion sur l'enfant droit.
• Si le nœud actuel est null, alors retourner false.

public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

Pour tester cette méthode, recherchons quelques éléments :

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Recherche d'éléments
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

Sortie :

true
true
false

Suppression d'un élément dans un arbre binaire de recherche

La suppression d'un élément dans un arbre binaire de recherche est un peu plus complexe que les étapes précédentes car nous devons traiter différents cas selon le type de nœud :

• Si le nœud n'a aucun enfant (un nœud feuille), supprimez-le simplement.
• Si le nœud a un seul enfant, remplacez-le par son seul enfant.
• Si le nœud a deux enfants, remplacez-le par la valeur minimale du sous-arbre droit ou la valeur maximale du sous-arbre gauche.

public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild!= null && current.rightChild!= null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild!= null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

Pour tester cette méthode, supprimez quelques nœuds et affichez l'arbre :

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Supprimez quelques nœuds
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // Affichez l'arbre pour vérifier la suppression
    System.out.println("Parcours après suppression : ");
    inorderTraversal(root);
}

Sortie :

Parcours après suppression :
5 7 21

Parcours de l'arbre binaire de recherche

Nous pouvons parcourir un arbre binaire de recherche de différentes manières :

• Parcours infixe (Gauche-Racine-Droite)
• Parcours préfixe (Racine-Gauche-Droite)
• Parcours postfixe (Gauche-Droite-Racine)
• Parcours en largeur (BFS)

public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild!= null)
            queue.add(temp.leftChild);
        if (temp.rightChild!= null)
            queue.add(temp.rightChild);
    }
}

Pour tester ces méthodes, affichez l'arbre en utilisant chaque technique de parcours :

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("Parcours infixe : ");
    inorderTraversal(root);
    System.out.print("\nParcours préfixe : ");
    preorderTraversal(root);
    System.out.print("\nParcours postfixe : ");
    postorderTraversal(root);
    System.out.print("\nParcours en largeur : ");
    levelOrderTraversal(root);
}

Sortie :

Parcours infixe : 5 7 9 12 20 21
Parcours préfixe : 12 7 5 9 20 21
Parcours postfixe : 5 9 7 21 20 12
Parcours en largeur : 12 7 20 5 9 21

Récapitulatif

Dans ce laboratoire, nous avons appris à créer, à insérer des éléments dans, à rechercher un élément dans, à supprimer un élément d'un arbre binaire de recherche et à le parcourir en Java.

Nous avons tout d'abord créé la classe BSTNode qui représente un nœud dans l'arbre binaire de recherche. Nous avons ensuite implémenté les fonctionnalités d'insertion, de recherche et de suppression en utilisant des algorithmes spécifiques aux arbres binaires de recherche. Enfin, nous avons appris à parcourir l'arbre binaire de recherche en utilisant différentes techniques de parcours telles que le parcours infixe, préfixe, postfixe et en largeur.

Avec ces concepts, vous devriez être capable d'implementer des arbres binaires de recherche dans vos propres programmes Java.