Trie (Árbol de Prefijos)

Un Trie (del inglés "retrieval tree") es un árbol especial para almacenar strings. Cada nodo representa un carácter, y el camino desde la raíz hasta un nodo forma un prefijo. Si guardas las palabras "casa", "cama", "castillo", comparten el nodo "c" y "a".

La búsqueda de si una palabra o prefijo existe es O(L) donde L es la longitud, sin importar cuántas palabras estén almacenadas. Búsqueda en diccionario de millones de palabras en microsegundos.

El autocompletado que ves en Google, en apps de notas o en tu teléfono usa una variación de Trie internamente. Cuando escribes "prog", el sistema navega el Trie hasta el nodo "g" y devuelve todas las palabras en ese subárbol (como "programa", "programar", "programación").

También es útil para detección de palabras en un texto, validación de palabras en juegos como Scrabble, y comprimir datos repetitivos con patrones comunes. Implementar un Trie desde cero es un ejercicio clásico de entrevistas.

class NodoTrie {
  constructor() {
    this.hijos = {};
    this.esFin = false; // Marca fin de palabra
  }
}

class Trie {
  constructor() {
    this.raiz = new NodoTrie();
  }
  
  // Insertar palabra O(L)
  insertar(palabra) {
    let actual = this.raiz;
    for (const char of palabra) {
      if (!actual.hijos[char]) {
        actual.hijos[char] = new NodoTrie();
      }
      actual = actual.hijos[char];
    }
    actual.esFin = true;
  }
  
  // Buscar palabra exacta O(L)
  buscar(palabra) {
    let actual = this.raiz;
    for (const char of palabra) {
      if (!actual.hijos[char]) return false;
      actual = actual.hijos[char];
    }
    return actual.esFin;
  }
  
  // Verificar si existe prefijo O(L)
  empiezaCon(prefijo) {
    let actual = this.raiz;
    for (const char of prefijo) {
      if (!actual.hijos[char]) return false;
      actual = actual.hijos[char];
    }
    return true;
  }
  
  // Autocompletado - todas las palabras con el prefijo
  sugerencias(prefijo) {
    let actual = this.raiz;
    for (const char of prefijo) {
      if (!actual.hijos[char]) return [];
      actual = actual.hijos[char];
    }
    // DFS desde el nodo del prefijo
    const resultado = [];
    this.#dfs(actual, prefijo, resultado);
    return resultado;
  }
  
  #dfs(nodo, prefixActual, resultado) {
    if (nodo.esFin) resultado.push(prefixActual);
    for (const [char, hijo] of Object.entries(nodo.hijos)) {
      this.#dfs(hijo, prefixActual + char, resultado);
    }
  }
}

// Uso
const trie = new Trie();
["manzana","mandarina","mango","melon","mora"].forEach(p => trie.insertar(p));
console.log(trie.buscar("mango"));        // true
console.log(trie.buscar("man"));          // false
console.log(trie.empiezaCon("man"));      // true
console.log(trie.sugerencias("man"));     // ["manzana","mandarina","mango"]