Introduction

Les algorithmes de recherche sont utilisés pour trouver des éléments spécifiques dans des structures de données. Trois des techniques de recherche les plus couramment utilisées sont la recherche binaire, les arbres de recherche équilibrés (comme les AVL et les arbres rouges-noirs), et les tables de hachage.

Recherche Binaire

La recherche binaire est une méthode efficace pour trouver un élément dans un tableau trié. Elle divise continuellement le tableau en deux moitiés jusqu'à ce que l'élément soit trouvé ou que la recherche échoue.

Caractéristiques

  • Complexité temporelle : O(log n)
  • Précondition : Le tableau doit être trié.

Étapes de l'algorithme :

  1. Diviser : Comparer l'élément cible avec l'élément au milieu du tableau.
  2. Régner : Si l'élément cible est égal à l'élément du milieu, l'élément est trouvé. Sinon, répéter la recherche dans la moitié appropriée (gauche ou droite) du tableau.
  3. Arrêter : Répéter jusqu'à ce que l'élément soit trouvé ou que la moitié à rechercher soit vide.

Implémentation en JavaScript

// Fonction de recherche binaire
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const middle = Math.floor((left + right) / 2);

        if (arr[middle] === target) {
            return middle; // L'élément est trouvé
        } else if (arr[middle] < target) {
            left = middle + 1; // Rechercher dans la moitié droite
        } else {
            right = middle - 1; // Rechercher dans la moitié gauche
        }
    }

    return -1; // L'élément n'est pas trouvé
}

// Exemple d'utilisation
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 7;
const index = binarySearch(arr, target);
console.log(index); // Output: 3

Explication du Code

  1. Initialisation : Les indices left et right sont définis pour indiquer les bornes du tableau.
  2. Boucle : Tant que left est inférieur ou égal à right, la recherche continue.
  3. Mise à Jour des Indices : Selon la comparaison de l'élément du milieu avec la cible, les indices sont mis à jour pour réduire la zone de recherche.

Arbres de Recherche Équilibrés

Les arbres de recherche équilibrés, tels que les arbres AVL et les arbres rouges-noirs, sont des structures de données qui maintiennent leurs éléments triés et permettent une recherche, une insertion et une suppression efficaces.

Arbres AVL

Un arbre AVL est un arbre binaire de recherche auto-équilibré où la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud est au plus 1.

Caractéristiques

  • Complexité temporelle : O(log n) pour la recherche, l'insertion et la suppression.
  • Équilibrage : Après chaque opération d'insertion ou de suppression, l'arbre est rééquilibré en utilisant des rotations.

Implémentation en JavaScript

class AVLNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }

    // Obtenir la hauteur d'un nœud
    height(node) {
        return node ? node.height : 0;
    }

    // Rotation à droite
    rightRotate(y) {
        const x = y.left;
        const T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;
        x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;

        return x;
    }

    // Rotation à gauche
    leftRotate(x) {
        const y = x.right;
        const T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;
        y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;

        return y;
    }

    // Obtenir le facteur d'équilibre d'un nœud
    getBalance(node) {
        return node ? this.height(node.left) - this.height(node.right) : 0;
    }

    // Insertion d'un nœud
    insert(node, value) {
        if (!node) return new AVLNode(value);

        if (value < node.value) {
            node.left = this.insert(node.left, value);
        } else if (value > node.value) {
            node.right = this.insert(node.right, value);
        } else {
            return node;
        }

        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));

        const balance = this.getBalance(node);

        if (balance > 1 && value < node.left.value) {
            return this.rightRotate(node);
        }

        if (balance < -1 && value > node.right.value) {
            return this.leftRotate(node);
        }

        if (balance > 1 && value > node.left.value) {
            node.left = this.leftRotate(node.left);
            return this.rightRotate(node);
        }

        if (balance < -1 && value < node.right.value) {
            node.right = this.rightRotate(node.right);
            return this.leftRotate(node);
        }

        return node;
    }

    // Insertion publique
    insertValue(value) {
        this.root = this.insert(this.root, value);
    }

    // Recherche d'un nœud
    search(node, value) {
        if (!node || node.value === value) return node;

        if (value < node.value) {
            return this.search(node.left, value);
        } else {
            return this.search(node.right, value);
        }
    }

    // Recherche publique
    searchValue(value) {
        return this.search(this.root, value);
    }
}

