Trie en C: ejercicio resuelto

Si buscas trie en C ejercicio resuelto, aquí tienes la implementación con asignación dinámica que cubre inserción, búsqueda exacta y búsqueda de prefijo. Un trie (árbol de prefijos o árbol digital) almacena cadenas compartiéndolas carácter a carácter, lo que permite búsquedas en O(m) donde m es la longitud de la clave, independientemente de cuántas cadenas haya en la estructura.

Enunciado

Implementa un trie para el alfabeto de letras minúsculas que soporte:

trie_insertar(raiz, palabra): inserta una palabra.
trie_buscar(raiz, palabra): devuelve 1 si la palabra exacta existe.
trie_prefijo(raiz, prefijo): devuelve 1 si alguna palabra comienza con el prefijo.

Inserta ["casa", "caro", "carta", "perro", "pez"] y prueba varias búsquedas.

Solución en C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALFA 26   /* solo letras minúsculas a-z */

typedef struct Nodo {
    struct Nodo *hijos[ALFA];
    int fin_palabra;   /* 1 si alguna palabra termina aquí */
} Nodo;

static Nodo *nuevo_nodo(void) {
    Nodo *n = calloc(1, sizeof(Nodo));  /* calloc pone todo a cero */
    return n;
}

void trie_insertar(Nodo *raiz, const char *pal) {
    Nodo *cur = raiz;
    for (int i = 0; pal[i]; i++) {
        int idx = pal[i] - 'a';
        if (!cur->hijos[idx]) cur->hijos[idx] = nuevo_nodo();
        cur = cur->hijos[idx];
    }
    cur->fin_palabra = 1;
}

static Nodo *trie_camino(Nodo *raiz, const char *s) {
    Nodo *cur = raiz;
    for (int i = 0; s[i]; i++) {
        int idx = s[i] - 'a';
        if (!cur->hijos[idx]) return NULL;
        cur = cur->hijos[idx];
    }
    return cur;
}

int trie_buscar(Nodo *raiz, const char *pal) {
    Nodo *n = trie_camino(raiz, pal);
    return n && n->fin_palabra;
}

int trie_prefijo(Nodo *raiz, const char *pref) {
    return trie_camino(raiz, pref) != NULL;
}

void trie_liberar(Nodo *n) {
    if (!n) return;
    for (int i = 0; i < ALFA; i++) trie_liberar(n->hijos[i]);
    free(n);
}

int main(void) {
    Nodo *raiz = nuevo_nodo();
    const char *palabras[] = {"casa", "caro", "carta", "perro", "pez"};

    for (int i = 0; i < 5; i++) trie_insertar(raiz, palabras[i]);

    /* Búsquedas exactas */
    const char *buscar[] = {"casa", "car", "carta", "per", "pez", "perros"};
    for (int i = 0; i < 6; i++)
        printf("buscar(\"%s\") = %d\n", buscar[i], trie_buscar(raiz, buscar[i]));

    printf("\n");

    /* Búsquedas de prefijo */
    const char *prefijos[] = {"car", "ca", "pe", "xyz", "p"};
    for (int i = 0; i < 5; i++)
        printf("prefijo(\"%s\") = %d\n", prefijos[i], trie_prefijo(raiz, prefijos[i]));

    trie_liberar(raiz);
    return 0;
}

Resultado esperado

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
buscar("casa") = 1
buscar("car") = 0
buscar("carta") = 1
buscar("per") = 0
buscar("pez") = 1
buscar("perros") = 0

prefijo("car") = 1
prefijo("ca") = 1
prefijo("pe") = 1
prefijo("xyz") = 0
prefijo("p") = 1

Errores frecuentes

Confundir búsqueda exacta con búsqueda de prefijo: trie_buscar solo devuelve 1 si fin_palabra está activo en el nodo final; trie_prefijo solo verifica que el camino exista.
No usar calloc o no inicializar los punteros de hijos a NULL: si quedan con valores basura, las comparaciones if (!cur->hijos[idx]) son incorrectas.
No manejar caracteres fuera del alfabeto soportado: un carácter como 'Z' (mayúscula) da un índice negativo y corrompe la memoria. Hay que validar la entrada.
No liberar el trie al final: cada nodo es un malloc/calloc independiente; hay que recorrer en postorden para liberarlos todos.

Aplicación práctica

Los tries se usan en autocompletado (buscadores, IDEs), corrección ortográfica, compresión de datos (LZW), enrutamiento IP con prefijos CIDR y en la implementación de diccionarios con búsqueda por prefijo.

Siguiente ejercicio recomendado

Práctica guiada y libro completo

Si quieres una ruta completa con progresión real de dificultad:

FAQ

¿Cuánta memoria consume un trie?

Cada nodo almacena 26 punteros (con el alfabeto a-z), lo que consume 26 × 8 = 208 bytes en sistemas de 64 bits más el campo fin_palabra. Para vocabularios pequeños esto puede ser ineficiente; la alternativa es el trie compacto (Patricia/Radix trie) que comprime los caminos sin bifurcaciones.

¿Por qué el trie es más rápido que una tabla hash para búsquedas por prefijo?

Una tabla hash requiere buscar cada clave individualmente para verificar si comienza con un prefijo dado. El trie lo resuelve en O(m) sin recorrer toda la estructura: basta con seguir el camino del prefijo y verificar si existe al menos un descendiente.

¿Se puede usar el trie para cadenas Unicode?

Sí, pero el tamaño del array de hijos debe aumentar (o usar un mapa hijo-→-nodo como tabla hash o árbol binario de búsqueda) para cubrir todos los posibles puntos de código. La implementación más práctica con Unicode es el trie con mapa de dispersión en cada nodo.