Trie (Árbol de Prefijos)

¿Qué es un Trie?

Analogía: Imagina un diccionario organizado como un árbol. La raíz es vacía. Desde ahí, hay una rama para cada primera letra. Desde cada letra, hay ramas para la segunda letra, y así sucesivamente. Para buscar "casa", sigues: c → a → s → a. Si el camino existe, la palabra está en el diccionario.

Un Trie (se pronuncia "trai", viene de retrieval) almacena un conjunto de strings donde:

• Cada nodo representa un carácter
• El camino de la raíz a un nodo forma un prefijo
• Inserción y búsqueda son $O(L)$ donde L es la longitud del string

Palabras: car, cat, card, care, dog, do

        (raíz)
       /      \
      c         d
      |         |
      a         o
     / \        |
    r    t      g
   / \
  d    e

Implementación con arreglos

const int MAXN = 100005 * 30;  // Máximo total de caracteres
const int ALPHA = 26;          // Tamaño del alfabeto

int trie[MAXN][ALPHA];   // trie[nodo][letra] = siguiente nodo
bool fin[MAXN];           // ¿Este nodo marca el fin de una palabra?
int cnt;                  // Contador de nodos

void init() {
    cnt = 0;
    memset(trie[0], -1, sizeof(trie[0]));
    fin[0] = false;
}

void insertar(const string &s) {
    int nodo = 0;

    for (char c : s) {
        int idx = c - 'a';

        if (trie[nodo][idx] == -1) {
            // Crear nuevo nodo
            cnt++;
            memset(trie[cnt], -1, sizeof(trie[cnt]));
            fin[cnt] = false;
            trie[nodo][idx] = cnt;
        }

        nodo = trie[nodo][idx];
    }

    fin[nodo] = true;  // Marcar fin de palabra
}

bool buscar(const string &s) {
    int nodo = 0;

    for (char c : s) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) return false;
        nodo = trie[nodo][idx];
    }

    return fin[nodo];  // Debe ser fin de palabra, no solo un prefijo
}

bool existePrefijo(const string &s) {
    int nodo = 0;

    for (char c : s) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) return false;
        nodo = trie[nodo][idx];
    }

    return true;  // El prefijo existe
}

Contando palabras con un prefijo

Agrega un contador en cada nodo para saber cuántas palabras pasan por ahí:

int pasos[MAXN];  // Cuántas palabras pasan por este nodo

void insertar(const string &s) {
    int nodo = 0;

    for (char c : s) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) {
            cnt++;
            memset(trie[cnt], -1, sizeof(trie[cnt]));
            fin[cnt] = false;
            pasos[cnt] = 0;
            trie[nodo][idx] = cnt;
        }
        nodo = trie[nodo][idx];
        pasos[nodo]++;
    }

    fin[nodo] = true;
}

int contarConPrefijo(const string &pref) {
    int nodo = 0;
    for (char c : pref) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) return 0;
        nodo = trie[nodo][idx];
    }
    return pasos[nodo];
}

Insertar: "car", "cat", "care", "card"
contarConPrefijo("ca") → 4  (todas empiezan con "ca")
contarConPrefijo("car") → 3  ("car", "care", "card")
contarConPrefijo("dog") → 0

Trie de bits (XOR máximo)

Un uso poderoso: encontrar el XOR máximo de un número con cualquier elemento de un conjunto.

Idea: Inserta los números bit a bit (del más significativo al menos) en un Trie. Para maximizar XOR, en cada bit intenta ir por el camino opuesto.

int bitTrie[MAXN * 32][2];
int bitCnt;

void initBit() {
    bitCnt = 0;
    bitTrie[0][0] = bitTrie[0][1] = -1;
}

void insertarNum(int num) {
    int nodo = 0;
    for (int i = 29; i >= 0; i--) {
        int b = (num >> i) & 1;
        if (bitTrie[nodo][b] == -1) {
            bitCnt++;
            bitTrie[bitCnt][0] = bitTrie[bitCnt][1] = -1;
            bitTrie[nodo][b] = bitCnt;
        }
        nodo = bitTrie[nodo][b];
    }
}

int maxXor(int num) {
    int nodo = 0;
    int resultado = 0;

    for (int i = 29; i >= 0; i--) {
        int b = (num >> i) & 1;
        int opuesto = 1 - b;

        if (bitTrie[nodo][opuesto] != -1) {
            resultado |= (1 << i);  // Este bit contribuye al XOR
            nodo = bitTrie[nodo][opuesto];
        } else {
            nodo = bitTrie[nodo][b];
        }
    }

    return resultado;
}

Aplicaciones del Trie

1. Autocompletado: Dado un prefijo, encontrar todas las palabras que empiezan con él.
2. Corrector ortográfico: Buscar palabras similares.
3. XOR máximo: Encontrar el par con mayor XOR en un arreglo.
4. Conteo de prefijos: ¿Cuántas palabras comparten un prefijo?
5. Longest common prefix: Prefijo común más largo entre strings.

Ejemplo completo

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100005 * 30;
int trie[MAXN][26];
bool fin[MAXN];
int pasos[MAXN];
int cnt;

void init() {
    cnt = 0;
    memset(trie[0], -1, sizeof(trie[0]));
    fin[0] = false;
    pasos[0] = 0;
}

void insertar(const string &s) {
    int nodo = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) {
            cnt++;
            memset(trie[cnt], -1, sizeof(trie[cnt]));
            fin[cnt] = false;
            pasos[cnt] = 0;
            trie[nodo][idx] = cnt;
        }
        nodo = trie[nodo][idx];
        pasos[nodo]++;
    }
    fin[nodo] = true;
}

int main() {
    init();

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        insertar(s);
    }

    while (q--) {
        string pref;
        cin >> pref;

        int nodo = 0;
        bool existe = true;
        for (char c : pref) {
            int idx = c - 'a';
            if (trie[nodo][idx] == -1) { existe = false; break; }
            nodo = trie[nodo][idx];
        }

        cout << (existe ? pasos[nodo] : 0) << "\n";
    }

    return 0;
}

Ejercicio

Dado un arreglo de N enteros, encuentra el máximo XOR entre cualquier par de elementos.

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005 * 32;
int trie[MAXN][2];
int cnt;

void init() {
    cnt = 0;
    trie[0][0] = trie[0][1] = -1;
}

void insertar(int num) {
    int nodo = 0;
    for (int i = 29; i >= 0; i--) {
        int b = (num >> i) & 1;
        if (trie[nodo][b] == -1) {
            cnt++;
            trie[cnt][0] = trie[cnt][1] = -1;
            trie[nodo][b] = cnt;
        }
        nodo = trie[nodo][b];
    }
}

int maxXor(int num) {
    int nodo = 0, res = 0;
    for (int i = 29; i >= 0; i--) {
        int b = (num >> i) & 1;
        int op = 1 - b;
        if (trie[nodo][op] != -1) {
            res |= (1 << i);
            nodo = trie[nodo][op];
        } else {
            nodo = trie[nodo][b];
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    init();
    int mejor = 0;
    insertar(v[0]);

    for (int i = 1; i < n; i++) {
        mejor = max(mejor, maxXor(v[i]));
        insertar(v[i]);
    }

    cout << mejor << endl;
    return 0;
}