algorithm - 将尝试扩展到更多的叶子

Question

我必须使用尝试制作字典，字母表中的字母数将从 26 增加到 120，因此叶节点的数量将成倍增加。我可以使用哪些优化来使我的查找、插入和删除时间不会成倍增加？

编辑 使问题更清楚，抱歉缺少细节我正在使用像基数树这样的多路特里树并对其进行一些修改。我的问题是，如果我知道单词大小（肯定）会从 26 增加到 120，它会增加树的深度。是否可以通过将密钥增加到 64 位以上来减少深度的增加（寄存器最多可以达到 64 位）？

Answer 1

根据密钥的二进制表示，使用带有路径压缩的二进制尝试（Patricia 尝试）通常会更好。这样您就可以获得尽可能小的字母表的好处，并且每个键仍然只有 2 个节点（一个叶子节点和一个内部节点）。

Answer 2

虽然可能会有一些优化，但我们的查找、插入和删除时间不会成倍增加。增加您的字母集仅意味着您的每个 trie 节点现在会更大。每个单词的路径仍然具有与单词中的字母相同的长度。