Voici une implémentation du concept de l'ascenseur magique utilisant une skip list. Nous allons créer une interface simple en HTML et JavaScript pour simuler son fonctionnement.

1. Structure HTML

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Ascenseur Magique (Skip List)</title>
    <style>
        .node {
            display: inline-block;
            padding: 5px 10px;
            margin: 5px;
            border: 1px solid #000;
            background-color: #f0f0f0;
        }
        .level {
            margin-bottom: 10px;
        }
    </style>
</head>
<body>
    <h1>Ascenseur Magique (Skip List)</h1>
    <div>
        <input type="number" id="input-value" placeholder="Enter a value" />
        <button onclick="insertValue()">Insert</button>
        <button onclick="searchValue()">Search</button>
        <button onclick="deleteValue()">Delete</button>
    </div>
    <div id="skip-list"></div>
    <script src="skiplist.js"></script>
</body>
</html>

2. Implémentation JavaScript (skiplist.js)

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
    }
}

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
            }
            renderSkipList(); // Rafraîchir l'affichage de la skip list
        }
    }

    // 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
            }
            renderSkipList(); // Rafraîchir l'affichage de la skip list
        }
    }
}

// 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);

// Fonction pour insérer une valeur dans la skip list
function insertValue() {
    const value = parseInt(document.getElementById("input-value").value);
    if (!isNaN(value)) {
        skipList.insert(value);
    }
}

// Fonction pour rechercher une valeur dans la skip list
function searchValue() {
    const value = parseInt(document.getElementById("input-value").value);
    if (!isNaN(value)) {
        const result = skipList.search(value);
        alert(result ? `${value} est présent dans la skip list.` : `${value} n'est pas présent dans la skip list.`);
    }
}

// Fonction pour supprimer une valeur de la skip list
function deleteValue() {
    const value = parseInt(document.getElementById("input-value").value);
    if (!isNaN(value)) {
        skipList.delete(value);
    }
}

// Fonction pour afficher la skip list
function renderSkipList() {
    const container = document.getElementById("skip-list");
    container.innerHTML = ''; // Efface l'affichage précédent

    for (let i = skipList.level; i >= 0; i--) {
        let levelDiv = document.createElement("div");
        levelDiv.className = 'level';
        let node = skipList.header.forward[i];
        while (node !== null) {
            let nodeDiv = document.createElement("div");
            nodeDiv.className = 'node';
            nodeDiv.innerText = node.value;
            levelDiv.appendChild(nodeDiv);
            node = node.forward[i];
        }
        container.appendChild(levelDiv);
    }
}

// Initialisation de l'affichage de la skip list
renderSkipList();

Explications des Fonctions

  1. HTML Structure:

    • Un simple formulaire avec un champ de saisie pour entrer des valeurs et des boutons pour insérer, rechercher et supprimer des valeurs dans la skip list.
    • Un conteneur div (#skip-list) pour afficher la skip list.

  2. JavaScript Code:

    • Classe Node : Représente un nœud dans la skip list avec une valeur et un tableau de pointeurs vers les nœuds suivants.
    • Classe SkipList : Gère les opérations sur la skip list (insertion, recherche, suppression).
    • Méthode renderSkipList : Affiche la skip list de manière visuelle dans le conteneur div.
    • Fonctions insertValue, searchValue, deleteValue : Gèrent les interactions de l'utilisateur pour insérer, rechercher et supprimer des valeurs.

Conclusion

Ce code permet de créer une interface simple pour simuler le fonctionnement d'une skip list en utilisant un ascenseur magique. Les utilisateurs peuvent ajouter, rechercher et supprimer des valeurs tout en visualisant les niveaux de la skip list. 

Modifié le: lundi 3 juin 2024, 05:18