Un Trie es una estructura de datos del tipo diccionario cuyas claves son strings.
En breve veremos la flexibilidad de los tries; pero bajo esta definición, en principio podemos simularlo con un map:

    /// Falso trie
    map<string, int> T;
    T["edad"] = 16
    T["altura"] = 174

Al escribir nosotros mismos la estructura, podemos mejorarla para añadir operaciones que map no soporta, a la vez que mejoramos la eficiencia.

Concretamente, llamamos Trie a un árbol con raíz donde cada arco está etiquetado con un carácter, y dos arcos con la misma etiqueta no pueden salir del mismo nodo. De esta manera, cada nodo representa al string que se obtiene de mirar el camino desde la raíz a él.

Imagen: Wikipedia.
Trie con contenido: “A” : 15, “to” : 7, “tea” : 3, “ted” : 4, “ten” : 12, “i” : 11, “in” : 5, “inn” : 9.
Los nodos no guardan las claves sino el valor (en azul), las etiquetas están sólo a modo de ilustración.

Las operaciones básicas de todo diccionario son:

• insertar(clave, valor) : asocia el valor a la clave
• buscar(clave) : devuelve el valor asociado a la clave (o indica que no se encuentra)
• eliminar(clave) : elimina la entrada

Inicialmente se tiene un trie vacío que consiste de un único nodo: la raíz.

• Para insertar un string a un trie, sólo hay que ir recorriéndolo desde la raíz creando los árcos y los nodos que hagan falta. En nuestro ejemplo anterior, si queremos agregar la palabra “TENAZ”, llegaremos hasta el nodo “TEN”, y luego vamos a tener que agregar dos arcos (y sus correspondientes nodos): A y Z para formar “TENAZ”.
• Para buscar un string, recorremos el trie desde la raíz hasta llegar al nodo tomando los arcos indicados por cada letra del string, en orden. Si en algún momento necesitamos tomar un arco que no existe, concluimos que el elemento buscado no se encuentra.
• Para borrar, hacemos una búsqueda, pero en lugar de borrar el nodo simplemente lo marcamos como “eliminado” y lo ignoramos en las subsecuentes búsquedas. Se debe recordar desmarcarlo si se hace una inserción.

Llamemos $n$ a la cantidad de elementos en la estructura y $k$ es la longitud de una clave.

Mientras que un map tiene una complejidad temporal $O(k\ \log n)$ para todas estas operaciones, un trie lo logra en $O(k)$: ¡es lineal!

Asímismo, la complejidad espacial también es lineal, $O(S)$ donde $S$ es la suma de las longitudes de todas las claves.

Se sugiere fuertemente intentar programar un trie por cuenta propia sabiendo las ideas ya vistas.

Se proveen acá dos implementaciones de tries, una recursiva, y una iterativa.
De cualquier manera, la estructura propiamente dicha del trie es recursiva. ¿Por qué?

Al pensar recursivamente, se cometen menos errores.

trie_recursivo.cpp

#include <iostream>
#include <map>
using namespace std;
 
struct trie{
    map<char, trie> m;  // arcos
    bool final = false; // una palabra termina en este nodo?
 
    void agregar(char *s){
        if( *s )    m[*s].agregar(s+1);
        else        final = true;
    }
    trie* buscar(char *s){
        if( *s ){ 
            if( m.count(*s) ) return m[*s].buscar(s+1);
            else              return NULL; 
        }else
            if( final )       return this;
            else              return NULL;
    }
    void eliminar(char *s){
        if( *s )    m[*s].eliminar(s+1);
        else        final = false;
    }
};
 
int main(){
    trie t;
 
    t.agregar("CASA");
    t.agregar("CAMA");
    t.agregar("CAMARERO");
    t.agregar("CASERO");
 
    if( t.buscar("CAM") ) cout<<"CAM esta"<<endl;
    else                  cout<<"CAM no esta"<<endl;
 
    if( t.buscar("CAMA") ) cout<<"CAMA esta"<<endl;
    else                   cout<<"CAMA no esta"<<endl;
 
    t.eliminar("CAMA");
 
    if( t.buscar("CAMA") ) cout<<"CAMA esta"<<endl;
    else                   cout<<"CAMA no esta"<<endl;
 
    if( t.buscar("CAMARERO") ) cout<<"CAMARERO esta"<<endl;
    else                       cout<<"CAMARERO no esta"<<endl;
 
    return 0;
}

