les Skip Lists

Niveau 3: [ ] -> [ ] -> [ ]
Niveau 2: [ ] -> [ ] -> [ ] -> [ ]
Niveau 1: [ ] -> [ ] -> [ ] -> [ ] -> [ ]
Niveau 0: [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

// Classe représentant un nœud de la skip list
class Node {
    constructor(value, level) {
        this.value = value; // Valeur du nœud
        this.forward = new Array(level + 1).fill(null); // Tableau de pointeurs vers les nœuds suivants pour chaque niveau
    }
}

// Classe représentant la skip list
class SkipList {
    constructor(maxLevel, p) {
        this.maxLevel = maxLevel; // Niveau maximum de la skip list
        this.p = p; // Probabilité utilisée pour déterminer les niveaux aléatoires
        this.header = new Node(null, maxLevel); // Nœud tête avec un niveau maximum
        this.level = 0; // Niveau actuel de la skip list
    }

    // Génère un niveau aléatoire pour le nouvel élément
    randomLevel() {
        let level = 0;
        while (Math.random() < this.p && level < this.maxLevel) {
            level++; // Incrémente le niveau tant que la condition est remplie
        }
        return level; // Retourne le niveau généré
    }

    // Recherche un élément dans la skip list
    search(value) {
        let current = this.header; // Commence à partir du nœud tête
        for (let i = this.level; i >= 0; i--) {
            // Descend à travers les niveaux
            while (current.forward[i] !== null && current.forward[i].value < value) {
                current = current.forward[i]; // Avance au nœud suivant au niveau actuel
            }
        }
        current = current.forward[0]; // Descend au niveau 0
        return current !== null && current.value === value ? current : null; // Retourne le nœud si trouvé
    }

    // Insertion d'un nouvel élément dans la skip list
    insert(value) {
        let update = new Array(this.maxLevel + 1).fill(null); // Tableau pour suivre les nœuds à mettre à jour
        let current = this.header; // Commence à partir du nœud tête
        for (let i = this.level; i >= 0; i--) {
            // Descend à travers les niveaux
            while (current.forward[i] !== null && current.forward[i].value < value) {
                current = current.forward[i]; // Avance au nœud suivant au niveau actuel
            }
            update[i] = current; // Enregistre le nœud à mettre à jour
        }

        current = current.forward[0]; // Descend au niveau 0
        if (current === null || current.value !== value) {
            // Si l'élément n'existe pas déjà
            let newLevel = this.randomLevel(); // Génère un niveau aléatoire pour le nouvel élément
            if (newLevel > this.level) {
                // Met à jour les nœuds tête si le nouveau niveau est plus grand
                for (let i = this.level + 1; i <= newLevel; i++) {
                    update[i] = this.header;
                }
                this.level = newLevel; // Met à jour le niveau actuel de la skip list
            }

            let newNode = new Node(value, newLevel); // Crée un nouveau nœud
            for (let i = 0; i <= newLevel; i++) {
                newNode.forward[i] = update[i].forward[i]; // Pointe le nouveau nœud vers les nœuds suivants
                update[i].forward[i] = newNode; // Met à jour les nœuds précédents pour pointer vers le nouveau nœud
            }
        }
    }

    // Suppression d'un élément de la skip list
    delete(value) {
        let update = new Array(this.maxLevel + 1).fill(null); // Tableau pour suivre les nœuds à mettre à jour
        let current = this.header; // Commence à partir du nœud tête
        for (let i = this.level; i >= 0; i--) {
            // Descend à travers les niveaux
            while (current.forward[i] !== null && current.forward[i].value < value) {
                current = current.forward[i]; // Avance au nœud suivant au niveau actuel
            }
            update[i] = current; // Enregistre le nœud à mettre à jour
        }

        current = current.forward[0]; // Descend au niveau 0
        if (current !== null && current.value === value) {
            // Si l'élément est trouvé
            for (let i = 0; i <= this.level; i++) {
                if (update[i].forward[i] !== current) break; // Arrête si le lien est rompu
                update[i].forward[i] = current.forward[i]; // Met à jour les nœuds pour sauter le nœud supprimé
            }
            while (this.level > 0 && this.header.forward[this.level] === null) {
                this.level--; // Ajuste le niveau actuel si nécessaire
            }
        }
    }
}

// Création d'une skip list avec un niveau maximum de 3 et une probabilité de 0.5
const skipList = new SkipList(3, 0.5);

// Insertion d'éléments
skipList.insert(1);
skipList.insert(3);
skipList.insert(7);
skipList.insert(8);
skipList.insert(9);
skipList.insert(12);
skipList.insert(19);

// Recherche d'éléments
console.log(skipList.search(3) !== null); // Output: true
console.log(skipList.search(10) !== null); // Output: false

// Suppression d'un élément
skipList.delete(3);
console.log(skipList.search(3) !== null); // Output: false

Explication du Code

1. Classe Node :

   • Représente un nœud dans la skip list.
   • Contient une valeur et un tableau de pointeurs (forward) vers les nœuds suivants à différents niveaux.

2. Classe SkipList :

   • Initialise la skip list avec un niveau maximum (maxLevel) et une probabilité (p).
   • Contient un nœud tête (header) et le niveau actuel de la liste (level).

3. Méthode randomLevel :

   • Génère un niveau aléatoire pour un nouvel élément basé sur la probabilité p.

4. Méthode search :

   • Recherche un élément dans la skip list en traversant les niveaux de haut en bas.

5. Méthode insert :

   • Insère un nouvel élément dans la skip list en mettant à jour les pointeurs (forward) des nœuds affectés.

6. Méthode delete :

   • Supprime un élément de la skip list en ajustant les pointeurs (forward) des nœuds affectés.

7. Exemple d'utilisation :

   • Création d'une skip list avec un niveau maximum de 3 et une probabilité de 0.5.
   • Insertion, recherche et suppression d'éléments dans la skip list.

Ce code montre comment les skip lists permettent des opérations efficaces de recherche, d'insertion et de suppression avec une complexité moyenne de $O(\log n)$. Les commentaires ligne par ligne facilitent la compréhension du fonctionnement interne de la skip list.