Количество узлов Trie, необходимых для представления определенного количества строк

Question

Я должен реализовать структуру данных Trie для представления словаря. В словаре содержится 1000 слов (строчных букв), и каждое из них имеет длину в диапазоне от 1 до 10. Мне не разрешается динамически выделять память, что означает, что я должен заранее объявить необходимое количество узлов Trie. Будет ли очень полезно, если какой-либо орган может предложить какую-либо формулировку относительно необходимого количества узлов для 1000 слов в худшем случае? (1000 * 10 не является ответом, его можно минимизировать)

Я могу рассчитать несколько слов, скажем, 10 или 20, но я не могу их формализовать.

Answer 1

Абсолютный наихудший случай - это три, где все слова имеют максимальный размер, и вы максимально запрещаете совместное использование префиксов.

Если предположить строчные буквы алфавита, все слова могут иметь следующую форму:

[a-z][a-z][a-z]aaaaaaa

с частями [az], уникальными для каждого слова. Нам нужен трехбуквенный префикс, потому что 26^2 < 1000 < 26^3

Тогда у нас будет следующий формат размещения:

• На первом уровне все 26 узлов заполнены (= 26 узлов)
• На втором уровне каждый узел первого уровня имеет 26 дочерних элементов (= 676 узлов)
• На третьем уровне будет существовать 1000 узлов, поскольку у нас есть 1000 слов (= 1000 узлов)
• Каждый из этих 1000 узлов будет иметь строку из 7 'a' узлов под ним (= 7000 узлов)

В итоге получается 26 + 676 + 1000 + 7000 =8702 узла.