Oubliez tout ce que vous savez sur la recherche de chaînes – les essais vous épateront !

Introduction à la structure de données Trie

Un trie, également connu sous le nom d'arbre de préfixes, est une structure de données arborescente efficace utilisée pour stocker et récupérer des chaînes. Il est particulièrement utile pour les tâches impliquant des recherches de chaînes, la correspondance de préfixes et la fonctionnalité de saisie semi-automatique.

Prononciation:

• C'est un mot d'une seule syllabe
• Le "ie" à la fin se prononce comme un long "e", semblable à "see" ou "tree"
• Ça ne rime pas avec "tarte" ou "mourir" Cette prononciation permet de le distinguer des autres mots d'apparence similaire et souligne son lien avec les opérations de récupération de données.

Quand utiliser un essai

Les essais sont idéaux dans les scénarios où vous devez :

1. Effectuez rapidement des recherches basées sur les préfixes
2. Implémenter les fonctionnalités de saisie semi-automatique
3. Stockez un dictionnaire de mots pour la vérification orthographique
4. Stockez et récupérez efficacement des chaînes avec des préfixes courants ## Visualiser un Trie

Visualisons un trie contenant les mots « chat », « voiture » et « chien » :

       root
     /   |   \
    c    d    ...
   /     |
  a      o
 / \     |
t   r    g

Chaque nœud représente un caractère et les chemins allant de la racine aux nœuds feuilles forment des mots complets.

Implémentation d'un Trie en JavaScript

Implémentons une structure trie de base en JavaScript :

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

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

  // Insert a word into the trie
  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;
  }

  // Search for a word in the trie
  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();

// Insert words
trie.insert("apple");
trie.insert("app");
trie.insert("banana");

console.log(trie.search("apple"));    // Output: true
console.log(trie.search("app"));      // Output: true
console.log(trie.search("appl"));     // Output: false
console.log(trie.startsWith("app"));  // Output: true
console.log(trie.startsWith("ban"));  // Output: true
console.log(trie.startsWith("cat"));  // Output: false

Explication du Code

1. classe TrieNode : Représente un nœud dans le trie. Chaque nœud possède : Un objet pour stocker les nœuds enfants : Un drapeau booléen pour marquer la fin d'un mot
2. class Trie : La structure principale du trie avec les méthodes :
   • insérer : ajoute un mot au trie
   • recherche : Vérifie si un mot existe dans le trie
   • startsWith : vérifie si un mot du trie commence par le préfixe donné
3. La méthode parcourt le trie, créant de nouveaux nœuds pour les caractères qui n'existent pas et marquant le dernier nœud comme fin d'un mot.
4. La méthode parcourt le trie le long du chemin du mot donné, retournant si le mot entier est trouvé et marqué comme un mot complet.
5. La méthode est similaire à mais vérifie uniquement si le préfixe donné existe dans le trie, qu'il s'agisse ou non d'un mot complet.

Complexité temporelle et spatiale

• Complexité temporelle :
  • Insérer : O(m), où m est la longueur du mot
  • Recherche : O(m), où m est la longueur du mot
  • StartsWith : O(m), où m est la longueur du préfixe
• Complexité spatiale : O(n * m), où n est le nombre de mots et m est la longueur moyenne des mots

Les essais offrent d'excellentes performances pour les opérations liées aux chaînes, en particulier lorsqu'il s'agit d'un grand nombre de mots avec des préfixes communs. Ils fournissent des recherches rapides et une correspondance de préfixes, ce qui les rend inestimables dans diverses applications telles que les systèmes de saisie semi-automatique, les tables de routage IP et les implémentations de dictionnaires.

Si vous avez aimé ce tutoriel, suivez-moi ici et sur X/Twitter à @turckalicious. Cet article a été réalisé avec l'aide de Wonderfall (https://wonderfall.xyz), un éditeur de documents interactif alimenté par l'IA qui vous aide à rechercher, écrire et itérer plus rapidement.

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!