[关闭]
@markheng 2018-03-17T21:00:06.000000Z 字数 1316 阅读 1773

Trie 前缀树

算法

什么是前缀树

Trie的重要特点是某一节点的后代都含有相同的前缀，因此叫做前缀树。

代码表示前缀树

  1. 数组法 如果字符仅有26个字母组成，那么每个节点申请26长度的数组，足够记录所有的情况，访问很快，但是会导致内存浪费。
  2. hashmap 克服了内存浪费的问题，扩展性也好一点，会慢一些

向前缀树插入结点

思路很直接，遍历字符串的字母的同时，也从树根沿路径前进，没有节点表示当前为止的字符串时，就插入新的结点，伪码如下：

  1. Initialize: cur = root
  2. for each char c in target string S:
  3.     if cur does not have a child c:
  4.         cur.children[c] = new Trie node
  5.     cur = cur.children[c]
  6. cur is the node which represents the string S

一定要注意根节点的初始化

前缀树的搜索

搜索前缀
也很直接的思路，按照目标字符串的每个字符在树中搜索，搜索不能进行下去则表示搜索失败，否则认为搜索成功，一直进行此过程直到搜索到根节点。

  1. Initialize: cur = root
  2. for each char c in target string S:
  3.     if cur does not have a child c:
  4.         search fails
  5.     cur = cur.children[c]
  6. search success

搜索单词
与搜索前缀的方法相同，只是在搜索到最终目标结点之后需要判断是否到达了树的最下层子节点。

题目

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注