Introduction

Les arbres binaires de recherche (BST) sont des structures de données arborescentes utilisées pour stocker des éléments de manière hiérarchique. Ils permettent une recherche, une insertion et une suppression efficaces de données, généralement avec une complexité moyenne de .

Notions Fondamentales

1. Définition

Un arbre binaire de recherche est un arbre binaire où chaque nœud a au plus deux enfants et satisfait les propriétés suivantes :

  • Le sous-arbre gauche d'un nœud contient uniquement des nœuds avec des valeurs inférieures à la valeur du nœud.
  • Le sous-arbre droit d'un nœud contient uniquement des nœuds avec des valeurs supérieures à la valeur du nœud.
  • Les sous-arbres gauche et droit sont eux-mêmes des arbres binaires de recherche.

2. Propriétés

  • Recherche, Insertion, Suppression : Opérations de complexité moyenne , mais dans le pire des cas (arbre dégénéré), elles peuvent atteindre .
  • Traversées : Parcours en profondeur (pré-ordre, en-ordre, post-ordre) et parcours en largeur (niveau par niveau).

Exemples Classiques

3. Insertion dans un BST

Exemple de Code en JavaScript :

class Noeud {
    constructor(valeur) {
        this.valeur = valeur;
        this.gauche = null;
        this.droite = null;
    }
}

class ArbreBinaireRecherche {
    constructor() {
        this.racine = null;
    }

    inserer(valeur) {
        const nouveauNoeud = new Noeud(valeur);
        if (this.racine === null) {
            this.racine = nouveauNoeud;
        } else {
            this._insererRec(this.racine, nouveauNoeud);
        }
    }

    _insererRec(noeud, nouveauNoeud) {
        if (nouveauNoeud.valeur < noeud.valeur) {
            if (noeud.gauche === null) {
                noeud.gauche = nouveauNoeud;
            } else {
                this._insererRec(noeud.gauche, nouveauNoeud);
            }
        } else {
            if (noeud.droite === null) {
                noeud.droite = nouveauNoeud;
            } else {
                this._insererRec(noeud.droite, nouveauNoeud);
            }
        }
    }

    // Méthode pour afficher l'arbre en parcours en ordre
    parcoursEnOrdre(noeud = this.racine) {
        if (noeud !== null) {
            this.parcoursEnOrdre(noeud.gauche);
            console.log(noeud.valeur);
            this.parcoursEnOrdre(noeud.droite);
        }
    }
}

// Création de l'arbre binaire de recherche et insertion de valeurs
const arbre = new ArbreBinaireRecherche();
arbre.inserer(5);
arbre.inserer(3);
arbre.inserer(7);
arbre.inserer(2);
arbre.inserer(4);
arbre.inserer(6);
arbre.inserer(8);

// Affichage de l'arbre en parcours en ordre
arbre.parcoursEnOrdre();

4. Recherche dans un BST

Exemple de Code en JavaScript :

class ArbreBinaireRecherche {
    //... autres méthodes

    recherche(valeur) {
        return this._rechercheRec(this.racine, valeur);
    }

    _rechercheRec(noeud, valeur) {
        if (noeud === null || noeud.valeur === valeur) {
            return noeud;
        }
        if (valeur < noeud.valeur) {
            return this._rechercheRec(noeud.gauche, valeur);
        } else {
            return this._rechercheRec(noeud.droite, valeur);
        }
    }
}

// Recherche de la valeur 4 dans l'arbre
const noeudTrouve = arbre.recherche(4);
console.log(noeudTrouve ? noeudTrouve.valeur : "Non trouvé");

5. Suppression dans un BST

Exemple de Code en JavaScript :

class ArbreBinaireRecherche {
    //... autres méthodes

    supprimer(valeur) {
        this.racine = this._supprimerRec(this.racine, valeur);
    }

    _supprimerRec(noeud, valeur) {
        if (noeud === null) {
            return null;
        }
        if (valeur < noeud.valeur) {
            noeud.gauche = this._supprimerRec(noeud.gauche, valeur);
            return noeud;
        } else if (valeur > noeud.valeur) {
            noeud.droite = this._supprimerRec(noeud.droite, valeur);
            return noeud;
        } else {
            // Cas 1: Noeud avec un seul enfant ou pas d'enfant
            if (noeud.gauche === null) {
                return noeud.droite;
            } else if (noeud.droite === null) {
                return noeud.gauche;
            }

            // Cas 2: Noeud avec deux enfants
            noeud.valeur = this._valeurMin(noeud.droite);
            noeud.droite = this._supprimerRec(noeud.droite, noeud.valeur);
            return noeud;
        }
    }

    _valeurMin(noeud) {
        let min = noeud.valeur;
        while (noeud.gauche !== null) {
            min = noeud.gauche.valeur;
            noeud = noeud.gauche;
        }
        return min;
    }
}

// Suppression de la valeur 3 dans l'arbre
arbre.supprimer(3);
arbre.parcoursEnOrdre();

Exemples Amusants Vulgarisés

6. Insertion dans un BST : Le Classement des Jouets

Exemple :

