Introduction à Trie (arbre de préfixes)

Un Trie est une structure de données arborescente qui est utilisée pour stocker et rechercher efficacement des chaînes, en particulier dans des applications telles que la saisie semi-automatique, la vérification orthographique et le routage IP.

---

Propriétés clés d'un Trie :

1. Nœuds : Chaque nœud représente un personnage.
2. Root : Le nœud racine est vide et sert de point de départ.
3. Enfants : Chaque nœud a jusqu'à 26 enfants (pour les lettres anglaises minuscules) ou plus, selon le jeu de caractères.
4. Marqueur de fin de mot : Certains nœuds sont marqués pour indiquer la fin d'un mot.

---

Opérations de base de Trie :

1. Insertion

Insérer un mot implique de parcourir le trie et de créer de nouveaux nœuds pour les caractères qui n'existent pas.

2. Rechercher

La recherche vérifie si un mot existe dans le trie en parcourant ses nœuds.

3. Recherche de préfixe

Cela vérifie si un mot du trie commence par un préfixe donné.

---

Implémentation de Basic Trie en JavaScript :

class TrieNode {
    constructor() {
        this.children = {}; // Stores child nodes
        this.isEndOfWord = false; // Marks the end of a word
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Insert a word
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

---

Opérations avancées de Trie :

1. Supprimer un mot :

La suppression d'un mot implique une approche récursive, où nous supprimons les nœuds qui ne sont plus nécessaires.

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

2. Compter les mots avec un préfixe :

Comptez combien de mots commencent par un préfixe donné.

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count += this._countWords(node.children[char]);
    }
    return count;
}

3. Suggestions de saisie semi-automatique :

À partir d'un préfixe, renvoie tous les mots qui commencent par celui-ci.

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix + char));
    }

    return results;
}

---

Complexité temporelle :

1. Insérer : O(L) (L = longueur du mot)
2. Recherche : O(L)
3. Recherche de préfixe : O(L)
4. Supprimer : O(L)

---

Applications de Trie :

1. Systèmes de saisie semi-automatique (par exemple, barres de recherche, éditeurs de texte).
2. Vérificateurs orthographiques.
3. Routage IP (correspondance du préfixe le plus long).
4. Jeux de mots (par exemple, Boggle).
5. Correspondance des séquences d'ADN.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!