Trie树是一种特殊的前缀树结构,常用于字符串检索和匹配。每个节点代表一个字符,从根节点到任意节点的路径表示一个字符串。它特别适合用于实现字典查找、自动补全和拼写检查等功能。
Trie树,也称为前缀树或字典树,是一种树形数据结构,专门用于高效存储和检索字符串集合。Trie这个名字来源于"retrieval"(检索)一词,反映了它的主要用途。
在Trie树中,每个节点代表一个字符,从根节点到某一节点的路径上经过的字符连接起来,就是该节点对应的字符串。Trie树的关键特点是,所有拥有相同前缀的字符串,在树中共享这个前缀的存储空间。
Trie树支持以下基本操作:
▼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复制代码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复制代码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复制代码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++复制代码#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)一个包含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,而不删除任何节点。
- 要删除的单词包含其他单词的前缀:需要仅删除不影响其他单词的节点。删除应从单词末尾向上进行,当遇到被标记为单词结尾的节点或有多个子节点的节点时停止。
- 需要使用递归或自底向上的方法,确保只删除不再需要的节点,保留其他单词所需的节点。