Trie 字典树
![Trie 字典树](https://static001.geekbang.org/infoq/14/14c28678c03b9bd99dbb62d6746f5016.png)
基础理论
什么是字典树
为了能够快速的找到一个单词,大佬们提出了一个用空间换时间的数据结构用来存储单词。具体表现为
用一颗树来存储单词
多叉树每一条边代表一个字母,
根到叶子表示一个字符串
最后叶子节点可以存频次信息
图解
![](https://static001.geekbang.org/infoq/14/14c28678c03b9bd99dbb62d6746f5016.png)
比如 我们如何存储but 和 cat 两个单词。
首先我们确定每一个节点:里面有isEnd 和一个指向子节点的数组。长为26(26个字母)。对于每一个字母,如果有单词对应这个字母,就存储一个树节点。否则为空。
典型的字典树运用场景
单词推导, 输入you 自动推导youtube,
代码实现
Tried 的存储结构 树结构boolean isEnd()TreeNode[] children // 一个字母表26长度的数组,如果第i位存在字母,则,下一个字母可以为'a'+i;
Treid 字典树的基本原子操作
构造一个TreeNode 点
public TreeNode() { children = new TreeNode[26];}
判断当前是否包含某这个字母
public boolean containsKey(char ch) { return children[ch - 'a'] != null; }在当前节点 获取char ch,也就是说或者当前节点的字母
public char get(char ch) { return children[ch - 'a']}
在当前节点插入一个node
public void put(char ch, TreeNode node) { children[ch - 'a'] = node; }
将当前点设为终点
public void setEnd() { isEnd = true;}判断当前Node 是不是endpublic boolean isEnd() {return isEnd;}
Tried树的常用操作
增加单词 见代码
查找单词 见代码
查找满足某一给前缀的所有单词 见代码
思维导图
![](https://static001.geekbang.org/infoq/28/288ea470442996cdb1a0f76929d4375b.png)
评论