Arbres AVL

Notions Fondamentales

Les arbres AVL (nommés d'après leurs inventeurs Adelson-Velsky et Landis) sont des arbres binaires de recherche auto-équilibrés. Pour chaque nœud de l'arbre, la hauteur des deux sous-arbres ne diffère jamais de plus de 1. Cet équilibre garantit que l'arbre reste équilibré, maintenant une complexité pour les opérations de base.

1. Insertion dans un Arbre AVL

Exemple de Code en JavaScript :

class NoeudAVL {
    constructor(valeur) {
        this.valeur = valeur;
        this.gauche = null;
        this.droite = null;
        this.hauteur = 1;
    }
}

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

    hauteur(noeud) {
        return noeud ? noeud.hauteur : 0;
    }

    inserer(valeur) {
        this.racine = this._insererRec(this.racine, valeur);
    }

    _insererRec(noeud, valeur) {
        if (!noeud) return new NoeudAVL(valeur);

        if (valeur < noeud.valeur) {
            noeud.gauche = this._insererRec(noeud.gauche, valeur);
        } else if (valeur > noeud.valeur) {
            noeud.droite = this._insererRec(noeud.droite, valeur);
        } else {
            return noeud; // Pas de valeur dupliquée
        }

        noeud.hauteur = 1 + Math.max(this.hauteur(noeud.gauche), this.hauteur(noeud.droite));
        const équilibre = this.getEquilibre(noeud);

        // Rotation gauche-gauche
        if (équilibre > 1 && valeur < noeud.gauche.valeur) {
            return this.rotationDroite(noeud);
        }

        // Rotation droite-droite
        if (équilibre < -1 && valeur > noeud.droite.valeur) {
            return this.rotationGauche(noeud);
        }

        // Rotation gauche-droite
        if (équilibre > 1 && valeur > noeud.gauche.valeur) {
            noeud.gauche = this.rotationGauche(noeud.gauche);
            return this.rotationDroite(noeud);
        }

        // Rotation droite-gauche
        if (équilibre < -1 && valeur < noeud.droite.valeur) {
            noeud.droite = this.rotationDroite(noeud.droite);
            return this.rotationGauche(noeud);
        }

        return noeud;
    }

    rotationGauche(z) {
        const y = z.droite;
        const T2 = y.gauche;
        y.gauche = z;
        z.droite = T2;
        z.hauteur = Math.max(this.hauteur(z.gauche), this.hauteur(z.droite)) + 1;
        y.hauteur = Math.max(this.hauteur(y.gauche), this.hauteur(y.droite)) + 1;
        return y;
    }

    rotationDroite(y) {
        const x = y.gauche;
        const T2 = x.droite;
        x.droite = y;
        y.gauche = T2;
        y.hauteur = Math.max(this.hauteur(y.gauche), this.hauteur(y.droite)) + 1;
        x.hauteur = Math.max(this.hauteur(x.gauche), this.hauteur(x.droite)) + 1;
        return x;
    }

    getEquilibre(noeud) {
        return noeud ? this.hauteur(noeud.gauche) - this.hauteur(noeud.droite) : 0;
    }

    // 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 AVL et insertion de valeurs
const arbreAVL = new ArbreAVL();
arbreAVL.inserer(10);
arbreAVL.inserer(20);
arbreAVL.inserer(30);
arbreAVL.inserer(40);
arbreAVL.inserer(50);
arbreAVL.inserer(25);

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

Exemples Amusants Vulgarisés

Histoire Amusante : L'Equilibriste et ses Plats

Imagine que tu es un équilibriste qui jongle avec des assiettes. Tu dois garder ton équilibre en veillant à ce que le nombre d'assiettes de chaque côté de toi soit presque égal. Si tu ajoutes une assiette de trop d'un côté, tu dois déplacer quelques assiettes pour retrouver ton équilibre.

Arbres Rouges-Noirs

Notions Fondamentales

Les arbres rouges-noirs sont également des arbres binaires de recherche auto-équilibrés. Chaque nœud de l'arbre est soit rouge, soit noir, avec des propriétés spécifiques pour maintenir l'équilibre. Ces propriétés garantissent que la profondeur de l'arbre reste logarithmique par rapport au nombre de nœuds, assurant des opérations efficaces.

1. Propriétés des Arbres Rouges-Noirs

  1. Chaque nœud est soit rouge, soit noir.
  2. La racine est toujours noire.
  3. Toutes les feuilles (nulles) sont noires.
  4. Si un nœud est rouge, alors ses enfants sont noirs.
  5. Chaque chemin de la racine à une feuille contient le même nombre de nœuds noirs.

2. Insertion dans un Arbre Rouge-Noir

Exemple de Code en JavaScript :

class NoeudRougeNoir {
    constructor(valeur, couleur = 'rouge') {
        this.valeur = valeur;
        this.couleur = couleur;
        this.gauche = null;
        this.droite = null;
        this.parent = null;
    }
}

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

    rotationGauche(x) {
        const y = x.droite;
        x.droite = y.gauche;
        if (y.gauche !== null) y.gauche.parent = x;
        y.parent = x.parent;
        if (x.parent === null) this.racine = y;
        else if (x === x.parent.gauche) x.parent.gauche = y;
        else x.parent.droite = y;
        y.gauche = x;
        x.parent = y;
    }

    rotationDroite(x) {
        const y = x.gauche;
        x.gauche = y.droite;
        if (y.droite !== null) y.droite.parent = x;
        y.parent = x.parent;
        if (x.parent === null) this.racine = y;
        else if (x === x.parent.droite) x.parent.droite = y;
        else x.parent.gauche = y;
        y.droite = x;
        x.parent = y;
    }

    inserer(valeur) {
        const nouveauNoeud = new NoeudRougeNoir(valeur);
        if (this.racine === null) {
            this.racine = nouveauNoeud;
            this.racine.couleur = 'noir';
        } else {
            this._insererRec(this.racine, nouveauNoeud);
            this._fixInsertion(nouveauNoeud);
        }
    }

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

    _fixInsertion(noeud) {
        while (noeud !== this.racine && noeud.parent.couleur === 'rouge') {
            if (noeud.parent === noeud.parent.parent.gauche) {
                let oncle = noeud.parent.parent.droite;
                if (oncle && oncle.couleur === 'rouge') {
                    noeud.parent.couleur = 'noir';
                    oncle.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    noeud = noeud.parent.parent;
                } else {
                    if (noeud === noeud.parent.droite) {
                        noeud = noeud.parent;
                        this.rotationGauche(noeud);
                    }
                    noeud.parent.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    this.rotationDroite(noeud.parent.parent);
                }
            } else {
                let oncle = noeud.parent.parent.gauche;
                if (oncle && oncle.couleur === 'rouge') {
                    noeud.parent.couleur = 'noir';
                    oncle.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    noeud = noeud.parent.parent;
                } else {
                    if (noeud === noeud.parent.gauche) {
                        noeud = noeud.parent;
                        this.rotationDroite(noeud);
                    }
                    noeud.parent.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    this.rotationGauche(noeud.parent.parent);
                }
            }
        }
        this.racine.couleur = 'noir';
    }

    // 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} (${noeud.couleur})`);
            this.parcoursEnOrdre(noeud.droite);
        }
    }
}