Imagine que tu es un enfant qui adore ranger ses jouets. Tu veux les ranger dans un ordre spécifique. Les jouets plus petits que tes mains vont à gauche de ton étagère, et les jouets plus gros vont à droite. Chaque fois que tu obtiens un nouveau jouet, tu le mets à la bonne place en fonction de sa taille.

 

Exemple de Code en JavaScript :

// Classe représentant un jouet avec un nom, une taille et des références à gauche et droite pour construire un arbre binaire.
class Jouet {
    // Constructeur pour initialiser un objet Jouet avec un nom et une taille.
    constructor(nom, taille) {
        this.nom = nom; // Nom du jouet
        this.taille = taille; // Taille du jouet
        this.gauche = null; // Référence au sous-arbre gauche, initialisée à null
        this.droite = null; // Référence au sous-arbre droit, initialisée à null
    }
}

// Classe représentant une étagère utilisant un arbre binaire pour ranger les jouets par taille.
class Etagere {
    // Constructeur pour initialiser une étagère vide avec une racine null.
    constructor() {
        this.racine = null; // Racine de l'arbre, initialisée à null
    }

    // Méthode pour ranger un nouveau jouet dans l'arbre.
    rangerJouet(nom, taille) {
        const nouveauJouet = new Jouet(nom, taille); // Création d'un nouveau jouet
        if (this.racine === null) {
            // Si l'arbre est vide, le nouveau jouet devient la racine
            this.racine = nouveauJouet;
        } else {
            // Sinon, on appelle la méthode récursive pour le ranger au bon endroit
            this._rangerJouetRec(this.racine, nouveauJouet);
        }
    }

    // Méthode récursive pour ranger un jouet dans l'arbre binaire.
    _rangerJouetRec(noeud, nouveauJouet) {
        if (nouveauJouet.taille < noeud.taille) {
            // Si la taille du nouveau jouet est inférieure à celle du nœud courant
            if (noeud.gauche === null) {
                // Si le sous-arbre gauche est vide, on place le nouveau jouet ici
                noeud.gauche = nouveauJouet;
            } else {
                // Sinon, on continue la recherche dans le sous-arbre gauche
                this._rangerJouetRec(noeud.gauche, nouveauJouet);
            }
        } else {
            // Si la taille du nouveau jouet est supérieure ou égale à celle du nœud courant
            if (noeud.droite === null) {
                // Si le sous-arbre droit est vide, on place le nouveau jouet ici
                noeud.droite = nouveauJouet;
            } else {
                // Sinon, on continue la recherche dans le sous-arbre droit
                this._rangerJouetRec(noeud.droite, nouveauJouet);
            }
        }
    }

    // Méthode pour afficher les jouets en utilisant un parcours en ordre (in-order traversal).
    afficherJouets(noeud = this.racine) {
        if (noeud !== null) {
            // Si le nœud courant n'est pas null
            this.afficherJouets(noeud.gauche); // On affiche d'abord les jouets du sous-arbre gauche
            console.log(noeud.nom); // Puis on affiche le jouet courant
            this.afficherJouets(noeud.droite); // Enfin, on affiche les jouets du sous-arbre droit
        }
    }
}

// Création de l'étagère et rangement des jouets
const etagere = new Etagere();
etagere.rangerJouet("Teddy Bear", 5); // Ajout du jouet "Teddy Bear" avec taille 5
etagere.rangerJouet("Ball", 3); // Ajout du jouet "Ball" avec taille 3
etagere.rangerJouet("Lego", 7); // Ajout du jouet "Lego" avec taille 7
etagere.rangerJouet("Car", 2); // Ajout du jouet "Car" avec taille 2
etagere.rangerJouet("Doll", 4); // Ajout du jouet "Doll" avec taille 4

// Affichage des jouets rangés
etagere.afficherJouets(); // Affiche les jouets en ordre croissant de taille

7. Recherche dans un BST : Trouver un Jouet

Exemple :

Maintenant, tu veux trouver un jouet spécifique sur ton étagère. Tu te rappelles que les jouets plus petits que tes mains sont à gauche et les plus gros sont à droite. Donc, tu sais où chercher!

Exemple de Code en JavaScript :

class Etagere {
    //... autres méthodes

    // Méthode pour trouver un jouet dans l'arbre par sa taille.
    trouverJouet(taille) {
        return this._trouverJouetRec(this.racine, taille); // Appelle la méthode récursive pour trouver le jouet à partir de la racine
    }

    // Méthode récursive pour trouver un jouet dans l'arbre binaire.
    _trouverJouetRec(noeud, taille) {
        if (noeud === null || noeud.taille === taille) {
            return noeud; // Si le nœud est null ou la taille correspond, retourne le nœud courant
        }
        if (taille < noeud.taille) {
            return this._trouverJouetRec(noeud.gauche, taille); // Si la taille à trouver est inférieure, continue la recherche dans le sous-arbre gauche
        } else {
            return this._trouverJouetRec(noeud.droite, taille); // Si la taille à trouver est supérieure, continue la recherche dans le sous-arbre droit
        }
    }
}

