文件名称：tst:自动完成前缀树（三元搜索树）
文件大小：4KB
文件格式：ZIP
更新时间：2024-07-13 20:59:47
Python
测试 称为“三元搜索树”(TST) 的不太简单的 trie 实现对于存储字符串的前缀很有用。 当您在字母表上存储单词的正确分布时，TST 最合适。 好处 比简单的 trie 实现更高效的内存。 在 TST 中，公共前缀以更智能的方式存储，除非元素的插入顺序创建了退化的 TST（例如，当它基本上看起来像一个链表时） 前缀的合适搜索时间：O(klogn) 其中k是单词的长度， n是树的高度（稍后，我将给出每个方法的运行时分析） 部分匹配、近似匹配、近邻查找、 缺点 搜索比 naive trie 慢（naive trie 搜索时间总是 O（单词长度）） 根据设计，我们为每个字符串中的每个字符使用一个完整节点——因此对于许多插入，内存使用量可能会急剧上升，尤其是当超过一半的节点没有公共前缀时 简洁树或紧凑前缀树对此进行改进，IIRC 的搜索时间略快（如果我错了，请纠正我） 如果我们试图
【文件预览】：
tst-master
----ternarysearchtree.py(4KB)
----test_tst.py(2KB)
----README.md(3KB)