// Création de l'arbre rouge-noir et insertion de valeurs
const arbreRougeNoir = new ArbreRougeNoir();
arbreRougeNoir.inserer(10);
arbreRougeNoir.inserer(20);
arbreRougeNoir.inserer(30);
arbreRougeNoir.inserer(15);
arbreRougeNoir.inserer(25);
arbreRougeNoir.inserer(5);
arbreRougeNoir.inserer(1);

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

Exemples Amusants Vulgarisés

Arbres AVL

Histoire Amusante : L'Acrobate et ses Jouets

Imagine que tu es un acrobate qui doit garder son équilibre en jonglant avec des jouets. Si tu mets trop de jouets d'un côté, tu dois les rééquilibrer en déplaçant quelques jouets de l'autre côté.

Exemple de Code en JavaScript :

class JouetAVL {
    constructor(nom, taille) {
        this.nom = nom;
        this.taille = taille;
        this.gauche = null;
        this.droite = null;
        this.hauteur = 1;
    }
}

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

    hauteur(noeud) {
        return noeud ? noeud.hauteur : 0;
    }

    rangerJouet(nom, taille) {
        const nouveauJouet = new JouetAVL(nom, taille);
        if (this.racine === null) {
            this.racine = nouveauJouet;
        } else {
            this.racine = this._rangerJouetRec(this.racine, nouveauJouet);
        }
    }

    _rangerJouetRec(noeud, nouveauJouet) {
        if (!noeud) return nouveauJouet;

        if (nouveauJouet.taille < noeud.taille) {
            noeud.gauche = this._rangerJouetRec(noeud.gauche, nouveauJouet);
        } else if (nouveauJouet.taille > noeud.taille) {
            noeud.droite = this._rangerJouetRec(noeud.droite, nouveauJouet);
        } else {
            return noeud;
        }

        noeud.hauteur = 1 + Math.max(this.hauteur(noeud.gauche), this.hauteur(noeud.droite));
        const équilibre = this.getEquilibre(noeud);

        if (équilibre > 1 && nouveauJouet.taille < noeud.gauche.taille) {
            return this.rotationDroite(noeud);
        }
        if (équilibre < -1 && nouveauJouet.taille > noeud.droite.taille) {
            return this.rotationGauche(noeud);
        }
        if (équilibre > 1 && nouveauJouet.taille > noeud.gauche.taille) {
            noeud.gauche = this.rotationGauche(noeud.gauche);
            return this.rotationDroite(noeud);
        }
        if (équilibre < -1 && nouveauJouet.taille < noeud.droite.taille) {
            noeud.droite = this.rotationDroite(noeud.droite);
            return this.rotationGauche(noeud);
        }

        return noeud;
    }

    rotationGauche(z) {
        const y = z.droite;
        const T2 = y.gauche;
        y.gauche = z;
        z.droite = T2;
        z.hauteur = Math.max(this.hauteur(z.gauche), this.hauteur(z.droite)) + 1;
        y.hauteur = Math.max(this.hauteur(y.gauche), this.hauteur(y.droite)) + 1;
        return y;
    }

    rotationDroite(y) {
        const x = y.gauche;
        const T2 = x.droite;
        x.droite = y;
        y.gauche = T2;
        y.hauteur = Math.max(this.hauteur(y.gauche), this.hauteur(y.droite)) + 1;
        x.hauteur = Math.max(this.hauteur(x.gauche), this.hauteur(x.droite)) + 1;
        return x;
    }

    getEquilibre(noeud) {
        return noeud ? this.hauteur(noeud.gauche) - this.hauteur(noeud.droite) : 0;
    }

    afficherJouets(noeud = this.racine) {
        if (noeud !== null) {
            this.afficherJouets(noeud.gauche);
            console.log(noeud.nom);
            this.afficherJouets(noeud.droite);
        }
    }
}

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

