дерево или сбалансированное двоичное дерево поиска для хранения словаря?

У меня есть простое требование (возможно, гипотетическое):

Я хочу сохранить словарь английских слов (n слов) и, учитывая слово (длина символа m), словарь может определить, если слово существует в словаре или нет. Какой была бы подходящая структура данных для этого?

сбалансированное двоичное дерево поиска? как это сделано в ассоциативных структурах данных C ++ STL, таких как set, map

или

a trie on strings

Некоторый анализ сложности: в сбалансированном bst время будет (log n) * m (сравнение двух строк занимает O (m) символ за символом)

in trie, если на каждом узле мы могли бы разветвляться за время O (1), мы можем найти, используя O (m), но предположение, что в каждом узле мы можем разветвляться за время O (1), неверно. на каждом узле максимальное количество возможных ветвей будет 26. если мы хотим O (1) в узле, мы сохраним короткий массив, индексируемый по символам в каждом узле. Это взорвет пространство. После нескольких уровней в дереве ветвление уменьшится, поэтому лучше сохранить связанный список символов и указателей следующего узла.

что выглядит более практичным? любые другие компромиссы?

Спасибо,