🧱 Trie
Estructura de datos · Se implementa a mano · Tema: Strings y Secuencias Catálogo completo: Catálogo de estructuras
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
Árbol de prefijos: inserta y busca cadenas (o números en binario) compartiendo prefijos comunes.
Operaciones y costo
| Operación | Costo | Notas |
|---|---|---|
| Insertar una palabra | O(largo) | independiente de cuántas palabras haya |
| Buscar una palabra | O(largo) | |
| Buscar un prefijo | O(largo) | su gracia frente a un set de strings |
| Espacio | O(caracteres × alfabeto) | puede ser pesado |
Por dentro
Un árbol donde cada arista es una letra: las palabras que comparten prefijo comparten camino desde la raíz. Buscar es caminar letra por letra.
Cuándo usarla
Conjunto de cadenas con consultas de prefijo; XOR máximo (trie binario). Es lo único ‘de strings’ que entra en el syllabus.
Implementación recomendada (C++)
struct Trie {
struct Node { int next[26]; bool end = false; Node(){ fill(next, next + 26, -1); } };
vector<Node> t; // los nodos viven en un vector; -1 = sin hijo
Trie() { t.emplace_back(); } // nodo 0 = raíz
void insert(const string& s) {
int cur = 0;
for (char c : s) {
int x = c - 'a'; // 'a'->0, 'b'->1, ...
if (t[cur].next[x] == -1) { t[cur].next[x] = t.size(); t.emplace_back(); }
cur = t[cur].next[x];
}
t[cur].end = true; // aquí termina una palabra
}
int bajar(const string& s) { // nodo al que lleva s, o -1 si no existe
int cur = 0;
for (char c : s) {
int x = c - 'a';
if (t[cur].next[x] == -1) return -1;
cur = t[cur].next[x];
}
return cur;
}
bool contains(const string& s) { int u = bajar(s); return u != -1 && t[u].end; }
bool prefijo(const string& s) { return bajar(s) != -1; } // ¿alguna empieza así?
};⚠️ Notas
Los nodos se guardan en un vector y se enlazan por índice en vez de por puntero: más rápido y más fácil de depurar (ver Punteros y referencias). Para XOR máximo usa un trie binario (2 hijos, bits de mayor a menor). Recuerda que KMP/suffix array/hashing están excluidos del syllabus.