Tries

¿Qué es un Trie?

Un Trie (árbol de prefijos) es una estructura tipo árbol para almacenar strings. Cada nodo representa un carácter, ideal para autocompletado, correctores y búsqueda por prefijos.

Implementación de Trie

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

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

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

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }

  autocomplete(prefix) {
    let node = this.root;

  

    
Aprende más
    

      
        
GeeksforGeeks: Trie
        
Aprende a implementar y usar Tries.
      
      
        
LeetCode: Trie
        
Resuelve problemas avanzados de strings con Tries.
      
    
  

    // Navigate to prefix
    for (const char of prefix) {
      if (!node.children[char]) return [];
      node = node.children[char];
    }
    
    // Collect all words with this prefix
    const results = [];
    this.collectWords(node, prefix, results);
    return results;
  }

  collectWords(node, currentWord, results) {
    if (node.isEndOfWord) {
      results.push(currentWord);
    }
    for (const char in node.children) {
      this.collectWords(node.children[char], currentWord + char, results);
    }
  }
}

// Usage
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
console.log(trie.search("app"));           // true
console.log(trie.startsWith("app"));       // true
console.log(trie.autocomplete("app"));     // ['app', 'apple', 'application']