trie树

trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,通常是字符串

读音:发明者读"tree",但是容易混淆,所以大多数作者都读"try",推荐"try"

Trie 树最有优势的是查找前缀匹配的字符串,比如搜索引擎中的关键词提示功能这个场景,就比较适合用它来解决,也是 Trie 树比较经典的应用场景


假设有5个字符串,code,cook,five,file,fat,他们在 trie 树中式这样存储的


特点:

1.根节点不包含字符,除根节点外每一个节点都只包含一个字符

2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串

3.每个节点的所有子节点包含的字符都不相同

搜索情况:

1.当用户输入c,此时前缀为c,我们通过查询trie树,返回 code,cook

2.当用户继续输入o,此时前缀为co,我们通过查询trie树,返回 code,cook

3.当用户继续输入o,此时前缀为coo,我们通过查询trie树,返回cook


trie树实际上是一个确定有限状态自动机(DFA),通常用转移矩阵表示。行表示状态,列表示输入字符,(行,列)位置表示转移状态。这种方式的查询效率很高,但由于稀疏的现象严重,空间利用效率很低。

假设每个节点只存储26个小写字母的其中一个,那么每个节点都要额外占用26个字节空间不管后面有几种可能

struct node
{
    char chr;
    struct node *edges[26];
};

也可以采用压缩的存储方式即链表来表示状态转移,但由于要线性查询,会造成效率低下


于是人们提出了下面两种结构 三数组Trie(Tripple-Array Trie)二数组Trie(Double-Array Trie),具体实现可以参考 An Implementation of Double-Array Trie

动态的插入删除查询可以参考 【动画】看动画轻松理解「Trie树」


上一篇: B树和B+树
下一篇: 散列表
作者邮箱: 203328517@qq.com