Esta implementación está buena como primera idea porque es simple. Sin embargo, realiza demasiadas llamadas a función, lo cual realentiza nuestro programa. También, al buscar un nodo, me devuelve un puntero a él. Usar punteros puede no ser muy estratégico en ámbitos de competencia. A continuación se provee de una implementación iterativa que es más rápida y no usa punteros.

trie_iterativo.cpp

#include <iostream>
#include <string>
#include <cstring>
#define forn(i, n) for(int i = 0; i < int(n); ++i)
using namespace std;
 
const int maxn = 1000; // maxima cantidad de nodos
 
int proximo_libre;
int sig[maxn][26]; // arcos (en este caso solo letras mayusculas)
bool final[maxn];  // una palabra termina en este nodo?
 
void agregar(const string &s, int raiz = 0){
    int actual = raiz;
    forn(i, s.size()){
        int letra = s[i] - 'A';
        if( sig[ actual ][ letra ] == -1 )
            sig[ actual ][ letra ] = proximo_libre++;
        actual = sig[ actual ][ letra ];
    }
    final[ actual ] = true;
}
 
int buscar(const string &s, int raiz = 0){
    int actual = raiz;
    forn(i, s.size()){
        int letra = s[i] - 'A';
        if( sig[ actual ][ letra ] == -1 )
            return -1;
        actual = sig[ actual ][ letra ];
    }
    if( final[ actual ] ) return actual;
    else                  return -1;
}
 
void eliminar(const string &s, int raiz = 0){
    int actual = raiz;
    forn(i, s.size()){
        int letra = s[i] - 'A';
        if( sig[ actual ][ letra ] == -1 )
            return;
        actual = sig[ actual ][ letra ];
    }
    final[ actual ] = false;
}
 
 
int main(){
    memset(sig, -1, sizeof(sig)); // seteamos en -1 todos los arcos
 
    agregar("CASA");
    agregar("CAMA");
    agregar("CAMARERO");
    agregar("CASERO");
 
    int trie2 = proximo_libre++;
    agregar("CAMA", trie2);
 
    if( buscar("CAM") != -1 ) cout<<"CAM esta"<<endl;
    else                      cout<<"CAM no esta"<<endl;
 
    if( buscar("CAMA") != -1 ) cout<<"CAMA esta"<<endl;
    else                       cout<<"CAMA no esta"<<endl;
 
    eliminar("CAMA");
 
    if( buscar("CAMA") != -1 ) cout<<"CAMA esta"<<endl;
    else                       cout<<"CAMA no esta"<<endl;
 
    if( buscar("CAMARERO") != -1 ) cout<<"CAMARERO esta"<<endl;
    else                           cout<<"CAMARERO no esta"<<endl;
 
    cout<<"En el trie 2:"<<endl;
 
    if( buscar("CAMA", trie2) != -1 ) cout<<"CAMA esta"<<endl;
    else                              cout<<"CAMA no esta"<<endl;
 
    if( buscar("CAMARERO", trie2) != -1 ) cout<<"CAMARERO esta"<<endl;
    else                                  cout<<"CAMARERO no esta"<<endl;
 
    return 0;
}

Un detalle para tener en cuenta es que para no tener que lidiar con memoria dinámica, reservamos estáticamente la memoria para todos los nodos posibles. De esta manera, cada nodo está identificado con un entero y ya no tenemos que devolver punteros. Más aún, esto no nos imposibilita usar varios tries en simultáneo: cada vez que se desee crear uno nuevo, se reserva un nodo para la raíz.

Tomemos la lista de palabras que se quiere ordenar e ingresémosla en un trie. Un recorrido DFS que visita los arcos en orden alfabético recorrerá las palabras lexicográficamente. Recorrer los arcos en sentido inverso para ordenar las palabras en sentido contrario.

Esta mejora es muy sencilla pero muy poderosa, consiste en agregar un contador a cada nodo. Cada vez que se inserte una palabra que pase por el nodo, se aumenta el contador en 1. Ahora podemos escribir una función cuentaPrefijos( s ) que devuelve la cantidad de palabras que comienzan con s.

