No momento, estou implementando uma árvore de raiz / patricia trie (como você quiser chamar). Eu quero usá-lo para pesquisas de prefixo em um dicionário em uma peça de hardware severamente insuficiente. Deveria funcionar mais ou menos como o preenchimento automático, i. e mostrando uma lista de palavras com as quais o prefixo digitado correspond

A minha implementação é baseada neste artigo, mas o código não inclui pesquisas de prefixo, embora o autor diga:

[...] Digamos que você queira enumerar todos os nós que possuem chaves com um prefixo comum "AB". Você pode realizar uma primeira pesquisa profunda começando nessa raiz, parando sempre que encontrar as arestas traseira

Mas não vejo como isso deve funcionar. Por exemplo, se eu construir uma árvore de raiz com estas palavras:

doenç
imaginári
imaginaçã
Imagin
imitaçã
imediat
imediatament
imens
dentr

Receberei exatamente a mesma "melhor correspondência" para os prefixos "i" e "in", de modo que me parece difícil reunir todas as palavras correspondentes apenas atravessando a árvore dessa melhor correspondênci

Adicionalmente, existe ummplementação de árvore @radix em Java que possui uma pesquisa de prefixo implementada em RadixTreeImpl.java. Esse código verifica explicitamente todos os nós (a partir de um determinado nó) em busca de uma correspondência de prefixo - na verdade, compara byte

Alguém pode me indicar uma descrição detalhada da implementação de uma pesquisa de prefixo em árvores de raiz? O algoritmo usado na implementação Java é a única maneira de fazer isso?