Actualmente estoy implementando un árbol de raíz / patricia trie (como quieras llamarlo). Quiero usarlo para búsquedas de prefijos en un diccionario en un hardware con poca potencia. Se supone que funciona más o menos como la finalización automática, i. mi. mostrando una lista de palabras que coincide con el prefijo escrito.

Mi implementación se basaen este artículo, pero el código no incluye búsquedas de prefijos, aunque el autor dice:

[...] Digamos que desea enumerar todos los nodos que tienen claves con un prefijo común "AB". Puede realizar una primera búsqueda en profundidad comenzando en esa raíz, deteniéndose cada vez que encuentre bordes traseros.

Pero no veo cómo se supone que debe funcionar. Por ejemplo, si construyo un árbol de raíz a partir de estas palabras:

enfermeda
imaginari
imaginació
imagin
imitació
inmediat
inmediatament
inmens
e

Obtendré exactamente la misma "mejor coincidencia" para los prefijos "i" y "en", de modo que me parece difícil reunir todas las palabras coincidentes simplemente atravesando el árbol de esa mejor coincidencia.

Adicionalmente, hay unmplementación del árbol @radix en Java que tiene una búsqueda de prefijo implementada en RadixTreeImpl.java. Ese código verifica explícitamente todos los nodos (a partir de un determinado nodo) para una coincidencia de prefijo: en realidad compara bytes.

¿Alguien puede señalarme una descripción detallada sobre la implementación de una búsqueda de prefijos en árboles radix? ¿Es el algoritmo utilizado en la implementación de Java la única forma de hacerlo?