time-complexity - 三叉搜索树和二叉搜索树哪个更快？

Question

三叉搜索树需要 O(log(n)+k) 比较，其中 n 是字符串数，k 是要搜索的字符串的长度，二叉搜索树需要 log(n) 比较，那么为什么 TST 比 BST 快？

Answer 1

三元搜索树是专门为存储字符串而设计的，因此我们的分析需要考虑到存储的每个项目都是一个具有一定长度的字符串。假设数据结构中最长的字符串长度为 L，总共有 n 个字符串。

您是正确的，二叉搜索树在进行查找时仅进行 O(log n) 比较。但是，由于存储在树中的项目都是字符串，因此每次比较都需要 O(L) 时间才能完成。因此，在这种情况下，使用二叉搜索树进行搜索的实际运行时间将是 O(L log n)，因为有 O(log n) 次比较，每次花费 O(L) 时间。

现在，让我们考虑一个三元搜索树。使用标准 TST 实现，对于要查找的输入字符串的每个字符，我们执行 BST 查找以找到要下降到的树。这需要时间 O(log n)，我们执行 L 次，总运行时间为 O(L log n)，与 BST 查找时间相匹配。但是，您实际上可以通过将三叉搜索树中的标准 BST 替换为权重平衡树来改进这一点，其权重由每个子树中的字符串数给出，可以使用更仔细的分析来显示总运行时间查找将是 O(L + log n)，这比标准 BST 查找要快得多。

希望这可以帮助！

Answer 2

因为在三进制情况下它是 log ₃ (n)，而在二进制情况下它是 log ₂ (n)。