Estructuras Avanzadastriestringsprefijosestructuras-de-datos

Trie (Árbol de Prefijos)

Aprende a usar Tries para búsqueda eficiente de strings y prefijos

OOI Oaxaca9 de febrero de 20267 min read

¿Qué es un Trie?

Un Trie (pronunciado "try") es un árbol de prefijos que permite operaciones eficientes con strings:

Insertar una palabra en $O(m)$
Buscar una palabra en $O(m)$
Buscar prefijo en $O(m)$

Donde $m$ es la longitud del string.

Visualización

Palabras: ["car", "card", "care", "cat", "dog"]

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

(✓) = fin de palabra

Implementación con nodos

const int ALPHABET = 26;

struct TrieNode {
    TrieNode* hijos[ALPHABET];
    bool finDePalabra;

    TrieNode() {
        for (int i = 0; i < ALPHABET; i++) {
            hijos[i] = nullptr;
        }
        finDePalabra = false;
    }
};

class Trie {
private:
    TrieNode* raiz;

public:
    Trie() {
        raiz = new TrieNode();
    }

    void insertar(string palabra) {
        TrieNode* nodo = raiz;
        for (char c : palabra) {
            int idx = c - 'a';
            if (nodo->hijos[idx] == nullptr) {
                nodo->hijos[idx] = new TrieNode();
            }
            nodo = nodo->hijos[idx];
        }
        nodo->finDePalabra = true;
    }

    bool buscar(string palabra) {
        TrieNode* nodo = raiz;
        for (char c : palabra) {
            int idx = c - 'a';
            if (nodo->hijos[idx] == nullptr) {
                return false;
            }
            nodo = nodo->hijos[idx];
        }
        return nodo->finDePalabra;
    }

    bool empiezaCon(string prefijo) {
        TrieNode* nodo = raiz;
        for (char c : prefijo) {
            int idx = c - 'a';
            if (nodo->hijos[idx] == nullptr) {
                return false;
            }
            nodo = nodo->hijos[idx];
        }
        return true;
    }
};

Uso

int main() {
    Trie trie;

    trie.insertar("car");
    trie.insertar("card");
    trie.insertar("care");
    trie.insertar("cat");

    cout << trie.buscar("car") << endl;      // 1 (true)
    cout << trie.buscar("ca") << endl;       // 0 (false)
    cout << trie.empiezaCon("ca") << endl;   // 1 (true)
    cout << trie.empiezaCon("dog") << endl;  // 0 (false)

    return 0;
}

Implementación con arrays (más rápida)

Para competencias, es más eficiente usar arrays:

const int MAXN = 1000005;  // Total de nodos posibles
const int ALPHABET = 26;

int trie[MAXN][ALPHABET];
bool finPalabra[MAXN];
int contador = 0;

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

int nuevoNodo() {
    contador++;
    memset(trie[contador], -1, sizeof(trie[contador]));
    finPalabra[contador] = false;
    return contador;
}

void insertar(string& s) {
    int nodo = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) {
            trie[nodo][idx] = nuevoNodo();
        }
        nodo = trie[nodo][idx];
    }
    finPalabra[nodo] = true;
}

bool buscar(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 finPalabra[nodo];
}

Contar palabras con prefijo

int conteo[MAXN];  // Palabras que pasan por este nodo

void insertar(string& s) {
    int nodo = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) {
            trie[nodo][idx] = nuevoNodo();
        }
        nodo = trie[nodo][idx];
        conteo[nodo]++;
    }
    finPalabra[nodo] = true;
}

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

Trie de bits (XOR máximo)

Un trie de bits es muy útil para encontrar el XOR máximo:

const int LOG = 30;  // Bits para enteros

int trie[MAXN * LOG][2];
int contador = 0;

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

int nuevoNodo() {
    contador++;
    trie[contador][0] = trie[contador][1] = -1;
    return contador;
}

