13.Trie树的基本实现与特性
2020-08-19 本文已影响0人
一角钱技术
13.Trie树的基本实现与特性
理解字典树之前我们先提出三个问题，后面我们再来回答：
- 字典树的数据结构
- 字典树的核心思想
- 字典树的基本性质
本文是之前的《字典树实现》的一个升级，如果觉得本篇稍繁杂可以去看之前的一篇。
在这里我们也先回忆一下树，树本身定义比较简单，如下图：
如果你看到上图这样的一个层级，你应该马上会想到按层次来打印一颗二叉树，这个题目是非常高频的题目：
102. 二叉树的层序遍历。
那么这里你不记得这个题目或者对写这个代码的话还有一点模糊，你可以去再练习一遍。
同时深度优先搜索和广度优先搜索你应该也需要掌握。这里可以看一下我之前的一遍文章：深度优先搜索和广度优先搜索
二叉搜索树
一提到二叉搜索树你就应该想到是子树的关系，并不是儿子和父亲的关系。那么它的定义就说：任何一个结点，所有的左子树值都比根节点小，所有的右子树值都比根节点大，且对于它的任何子树同样地以此类推。对于任何子树都满足这样的特性，这个就是所谓的二叉搜索树。
另外一个特性：二叉搜索树是一个升序的序列，如果是中序遍历的话（左-根-右）。
那么还有一种情况，在现实中特别常见，但是在二叉搜索树来进行存储的话并不是特别好解决这样的一个实际问题。就是在搜索的时候，当你打来一个字母的前缀或者你中文也类似，比如说你打来一个周杰，一般人可能会觉得是伦，就是周杰伦。同理英文的话就是you的话就有这么多可以感应出来的，像这种所谓的词频的感应或者是由前缀来推后面可能的词语。那么它应该用怎样的数据结构来表示？
字典树（Trie）
1. 基本结构
字典树，即 Tire 树，又称单词查找树或键树，是一种树型结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希高。其核心思想是利用公共前缀来减少查询时间。
2. 基本性质
- 结点本身不存完整单词；
- 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；
- 每个结点的所有子结点路径代表的字符都不相同。
结点存储额外信息
很多时候我们还要统计频次，应该怎么做呢？就会在这里加一个数字，所以这个数字就表示相应到这个结点所代表的单词它的统计的计数就放在这个地方，当然来它的结点上可以存其他的额外的信息，在这个图上只是用数字来举例。这里数字就是这个单词出现的统计频次。而按照统计频次，我们后序就可以给用户做相应的推荐。
结点的内部实现
每个结点的如果是英文的话，那么毫无疑问它就会存到下一个结点去的话，指向下一个结点的不同的指针，这里它存储就不再是用left 和 right 来表示左右结点来，它就直接用相应的字符来指向下一个结点。同时除了小写的 abcdefg... 还有大写的 ABCDEFG... ，同时如果还存在一些特殊符合的话，也可以放这里，所以如果是简单单词的话，同时不分大小写，你可以认为这里是26个分叉，就从 a 分到 z 26个分叉出去，当然你如果要包含大小写或者包括其他的话就更多，同时如果是整个字符串的话，它的 ASCII 域是255，所以是255分叉。一般来说你可以认为是26分叉的一个多叉树。
3. 核心思想
- Trie 树的核心实现是空间换时间。
- 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
实战题目
208. 实现 Trie (前缀树)
Trie 树代码模板
//Java
class Trie {
private boolean isEnd;
private Trie[] next;
/** Initialize your data structure here. */
public Trie() {
isEnd = false;
next = new Trie[26];
}
/** Inserts a word into the trie. */
public void insert(String word) {
if (word == null || word.length() == 0) return;
Trie curr = this;
char[] words = word.toCharArray();
for (int i = 0;i < words.length;i++) {
int n = words[i] - 'a';
if (curr.next[n] == null) curr.next[n] = new Trie();
curr = curr.next[n];
}
curr.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Trie node = searchPrefix(prefix);
return node != null;
}
private Trie searchPrefix(String word) {
Trie node = this;
char[] words = word.toCharArray();
for (int i = 0;i < words.length;i++) {
node = node.next[words[i] - 'a'];
if (node == null) return null;
}
return node;
}
}
# Python
class Trie(object):
def __init__(self):
self.root = {}
self.end_of_word = "#"
def insert(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end_of_word] = self.end_of_word
def search(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.end_of_word in node
def startsWith(self, prefix):
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
//C/C++
class Trie {
struct TrieNode {
map<char, TrieNode*>child_table;
int end;
TrieNode(): end(0) {}
};
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *curr = root;
for (int i = 0; i < word.size(); i++) {
if (curr->child_table.count(word[i]) == 0)
curr->child_table[word[i]] = new TrieNode();
curr = curr->child_table[word[i]];
}
curr->end = 1;
}
/** Returns if the word is in the trie. */
bool search(string word) {
return find(word, 1);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return find(prefix, 0);
}
private:
TrieNode* root;
bool find(string s, int exact_match) {
TrieNode *curr = root;
for (int i = 0; i < s.size(); i++) {
if (curr->child_table.count(s[i]) == 0)
return false;
else
curr = curr->child_table[s[i]];
}
if (exact_match)
return (curr->end) ? true : false;
else
return true;
}
};
// JavaScript
class Trie {
constructor() {
this.root = {};
this.endOfWord = "$";
}
insert(word) {
let node = this.root;
for (let ch of word) {
node[ch] = node[ch] || {};
node = node[ch];
}
node[this.endOfWord] = this.endOfWord;
}
search(word) {
let node = this.root;
for (let ch of word) {
if (!node[ch]) return false;
node = node[ch];
}
return node[this.endOfWord] === this.endOfWord;
}
startsWith(word) {
let node = this.root;
for (let ch of word) {
if (!node[ch]) return false;
node = node[ch];
}
return true;
}
}
let trie = new Trie();
console.log(trie.insert("apple"));
console.log(trie.search("apple")); // 返回 true
console.log(trie.search("app")); // 返回 false
console.log(trie.startsWith("app")); // 返回 true
console.log(trie.insert("app"));
console.log(trie.search("app")); // 返回 true
212. 单词搜索 II
class Solution {
public List<String> findWords(char[][] board, String[] words) {
// 构建字典树
Trie trie = new Trie();
// 插入数据
for (String word : words) {
trie.insert(word);
}
// 构建结果集容器
List<String> result = new LinkedList<>();
// 矩阵行数
int m = board.length;
// 矩阵列数
int n = board[0].length;
// 存储该结点是否访问
boolean[][] visited = new boolean[m][n];
// 遍历整个二维数组
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
find(board, visited, i, j, m, n, result, trie);
}
}
return result;
}
private void find(char[][] board, boolean[][] visited, int i, int j, int m, int n, List<String> result, Trie cur) {
// 边界判断以及是否已经访问判断
if (i < 0 || i >= m || j < 0 || j >=n || visited[i][j]) {
return;
}
// 获取子结点状态，判断其是否又子结点
cur = cur.next[board[i][j] - 'a'];
if (cur == null) return;
// 修改结点状态，防止重复访问
visited[i][j] = true;
// 找到单词加入
if (cur.isEnd) {
result.add(cur.val);
// 找到单词后，修改字典树内叶子结点状态为false，防止出现重复单词
cur.isEnd = false;
}
find(board, visited, i + 1, j, m, n, result, cur);
find(board, visited, i - 1, j, m, n, result, cur);
find(board, visited, i, j + 1, m, n, result, cur);
find(board, visited, i, j - 1, m, n, result, cur);
// 最后修改结点状态为未访问状态
visited[i][j] = false;
}
class Trie {
// 表示是否最后叶子结点
private boolean isEnd;
// 表示字节的
private Trie[] next;
// 存储最后结点的字符串
private String val;
public Trie() {
isEnd = false;
next = new Trie[26];
}
public void insert(String word) {
if (word == null || word.length() == 0) return;
Trie curr = this;
char[] words = word.toCharArray();
for (int i = 0; i < words.length; i++) {
// 判断是否存在该字符的结点，不存在则创建
int n = words[i] - 'a';
if (curr.next[n] == null) {
curr.next[n] = new Trie();
}
curr = curr.next[n];
}
// 遍历结束后，修改叶子结点的状态，并存储字符串
curr.isEnd = true;
curr.val = word;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
Trie node = searchPrefix(prefix);
return node != null;
}
private Trie searchPrefix(String word) {
Trie node = this;
char[] words = word.toCharArray();
for (int i = 0; i < words.length; i++) {
node = node.next[words[i] - 'a'];
if (node == null) return null;
}
return node;
}
}
}
部分图片来源于网络，版权归原作者，侵删。
