首页 > 代码库 > 字典树

字典树

字典树

字典树又叫tire树,是个简单但是非常实用的数据结构,通常用于字符串的处理或者字典查询。本质上,Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符,这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串。和普通树不同的地方是,相同的字符串前缀共享同一条分支。还是例子最清楚。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:

技术分享

从图中可以看出:

  • 每条边代表一个字符
  • 每个节点对应一项前缀。叶节点前缀最长,即一个单词本身。
  • 单词inn和int共享单词前缀in,因此他们共享左边的一条分支为root->i->in。‘a‘系列的分支同理。
  •  查询也非常简单。比如要查找int顺着从根节点root找下来就好了,root->i->in->int。
  • 搭建Trie的基本算法也很简单,无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在,就共享,否则创建对应的节点和边。比如要插入单词add,就有下面几步:
    1. 先从根节点出发,然后是字符‘a‘,发现字符‘a‘已经存在,那么共享。
    2. 再到‘d‘,又发现‘d‘也已经存在,共享。
    3. 再从‘ad‘向后再找一个‘d‘,发现不再存在,这时建一条边,从‘ad‘连向‘d‘构成‘add‘。(建议用指针写,省点空间)

 

字典树