agregar("CASA");
agregar("CAMA");
agregar("CAMARERO");
agregar("CASERO");

cuentaPrefijos("CA") --> 4
cuentaPrefijos("CASE") --> 1
cuentaPrefijos("CASO") --> 0

• Ejercicio: Dibujar el trie que contiene la palabra “CAMISA”, y dibujar otro trie que contiene las palabras “CAMISA”, “CAMIS”, “CAMI”, “CAM”, “CA”, y “C”.

Ambos son el mismo trie, ¿no? Esto es porque al ingresar una palabra, también ingresamos todos sus prefijos. La única diferencia es que en el primer caso, sólo un nodo es final, mientras que en el segundo todos los nodos son finales. Podemos escribir una función agregarPrefijos que sea exactamente igual a “agregar” pero que vaya marcando todos los nodos como finales. ¡Y mantenemos la complejidad $O(k)$!

Por lo tanto, si queremos insertar todos los substrings de un texto de longitud $T$, sólo necesitamos agregarPrefijos de sus $T$ sufijos, que tarda $O(T^2)$ en total. Una vez construido este trie de sufijos, muchas operaciones pueden realizarse eficientemente:

Si tenemos un string $S$, la cantidad de apariciones en el texto es simplemente cuentaPrefijos(S) en el trie de sufijos.

Adicionalmente, si en cada inserción además de marcar el nodo como final, guardamos el índice del substring, un recorrido del subtrie cuya raiz se corresponde a $S$ nos arrojará todos los índices en los cuales aparece $S$ con costo adicional $O(A)$ donde $A$ es la cantidad de apariciones.

Consideremos un recorrido DFS en el trie de sufijos. Un nodo de profundidad $l$ se corresponde con un string de largo $l$. Por lo que recorreremos el trie buscando un nodo de profundidad máxima cuyo contador sea mayor o igual a $K$.

Supongamos que tenemos una lista de $n$ palabras de longitud $s_i$. Construyamos un trie de sufijos común a todas las palabras, pero manteniendo con cuidado un contador en cada nodo que indica a cuántas palabras distintas corresponde ese nodo. Es decir, si tengo dos palabras: “PAPA” y “PALO”, el nodo correspondiente a “PA” tiene contador 2 -y no 3- ya que aunque aparece 3 veces, aparece sólo en 2 palabras distintas. La respuesta a nuestro problema está dada por el nodo más profundo cuyo contador sea al menos $K$.

El costo de construcción de este trie de prefijos común es $O(s_1^2 + \dots + s_n^2)$, por lo que es cuadrático.

Consiste en guardar en cada nodo, cuál es su padre. Esto permite moverse en cualquier dirección dentro del trie, lo cual nos será útil en la siguiente mejora:

En lugar de etiquetar los arcos con letras, se los puede etiquetar con cualquier otra cosa, por ejemplo: enteros. Si la cantidad de etiquetas distintas -llamémosla $E$- no está acotada, quizás haya que usar un map<int, trie> a costa de un $O(\log E)$ adicional.

Una estructura de datos persistente es, hablando mal y pronto, una estructura donde cada operación devuelve una copia nueva en lugar de modificar la anterior. De esta manera, ambas versiones son totalmente independientes y uno puede optar seguir realizando operaciones en cualquiera de ellas.

Una pila (stack) es una estructura de datos que permite las siguientes operaciones:

• push(x): apila x en el tope de la pila
• top(): devuelve el valor del tope de la pila
• pop(): desapila el elemento del tope de la pila

Así, una pila persistente es una pila donde cada operación (excepto quizás top que no hace nada) devuelve una nueva instancia de la pila.

Una pila de enteros persistente se corresponde con un nodo s de un trie etiquetado con enteros:

• push_persistente(s, x): insertar un arco y un nodo s' con etiqueta x, luego la nueva pila es s'.
• pop_persitente(s): sea s' el padre de s, la nueva pila es s'.

¡Estas operaciones persistentes siguen siendo constantes! $O(1)$

max xor pair from set max xor subarray number of subarrays with xor less than K tries in game theory IOI 2008 type printer IOI 2012 scrivener OIA formando equipo ??? cellphone prediction DP + trie