Trie树(字典树)

算法

Trie树是一种特殊的前缀树结构,常用于字符串检索和匹配。每个节点代表一个字符,从根节点到任意节点的路径表示一个字符串。它特别适合用于实现字典查找、自动补全和拼写检查等功能。

算法讲解

Trie树

介绍

Trie树,也称为前缀树或字典树,是一种树形数据结构,专门用于高效存储和检索字符串集合。Trie这个名字来源于"retrieval"(检索)一词,反映了它的主要用途。

在Trie树中,每个节点代表一个字符,从根节点到某一节点的路径上经过的字符连接起来,就是该节点对应的字符串。Trie树的关键特点是,所有拥有相同前缀的字符串,在树中共享这个前缀的存储空间。

核心特性

  1. 前缀共享: 具有相同前缀的字符串在Trie树中共享存储空间,大大节省了内存
  2. 快速查找: 查找一个长度为k的字符串的时间复杂度为O(k),与Trie树中存储的字符串总数无关
  3. 词汇关联: 通过前缀可以轻松找到所有具有该前缀的单词
  4. 有序性: Trie树天然地保持了字典序

基本操作

Trie树支持以下基本操作:

  1. 插入(Insert): 将一个字符串添加到Trie树中
  2. 查找(Search): 检查一个完整的字符串是否存在于Trie树中
  3. 前缀查找(StartsWith): 检查Trie树中是否有以给定前缀开头的字符串
  4. 删除(Delete): 从Trie树中删除一个字符串(相对复杂)

基础实现

代码实现

Java

