Trie
- Trie 树的数据结构
- Trie 树的核⼼心思想
- Trie 树的基本性质
基本结构
Trie 树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应⽤用是⽤用于统计和排序⼤量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统⽤用于⽂文本词频统计。
它的优点是:最⼤限度地减少⽆谓的字符串比较，查询效率⽐哈希表高。
核心思想
Trie 的核心思想是空间换时间。利⽤字符串的公共前缀来降低查询时间的开销以达到提高效率的⽬的。
字典树代码
static final int ALPHABET_SIZE = 256
static class TrieNode {
TrieNode[] children = new TrieNode[ALPHABET_SIZE]
boolean isEndOfWord = false
TrieNode() {
isEndOfWord = false
for (int i = 0; i < ALPHABET_SIZE; i++)
children[i] =null
}
}
class TrieNode:
# Trie node class
def __init__(self):
self.children = [None] * ALPHABET_SIZE
# isEndOfWord is True if node represent
# the end of the word
self.isEndOfWord = False
基本性质
- 根节点不不包含字符，除根节点外每⼀一个节点都只包含⼀一 个字符。
- 从根节点到某⼀一节点，路路径上经过的字符连接起来，为 该节点对应的字符串串。
- 每个节点的所有⼦子节点包含的字符都不不相同。
应用场景
- 搜索框模糊查询
实战题⽬
- https://leetcode.com/problems/implement-trie-prefix-tree/#/description
- https://leetcode.com/problems/word-search-ii/