void insertar(int num) {
    int nodo = 0;
    for (int i = LOG - 1; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (trie[nodo][bit] == -1) {
            trie[nodo][bit] = nuevoNodo();
        }
        nodo = trie[nodo][bit];
    }
}

int maxXOR(int num) {
    int nodo = 0;
    int resultado = 0;
    for (int i = LOG - 1; i >= 0; i--) {
        int bit = (num >> i) & 1;
        int opuesto = 1 - bit;

        if (trie[nodo][opuesto] != -1) {
            resultado |= (1 << i);
            nodo = trie[nodo][opuesto];
        } else {
            nodo = trie[nodo][bit];
        }
    }
    return resultado;
}

Uso: XOR máximo en array

int maxXORPar(vector<int>& arr) {
    init();
    int maxVal = 0;

    insertar(arr[0]);
    for (int i = 1; i < arr.size(); i++) {
        maxVal = max(maxVal, maxXOR(arr[i]));
        insertar(arr[i]);
    }

    return maxVal;
}

Aplicaciones

1. Autocompletado

void autocompletar(TrieNode* nodo, string prefijo, vector<string>& sugerencias) {
    if (nodo->finDePalabra) {
        sugerencias.push_back(prefijo);
    }

    for (int i = 0; i < 26; i++) {
        if (nodo->hijos[i] != nullptr) {
            autocompletar(nodo->hijos[i], prefijo + char('a' + i), sugerencias);
        }
    }
}

vector<string> obtenerSugerencias(Trie& trie, string prefijo) {
    TrieNode* nodo = trie.raiz;
    for (char c : prefijo) {
        int idx = c - 'a';
        if (nodo->hijos[idx] == nullptr) {
            return {};
        }
        nodo = nodo->hijos[idx];
    }

    vector<string> sugerencias;
    autocompletar(nodo, prefijo, sugerencias);
    return sugerencias;
}

2. Longest Common Prefix

string longestCommonPrefix(vector<string>& palabras) {
    if (palabras.empty()) return "";

    Trie trie;
    for (string& s : palabras) {
        trie.insertar(s);
    }

    string lcp = "";
    TrieNode* nodo = trie.raiz;

    while (true) {
        int count = 0, idx = -1;
        for (int i = 0; i < 26; i++) {
            if (nodo->hijos[i] != nullptr) {
                count++;
                idx = i;
            }
        }

        if (count != 1 || nodo->finDePalabra) break;

        lcp += char('a' + idx);
        nodo = nodo->hijos[idx];
    }

    return lcp;
}

3. Número de strings distintos

int contarDistintos() {
    int total = 0;
    for (int i = 0; i <= contador; i++) {
        if (finPalabra[i]) total++;
    }
    return total;
}

Template completo

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
const int ALPHABET = 26;

int trie[MAXN][ALPHABET];
bool finPalabra[MAXN];
int cnt[MAXN];  // Contador de palabras con este prefijo
int contador;

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

int nuevoNodo() {
    contador++;
    memset(trie[contador], -1, sizeof(trie[contador]));
    finPalabra[contador] = false;
    cnt[contador] = 0;
    return contador;
}

void insertar(const string& s) {
    int nodo = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (trie[nodo][idx] == -1) {
            trie[nodo][idx] = nuevoNodo();
        }
        nodo = trie[nodo][idx];
        cnt[nodo]++;
    }
    finPalabra[nodo] = true;
}

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 finPalabra[nodo];
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    init();

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

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

    while (q--) {
        string s;
        cin >> s;
        cout << contarPrefijo(s) << "\n";
    }

    return 0;
}

Complejidades

Operación	Tiempo	Espacio
Insertar	$O(m)$	$O(m \cdot \Sigma)$
Buscar	$O(m)$	-
Prefijo	$O(m)$	-

Donde $m$ = longitud del string, $\Sigma$ = tamaño del alfabeto.