▼
Java
复制代码
class Trie { private TrieNode root; // Trie树的节点结构 class TrieNode { // 子节点,使用数组实现(假设只包含小写字母a-z) private TrieNode[] children; // 标记该节点是否为某个单词的结尾 private boolean isEndOfWord; public TrieNode() { children = new TrieNode[26]; // 26个英文字母 isEndOfWord = false; } } /** 初始化Trie树 */ public Trie() { root = new TrieNode(); } /** 向Trie树中插入单词 */ public void insert(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; // 将字符转换为索引 // 如果当前字符的节点不存在,创建一个新节点 if (current.children[index] == null) { current.children[index] = new TrieNode(); } // 移动到下一个节点 current = current.children[index]; } // 标记单词结束 current.isEndOfWord = true; } /** 查找Trie树中是否存在完整单词 */ public boolean search(String word) { TrieNode node = searchPrefix(word); // 节点存在且是单词结尾 return node != null && node.isEndOfWord; } /** 查找Trie树中是否存在指定前缀 */ public boolean startsWith(String prefix) { // 只需要节点存在即可 return searchPrefix(prefix) != null; } /** 查找前缀对应的节点 */ private TrieNode searchPrefix(String prefix) { TrieNode current = root; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; // 如果当前字符的节点不存在,返回null if (current.children[index] == null) { return null; } current = current.children[index]; } return current; } /** 从Trie树中删除单词(较复杂的操作) */ public void delete(String word) { delete(root, word, 0); } private boolean delete(TrieNode current, String word, int index) { // 已经处理完所有字符 if (index == word.length()) { // 如果不是单词结尾,单词不存在 if (!current.isEndOfWord) { return false; } // 取消标记单词结尾 current.isEndOfWord = false; // 如果节点没有子节点,可以删除 return hasNoChildren(current); } char ch = word.charAt(index); int childIndex = ch - 'a'; TrieNode child = current.children[childIndex]; // 如果字符对应的节点不存在,单词不存在 if (child == null) { return false; } // 递归删除子节点 boolean shouldDeleteChild = delete(child, word, index + 1); // 如果子节点应该被删除 if (shouldDeleteChild) { current.children[childIndex] = null; // 如果当前节点不是单词结尾且没有其他子节点,则它也可以被删除 return !current.isEndOfWord && hasNoChildren(current); } return false; } private boolean hasNoChildren(TrieNode node) { for (TrieNode child : node.children) { if (child != null) { return false; } } return true; } }

JavaScript

▼
Javascript
复制代码
class TrieNode { constructor() { // 子节点,使用对象实现(JS中没有固定大小的数组) this.children = {}; // 标记该节点是否为某个单词的结尾 this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } /** 向Trie树中插入单词 */ insert(word) { let current = this.root; for (let i = 0; i < word.length; i++) { const ch = word[i]; // 如果当前字符的节点不存在,创建一个新节点 if (!current.children[ch]) { current.children[ch] = new TrieNode(); } // 移动到下一个节点 current = current.children[ch]; } // 标记单词结束 current.isEndOfWord = true; } /** 查找Trie树中是否存在完整单词 */ search(word) { const node = this.searchPrefix(word); // 节点存在且是单词结尾 return node !== null && node.isEndOfWord; } /** 查找Trie树中是否存在指定前缀 */ startsWith(prefix) { // 只需要节点存在即可 return this.searchPrefix(prefix) !== null; } /** 查找前缀对应的节点 */ searchPrefix(prefix) { let current = this.root; for (let i = 0; i < prefix.length; i++) { const ch = prefix[i]; // 如果当前字符的节点不存在,返回null if (!current.children[ch]) { return null; } current = current.children[ch]; } return current; } /** 从Trie树中删除单词 */ delete(word) { return this.deleteHelper(this.root, word, 0); } deleteHelper(current, word, index) { // 已经处理完所有字符 if (index === word.length) { // 如果不是单词结尾,单词不存在 if (!current.isEndOfWord) { return false; } // 取消标记单词结尾 current.isEndOfWord = false; // 如果节点没有子节点,可以删除 return this.hasNoChildren(current); } const ch = word[index]; const child = current.children[ch]; // 如果字符对应的节点不存在,单词不存在 if (!child) { return false; } // 递归删除子节点 const shouldDeleteChild = this.deleteHelper(child, word, index + 1); // 如果子节点应该被删除 if (shouldDeleteChild) { delete current.children[ch]; // 如果当前节点不是单词结尾且没有其他子节点,则它也可以被删除 return !current.isEndOfWord && this.hasNoChildren(current); } return false; } hasNoChildren(node) { return Object.keys(node.children).length === 0; } }

Python

▼
Python
复制代码
class TrieNode: def __init__(self): # 子节点,使用字典实现 self.children = {} # 标记该节点是否为某个单词的结尾 self.is_end_of_word = False class Trie: def __init__(self): """初始化Trie树""" self.root = TrieNode() def insert(self, word): """向Trie树中插入单词""" current = self.root for ch in word: # 如果当前字符的节点不存在,创建一个新节点 if ch not in current.children: current.children[ch] = TrieNode() # 移动到下一个节点 current = current.children[ch] # 标记单词结束 current.is_end_of_word = True def search(self, word): """查找Trie树中是否存在完整单词""" node = self._search_prefix(word) # 节点存在且是单词结尾 return node is not None and node.is_end_of_word def starts_with(self, prefix): """查找Trie树中是否存在指定前缀""" # 只需要节点存在即可 return self._search_prefix(prefix) is not None def _search_prefix(self, prefix): """查找前缀对应的节点""" current = self.root for ch in prefix: # 如果当前字符的节点不存在,返回None if ch not in current.children: return None current = current.children[ch] return current def delete(self, word): """从Trie树中删除单词""" self._delete(self.root, word, 0) def _delete(self, current, word, index): # 已经处理完所有字符 if index == len(word): # 如果不是单词结尾,单词不存在 if not current.is_end_of_word: return False # 取消标记单词结尾 current.is_end_of_word = False # 如果节点没有子节点,可以删除 return self._has_no_children(current) ch = word[index] # 如果字符对应的节点不存在,单词不存在 if ch not in current.children: return False child = current.children[ch] # 递归删除子节点 should_delete_child = self._delete(child, word, index + 1) # 如果子节点应该被删除 if should_delete_child: del current.children[ch] # 如果当前节点不是单词结尾且没有其他子节点,则它也可以被删除 return not current.is_end_of_word and self._has_no_children(current) return False def _has_no_children(self, node): """检查节点是否没有子节点""" return len(node.children) == 0

Go

▼
Go
复制代码
package trie // TrieNode 表示Trie树中的节点 type TrieNode struct { // 子节点,使用map实现 Children map[rune]*TrieNode // 标记该节点是否为某个单词的结尾 IsEndOfWord bool } // Trie 表示前缀树数据结构 type Trie struct { Root *TrieNode } // NewTrie 创建一个新的Trie树 func NewTrie() *Trie { return &Trie{ Root: &TrieNode{ Children: make(map[rune]*TrieNode), IsEndOfWord: false, }, } } // Insert 向Trie树中插入单词 func (t *Trie) Insert(word string) { current := t.Root for _, ch := range word { // 如果当前字符的节点不存在,创建一个新节点 if _, exists := current.Children[ch]; !exists { current.Children[ch] = &TrieNode{ Children: make(map[rune]*TrieNode), IsEndOfWord: false, } } // 移动到下一个节点 current = current.Children[ch] } // 标记单词结束 current.IsEndOfWord = true } // Search 查找Trie树中是否存在完整单词 func (t *Trie) Search(word string) bool { node := t.searchPrefix(word) // 节点存在且是单词结尾 return node != nil && node.IsEndOfWord } // StartsWith 查找Trie树中是否存在指定前缀 func (t *Trie) StartsWith(prefix string) bool { // 只需要节点存在即可 return t.searchPrefix(prefix) != nil } // searchPrefix 查找前缀对应的节点 func (t *Trie) searchPrefix(prefix string) *TrieNode { current := t.Root for _, ch := range prefix { // 如果当前字符的节点不存在,返回nil if _, exists := current.Children[ch]; !exists { return nil } current = current.Children[ch] } return current } // Delete 从Trie树中删除单词 func (t *Trie) Delete(word string) bool { return t.delete(t.Root, []rune(word), 0) } // delete 递归删除单词的辅助函数 func (t *Trie) delete(current *TrieNode, word []rune, index int) bool { // 已经处理完所有字符 if index == len(word) { // 如果不是单词结尾,单词不存在 if !current.IsEndOfWord { return false } // 取消标记单词结尾 current.IsEndOfWord = false // 如果节点没有子节点,可以删除 return len(current.Children) == 0 } ch := word[index] // 如果字符对应的节点不存在,单词不存在 child, exists := current.Children[ch] if !exists { return false } // 递归删除子节点 shouldDeleteChild := t.delete(child, word, index+1) // 如果子节点应该被删除 if shouldDeleteChild { delete(current.Children, ch) // 如果当前节点不是单词结尾且没有其他子节点,则它也可以被删除 return !current.IsEndOfWord && len(current.Children) == 0 } return false }

C++

▼
C++
复制代码
#include <string> #include <unordered_map> class Trie { private: // Trie树的节点结构 struct TrieNode { // 子节点,使用unordered_map实现 std::unordered_map<char, TrieNode*> children; // 标记该节点是否为某个单词的结尾 bool isEndOfWord; TrieNode() : isEndOfWord(false) {} // 析构函数,释放所有子节点的内存 ~TrieNode() { for (auto& pair : children) { delete pair.second; } } }; TrieNode* root; // 查找前缀对应的节点 TrieNode* searchPrefix(const std::string& prefix) { TrieNode* current = root; for (char ch : prefix) { auto it = current->children.find(ch); if (it == current->children.end()) { return nullptr; } current = it->second; } return current; } // 从Trie树中删除单词(递归辅助函数) bool deleteHelper(TrieNode* current, const std::string& word, size_t index) { // 已经处理完所有字符 if (index == word.length()) { // 如果不是单词结尾,单词不存在 if (!current->isEndOfWord) { return false; } // 取消标记单词结尾 current->isEndOfWord = false; // 如果节点没有子节点,可以删除 return current->children.empty(); } char ch = word[index]; auto it = current->children.find(ch); // 如果字符对应的节点不存在,单词不存在 if (it == current->children.end()) { return false; } TrieNode* child = it->second; // 递归删除子节点 bool shouldDeleteChild = deleteHelper(child, word, index + 1); // 如果子节点应该被删除 if (shouldDeleteChild) { delete child; current->children.erase(ch); // 如果当前节点不是单词结尾且没有其他子节点,则它也可以被删除 return !current->isEndOfWord && current->children.empty(); } return false; } public: // 初始化Trie树 Trie() { root = new TrieNode(); } // 析构函数,释放所有节点的内存 ~Trie() { delete root; } // 向Trie树中插入单词 void insert(const std::string& word) { TrieNode* current = root; for (char ch : word) { // 如果当前字符的节点不存在,创建一个新节点 if (current->children.find(ch) == current->children.end()) { current->children[ch] = new TrieNode(); } // 移动到下一个节点 current = current->children[ch]; } // 标记单词结束 current->isEndOfWord = true; } // 查找Trie树中是否存在完整单词 bool search(const std::string& word) { TrieNode* node = searchPrefix(word); // 节点存在且是单词结尾 return node != nullptr && node->isEndOfWord; } // 查找Trie树中是否存在指定前缀 bool startsWith(const std::string& prefix) { // 只需要节点存在即可 return searchPrefix(prefix) != nullptr; } // 从Trie树中删除单词 void remove(const std::string& word) { if (!word.empty()) { deleteHelper(root, word, 0); } } };

优缺点

优点