// Affichage des jouets rangés
etagereAVL.afficherJouets();

Arbres Rouges-Noirs

Histoire Amusante : Le Gardien de la Forêt

Imagine que tu es un gardien de la forêt magique où chaque arbre a des fruits rouges ou noirs. Les règles de la forêt sont strictes : chaque arbre rouge doit avoir des enfants noirs, et le chemin de la racine aux feuilles doit avoir le même nombre d'arbres noirs. Ton travail est de planter des arbres tout en respectant ces règles.

Exemple de Code en JavaScript :

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

    _fixInsertion(noeud) {
        while (noeud !== this.racine && noeud.parent.couleur === 'rouge') {
            if (noeud.parent === noeud.parent.parent.gauche) {
                let oncle = noeud.parent.parent.droite;
                if (oncle && oncle.couleur === 'rouge') {
                    noeud.parent.couleur = 'noir';
                    oncle.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    noeud = noeud.parent.parent;
                } else {
                    if (noeud === noeud.parent.droite) {
                        noeud = noeud.parent;
                        this.rotationGauche(noeud);
                    }
                    noeud.parent.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    this.rotationDroite(noeud.parent.parent);
                }
            } else {
                let oncle = noeud.parent.parent.gauche;
                if (oncle && oncle.couleur === 'rouge') {
                    noeud.parent.couleur = 'noir';
                    oncle.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    noeud = noeud.parent.parent;
                } else {
                    if (noeud === noeud.parent.gauche) {
                        noeud = noeud.parent;
                        this.rotationDroite(noeud);
                    }
                    noeud.parent.couleur = 'noir';
                    noeud.parent.parent.couleur = 'rouge';
                    this.rotationGauche(noeud.parent.parent);
                }
            }
        }
        this.racine.couleur = 'noir';
    }

    afficherArbres(noeud = this.racine) {
        if (noeud !== null) {
            this.afficherArbres(noeud.gauche);
            console.log(`${noeud.valeur} (${noeud.couleur})`);
            this.afficherArbres(noeud.droite);
        }
    }
}

// Création de la forêt et plantation des arbres
const foret = new ArbreRougeNoir();
foret.inserer(10);
foret.inserer(20);
foret.inserer(30);
foret.inserer(15);
foret.inserer(25);
foret.inserer(5);
foret.inserer(1);

// Affichage des arbres dans la forêt
foret.afficherArbres();

Ce cours permet de comprendre les arbres AVL et les arbres rouges-noirs à travers des exemples classiques et des histoires amusantes pour rendre l'apprentissage plus engageant. Les arbres auto-équilibrés garantissent des opérations efficaces même lorsque le nombre d'éléments dans l'arbre augmente.

Modifié le: mardi 18 février 2025, 03:49