// Exemple d'utilisation
const avl = new AVLTree();
avl.insertValue(10);
avl.insertValue(20);
avl.insertValue(30);
avl.insertValue(40);
avl.insertValue(50);
avl.insertValue(25);
console.log(avl.searchValue(30)); // Output: AVLNode { value: 30, left: null, right: null, height: 1 }

Explication du Code

  1. Insertion : Les nœuds sont insérés de manière récursive et l'équilibre de l'arbre est maintenu en effectuant des rotations si nécessaire.
  2. Rotation : Des rotations gauche et droite sont effectuées pour maintenir l'équilibre de l'arbre.
  3. Recherche : La recherche dans un arbre AVL est similaire à la recherche dans un arbre binaire de recherche classique.

Arbres Rouges-Noirs

Un arbre rouge-noir est un arbre binaire de recherche auto-équilibré où chaque nœud contient un bit de couleur (rouge ou noir) pour garantir l'équilibre.

Caractéristiques

  • Complexité temporelle : O(log n) pour la recherche, l'insertion et la suppression.
  • Équilibrage : Utilise des rotations et des changements de couleur pour maintenir les propriétés de l'arbre.

Tables de Hachage

Une table de hachage est une structure de données qui utilise une fonction de hachage pour mapper des clés à des valeurs, permettant une insertion, une recherche et une suppression efficaces.

Caractéristiques

  • Complexité temporelle : O(1) en moyenne pour l'insertion, la recherche et la suppression.
  • Fonction de hachage : Utilisée pour convertir une clé en un indice de tableau.

Implémentation en JavaScript

class HashTable {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
    }

    // Fonction de hachage
    hash(key) {
        let hash = 0;
        for (let char of key) {
            hash += char.charCodeAt(0);
        }
        return hash % this.size;
    }

    // Insertion d'une clé-valeur
    set(key, value) {
        const index = this.hash(key);
        if (!this.table[index]) {
            this.table[index] = [];
        }
        this.table[index].push([key, value]);
    }

    // Recherche d'une valeur par clé
    get(key) {
        const index = this.hash(key);
        if (!this.table[index]) return undefined;

        for (let [k, v] of this.table[index]) {
            if (k === key) return v;
        }
        return undefined;
    }

    // Suppression d'une clé-valeur
    remove(key) {
        const index = this.hash(key);
        if (!this.table[index]) return false;

        for (let i = 0; i < this.table[index].length; i++) {
            if (this.table[index][i][0] === key) {
                this.table[index].splice(i, 1);
                return true;
            }
        }
        return false;
    }
}

// Exemple d'utilisation
const hashTable = new HashTable();
hashTable.set('name', 'John');
hashTable.set('age', 25);
console.log(hashTable.get('name')); // Output: John
console.log(hashTable.get('age')); // Output: 25
hashTable.remove('age');
console.log(hashTable.get('age')); // Output: undefined

Explication du Code

  1. Fonction de Hachage : Convertit une clé en un indice de tableau.
  2. Insertion : La clé-valeur est insérée à l'indice calculé. En cas de collision, une liste chaînée est utilisée.
  3. Recherche : La valeur associée à une clé est recherchée à l'indice calculé.
  4. Suppression : La clé-valeur est supprimée de l'indice calculé.

Comparaison des Algorithmes de Recherche

Complexité Temporelle

  • Recherche Binaire : O(log n)
  • Arbres AVL : O(log n)
  • Arbres Rouges-Noirs : O(log n)
  • Tables de Hachage : O(1) en moyenne

Applications

  • Recherche Binaire : Utilisée pour rechercher des éléments dans des tableaux triés.
  • Arbres AVL et Rouges-Noirs : Utilisés dans les bases de données, les systèmes de fichiers, et d'autres applications nécessitant des opérations de recherche, insertion et suppression efficaces.
  • Tables de Hachage : Utilisées dans les dictionnaires, les caches, et les index de bases de données.

Exemples de Fonctions de Frameworks JavaScript Utilisant des Algorithmes de Recherche

Recherche Binaire

Exemples dans les Frameworks et Bibliothèques

  1. Lodash : Une bibliothèque JavaScript utilitaire qui fournit de nombreuses fonctions utiles, y compris des méthodes pour la recherche binaire.
Exemple d'utilisation de _.sortedIndex dans Lodash
// Chargement de la bibliothèque Lodash
const _ = require('lodash');

// Tableau trié
const arr = [10, 20, 30, 40, 50];

// Élément à insérer
const element = 35;

// Utilisation de _.sortedIndex pour trouver l'indice d'insertion
const index = _.sortedIndex(arr, element);