  1. 高效的字符串检索:查找、插入和删除操作的时间复杂度与字符串长度成正比(O(k)),而与存储的字符串总数无关
  2. 节省空间:通过共享前缀,减少了重复存储
  3. 支持按字典序遍历:可以方便地按字典序输出所有字符串
  4. 前缀匹配高效:特别适合前缀查询和自动补全功能

缺点

  1. 内存消耗:对于不共享前缀的字符串集合,Trie树可能消耗大量内存
  2. 空间复杂度高:每个节点需要存储所有可能字符的引用(如上例中每个节点存储26个子节点引用)
  3. 不适合单次查询:如果只需要进行单次的精确字符串查询,哈希表可能是更好的选择
  4. 实现较为复杂:特别是删除操作,需要额外的逻辑来处理节点的清理

应用场景

  • 自动补全和拼写检查:当用户在搜索框中输入时,Trie树可以快速找到所有以当前输入为前缀的单词,提供智能提示。输入法和文本编辑器通常利用这一特性实现单词补全功能。
  • IP路由表:网络路由器使用类似Trie的结构来存储IP地址,实现高效的最长前缀匹配。
  • 字典和词汇表:电子字典应用可以使用Trie树来存储词汇,支持快速查找和前缀搜索。
  • 文本分析:在自然语言处理中,Trie树可以用于单词频率统计、关键词提取等任务。
  • 电话号码簿:通讯录应用可以使用Trie树来存储联系人信息,支持按号码前缀搜索。

测验

1)一个包含10000个单词的Trie树,查找一个长度为15的单词的时间复杂度是多少?为什么?

2)Trie树与哈希表相比,在字符串存储和检索方面有什么优势和劣势?

3)如果要在Trie树中存储的不是26个小写英文字母,而是所有ASCII字符(共128个),应该如何修改Trie节点的实现?这种修改会带来什么问题?

