Решал я такую задачку: есть строка набранная в манере T9 - типа "233 364", которое расшифровывается как "bad dog" (2 = abc, 3 = def ... как клавиши на телефоне). Есть словарь, в котором даны слова и частоты их встречаемости. Частоты нужны на случай, если подойдет несколько слов (223 может быть dog или add) - тогда выбирается наиболее часто встречающееся. Я делал прогу, которая читает строку T9 и превращает ее в нормальный текст. Алгоритм выбрал простой: разбиваем строку на слова, читаем слово - его отыскиваем в словаре. Чтобы поиск по словарю был быстрым я сделал из него дерево. Например слово add в нем будет размещено так: root -> 2 -> 3 -> 3 , цифры - это номера клавиш для букв: первая буква (Add) - 2, вторая (aDd) - 3, третья (adD) снова 3. В том же узле 2->3->3 где висит слово add, висит и слово bad и другие слова, которые подходят под описание 233. Имея такое дерево, можно очень быстро найти список вариантов для любой комбинации (тем более, что в слове не больше 20 букв). Надо сказать, что до этого я пробовал брутфорс для поиска в словаре подходящих комбинаций: время на обработку словаря нулевое, но поиск был слишком долгим на больших строках - программа конкурсная, строка могла содержать до 100000 символов, а уложиться надо было в лимит 1.5 секунд. Построение дерева закономерно дало огромный выигрыш во времени поиска, но возникла другая проблема - теперь программа выходила за лимит при больших объемах словаря: я так понял, дерево потому что долго строилось. Дерево я строил рекурсивно, в виде связанных списков, код рекурсивной функции внизу. И как ускорить алгоритм его построения я не знаю. Может кто знает способы?

речь не о буквах - о цифрах, верно?
тогда на каждом уровне вместо перебора братьев можно использовать массив из 10 элементов-указателей. вместо перебора - выбор по индексу плюс проверка на NULL.
правда, не думаю, что сильно ускорит процесс :(

да, и правда, поддеревьев не будет больше 10, так что можно упростить структуру и ограничиться массивом. Думаю это даст выигрыш неплохой - попробую и расскажу.