console.log(index); // Output: 3 (indice où 35 doit être inséré pour maintenir l'ordre trié)

Arbres de Recherche Équilibrés

Exemples dans les Frameworks et Bibliothèques

  1. B-Trees dans IndexedDB : IndexedDB est une API JavaScript pour les bases de données NoSQL dans les navigateurs web. Elle utilise des B-Trees (qui sont similaires aux arbres AVL et aux arbres rouges-noirs) pour stocker et indexer les données.
Exemple d'utilisation de IndexedDB
// Ouverture d'une base de données IndexedDB
const request = indexedDB.open('MyDatabase', 1);

request.onupgradeneeded = function(event) {
    const db = event.target.result;
    // Création d'un objet de stockage avec une clé primaire auto-incrémentée
    const objectStore = db.createObjectStore('MyObjectStore', { keyPath: 'id', autoIncrement: true });
    // Création d'un index sur le champ 'name'
    objectStore.createIndex('name', 'name', { unique: false });
};

request.onsuccess = function(event) {
    const db = event.target.result;
    const transaction = db.transaction(['MyObjectStore'], 'readwrite');
    const objectStore = transaction.objectStore('MyObjectStore');

    // Ajout d'un enregistrement
    const addRequest = objectStore.add({ name: 'John', age: 30 });

    addRequest.onsuccess = function(event) {
        console.log('Enregistrement ajouté avec succès.');
    };

    // Recherche d'un enregistrement par clé
    const getRequest = objectStore.get(1);

    getRequest.onsuccess = function(event) {
        console.log('Enregistrement trouvé:', event.target.result);
    };
};
  1. AVL Tree dans Immutable.js : Immutable.js est une bibliothèque pour la création de structures de données immuables persistantes. Elle utilise des arbres AVL pour certaines de ses structures de données.
Exemple d'utilisation de Map dans Immutable.js
const { Map } = require('immutable');

// Création d'une nouvelle carte immuable
let map1 = Map({ a: 1, b: 2, c: 3 });

// Ajout d'un élément à la carte
let map2 = map1.set('d', 4);

console.log(map1.toJS()); // Output: { a: 1, b: 2, c: 3 }
console.log(map2.toJS()); // Output: { a: 1, b: 2, c: 3, d: 4 }

Tables de Hachage

Exemples dans les Frameworks et Bibliothèques

  1. HashMap dans JavaScript ES6 : JavaScript natif fournit une structure de données Map qui fonctionne comme une table de hachage.
Exemple d'utilisation de Map
// Création d'une nouvelle carte
const map = new Map();

// Ajout d'éléments à la carte
map.set('name', 'John');
map.set('age', 30);

// Recherche d'un élément par clé
console.log(map.get('name')); // Output: John

// Suppression d'un élément par clé
map.delete('age');

// Vérification de la présence d'une clé
console.log(map.has('age')); // Output: false
  1. Redis : Redis est une base de données en mémoire, souvent utilisée comme cache ou magasin de sessions. Elle utilise des tables de hachage pour stocker et récupérer des données rapidement.
Exemple d'utilisation de Redis avec Node.js
const redis = require('redis');
const client = redis.createClient();

client.on('connect', function() {
    console.log('Connecté à Redis...');
});

// Ajout d'un élément à une table de hachage
client.hset('user:1000', 'name', 'John', redis.print);
client.hset('user:1000', 'age', 30, redis.print);

// Recherche d'un élément par clé dans une table de hachage
client.hget('user:1000', 'name', function(err, reply) {
    console.log(reply); // Output: John
});

// Suppression d'un élément par clé dans une table de hachage
client.hdel('user:1000', 'age', function(err, reply) {
    console.log(reply); // Output: 1 (nombre d'éléments supprimés)
});

client.quit();

Conclusion

Les algorithmes de recherche tels que la recherche binaire, les arbres de recherche équilibrés (AVL, arbres rouges-noirs) et les tables de hachage sont largement utilisés dans de nombreux frameworks et bibliothèques JavaScript. Ces structures de données et algorithmes offrent des performances optimales pour la recherche, l'insertion et la suppression, ce qui les rend indispensables pour une variété d'applications pratiques. En comprenant comment ces algorithmes sont utilisés dans des outils comme Lodash, IndexedDB, Immutable.js et Redis, les développeurs peuvent mieux appliquer ces concepts dans leurs propres projets.

 

Modifié le: vendredi 7 juin 2024, 06:11