4)描述在Trie树中删除一个单词的过程中可能遇到的复杂情况,以及如何处理这些情况。

测验答案

1)时间复杂度是O(15),即O(k),其中k是单词长度。因为在Trie树中查找一个单词的时间复杂度只与单词长度有关,与树中存储的单词总数无关。查找过程就是沿着单词的每个字符在树中遍历,共需要15步。

2)

  • 优势:Trie树支持按前缀查找;保持字符串的有序性;对于有共同前缀的字符串集合更节省空间;查找时间与字符串总数无关。
  • 劣势:Trie树的空间消耗可能较大,特别是当字符集较大时;实现更复杂;对于单次精确查询,哈希表通常更快。

3)需要将TrieNode类中的children数组大小从26改为128,即children = new TrieNode[128],并且修改索引计算逻辑为int index = ch,不再需要减去'a'。这种修改会使每个节点占用更多内存,因为即使只用到少数几个字符,每个节点仍需要为所有128个可能的字符分配空间,导致内存使用效率降低。

4)

  • 要删除的单词是另一个单词的前缀:这种情况下,只需将该单词的终止标记设为false,而不删除任何节点。
  • 要删除的单词包含其他单词的前缀:需要仅删除不影响其他单词的节点。删除应从单词末尾向上进行,当遇到被标记为单词结尾的节点或有多个子节点的节点时停止。
  • 需要使用递归或自底向上的方法,确保只删除不再需要的节点,保留其他单词所需的节点。

相关的LeetCode热门题目

  1. 208. 实现 Trie (前缀树) - 基础题,要求实现Trie树的基本操作。
  2. 211. 添加与搜索单词 - 数据结构设计 - 在基本Trie的基础上增加了通配符匹配功能。
  3. 212. 单词搜索 II - 使用Trie树优化在二维字符网格中搜索单词的过程。
  4. 648. 单词替换 - 使用Trie树查找词根并替换单词。
  5. 1032. 字符流 - 设计一个数据结构,支持对字符流的查询,判断最近添加的字符是否形成了给定单词集合中的某个单词的后缀。