// Création de l'étagère et rangement des jouets
const etagere = new Etagere();
etagere.rangerJouet("Teddy Bear", 5);
etagere.rangerJouet("Ball", 3);
etagere.rangerJouet("Lego", 7);
etagere.rangerJouet("Car", 2);
etagere.rangerJouet("Doll", 4);

// Recherche du jouet avec la taille 4
const jouetTrouve = etagere.trouverJouet(4); // Appelle la méthode pour trouver le jouet avec la taille 4
console.log(jouetTrouve ? jouetTrouve.nom : "Non trouvé"); // Affiche le nom du jouet trouvé ou "Non trouvé" si aucun jouet n'a cette taille

Ce code ajoute la fonctionnalité de trouver un jouet dans l'arbre binaire de recherche en fonction de sa taille. La méthode trouverJouet utilise une méthode récursive _trouverJouetRec pour parcourir l'arbre et trouver le nœud avec la taille spécifiée. Si le nœud avec la taille donnée est trouvé, il est retourné, sinon la recherche continue dans le sous-arbre gauche ou droit selon la taille comparée à celle du nœud courant.

8. Suppression dans un BST : Se Débarrasser d'un Jouet

Exemple :

Tu décides de te débarrasser d'un jouet que tu n'aimes plus. Tu dois donc le retirer de ton étagère tout en maintenant l'ordre des autres jouets.

Exemple de Code en JavaScript :

class Etagere {
    //... autres méthodes

    // Méthode pour retirer un jouet de l'arbre par sa taille.
    retirerJouet(taille) {
        this.racine = this._retirerJouetRec(this.racine, taille); // Appelle la méthode récursive pour retirer le jouet à partir de la racine
    }

    // Méthode récursive pour retirer un jouet de l'arbre binaire.
    _retirerJouetRec(noeud, taille) {
        if (noeud === null) {
            return null; // Si le nœud est null, il n'y a rien à retirer, retourne null
        }
        if (taille < noeud.taille) {
            // Si la taille à retirer est inférieure à la taille du nœud courant
            noeud.gauche = this._retirerJouetRec(noeud.gauche, taille); // Continue la recherche dans le sous-arbre gauche
            return noeud; // Retourne le nœud courant
        } else if (taille > noeud.taille) {
            // Si la taille à retirer est supérieure à la taille du nœud courant
            noeud.droite = this._retirerJouetRec(noeud.droite, taille); // Continue la recherche dans le sous-arbre droit
            return noeud; // Retourne le nœud courant
        } else {
            // Si la taille correspond à celle du nœud courant, on doit retirer ce nœud
            // Cas 1: Noeud avec un seul enfant ou pas d'enfant
            if (noeud.gauche === null) {
                return noeud.droite; // Si le sous-arbre gauche est null, retourne le sous-arbre droit
            } else if (noeud.droite === null) {
                return noeud.gauche; // Si le sous-arbre droit est null, retourne le sous-arbre gauche
            }

            // Cas 2: Noeud avec deux enfants
            // Trouve le plus petit nœud du sous-arbre droit
            const minDroit = this._valeurMin(noeud.droite);
            noeud.taille = minDroit.taille; // Remplace la taille du nœud courant par la taille du plus petit nœud trouvé
            noeud.nom = minDroit.nom; // Remplace le nom du nœud courant par le nom du plus petit nœud trouvé
            noeud.droite = this._retirerJouetRec(noeud.droite, minDroit.taille); // Retire le plus petit nœud du sous-arbre droit
            return noeud; // Retourne le nœud courant
        }
    }

    // Méthode pour trouver le nœud avec la plus petite valeur dans un sous-arbre.
    _valeurMin(noeud) {
        let min = noeud; // Initialise la variable min avec le nœud courant
        while (noeud.gauche !== null) {
            // Parcourt le sous-arbre gauche jusqu'à trouver le nœud le plus à gauche
            min = noeud.gauche; // Met à jour la variable min avec le nœud courant
            noeud = noeud.gauche; // Passe au nœud suivant à gauche
        }
        return min; // Retourne le nœud avec la plus petite valeur
    }
}

// Suppression du jouet avec la taille 3
etagere.retirerJouet(3); // Appelle la méthode pour retirer le jouet avec la taille 3
etagere.afficherJouets(); // Affiche les jouets restants après la suppression

Ce code ajoute la fonctionnalité de retirer un jouet de l'arbre binaire de recherche en fonction de sa taille. La méthode retirerJouet utilise une méthode récursive _retirerJouetRec pour parcourir l'arbre et trouver le nœud à supprimer. Une fois trouvé, le nœud est retiré en gérant les différents cas possibles (nœud avec zéro, un ou deux enfants). La méthode _valeurMin est utilisée pour trouver le nœud avec la plus petite valeur dans le sous-arbre droit, nécessaire pour remplacer le nœud à supprimer lorsqu'il a deux enfants.

Ce cours vous permet de comprendre les bases des arbres binaires de recherche à travers des exemples classiques et des histoires amusantes pour rendre l'apprentissage plus engageant.

Modifié le: mardi 18 février 2025, 06:00