我目前正试图了解 Trie 的变化，并想知道是否有人能够澄清几点。（我对这个问题的答案感到很困惑Tries vs ternary search trees for autocomplete?，尤其是在第一段中）。
根据我的阅读，以下内容是否正确？假设我们在数据结构中存储了 n 个元素，L 是我们要搜索的字符串的长度：
Trie 将其键存储在叶节点上，如果我们的搜索结果为正，则意味着它将执行 O(L) 比较。然而，对于未命中的情况，平均性能为 O(log2(n))。
类似地，基数树（R = 2^r）将键存储在叶节点，并将执行 O(L) 比较以获得正命中。然而，未命中会更快，并且平均发生在 O(logR(n)) 中。
三元搜索 Trie 本质上是一个带有操作 <、>、= 的 BST，并且每个节点中都存储了一个字符。我们不比较节点处的整个密钥（与 BST 一样），而是只比较该节点处密钥的一个字符。总的来说，假设我们的字母大小是 A，那么如果有命中，我们必须（最多）执行 O(L*A) = O(L) 比较。如果没有命中，我们平均有 O(log3(n))。
关于基数树，如果我们的字母表是 {0,1} 并且我们设置 R = 4，对于二进制字符串 0101，我们只需要两次比较，对吧？因此，如果我们的字母表的大小是 A，我们实际上只会执行 L * (A / R) 比较？如果是这样，那么我猜这只是 O(L)，但我很好奇这是否是正确的推理。
感谢大家提供的任何帮助！