🧱 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ónCostoNotas
Insertar una palabraO(largo)independiente de cuántas palabras haya
Buscar una palabraO(largo)
Buscar un prefijoO(largo)su gracia frente a un set de strings
EspacioO(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.