likes
comments
collection
share

前缀树🌳

作者站长头像
站长
· 阅读数 16

前缀树是什么

前缀树，也称为 Trie 树或字典树，是一种基于字符串的数据结构。它可以有效地支持诸如前缀匹配等操作，非常适合存储和查找字符串集合。

前缀树的基本思想是将每个字符串分解为其字符的序列，并将这些字符序列插入到一棵树中。每个节点表示一个字符串的前缀，根节点代表空串。从根节点开始，每个节点的子节点表示在当前节点代表的前缀上添加一个字符后得到的新前缀。在每个叶子节点处存储一个完整的字符串。因此，从根节点到任何一个叶子节点的路径都代表一个字符串。

前缀树的优点在于它可以支持高效的前缀匹配操作。通过沿着前缀树上的路径遍历，可以找到与给定前缀匹配的所有字符串。此外，前缀树还可以有效地支持字符串的插入、删除和查找操作。

然而，前缀树的缺点在于其空间复杂度比较高，因为每个节点都可能有多个子节点，即每个节点可能代表多个字符串前缀。此外，在某些情况下，前缀树可能不如其他数据结构（如哈希表或有序列表）效率高。

借用剑指offer里边的一张图直观地解释一下：

前缀树🌳

实现 Trie (前缀树)

208. 实现 Trie (前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

 

示例：

输入

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出

[null, null, true, false, true, null, true]

解释 Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // 返回 True

trie.search("app"); // 返回 False

trie.startsWith("app"); // 返回 True

trie.insert("app");

trie.search("app"); // 返回 True

 

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
class TrieNode:
    def __init__(self):
        self.isWord = False
        self.children = {}
class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.isWord = True

    def search(self, word: str) -> bool:
        node  = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.isWord

    def startsWith(self, prefix: str) -> bool:
        node  = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

这是一个使用Python实现的基本的前缀树（Trie树）数据结构。代码中包含两个类：TrieNode和Trie。

  • TrieNode类代表树中的一个节点，每个节点包含一个标志位isWord和一个子节点字典children。如果isWord为True，则表示该节点是一个单词的结尾。

  • Trie类是一个包含根节点的前缀树。它包含三个方法：insert、search和startsWith。其中insert方法用于将单词插入到前缀树中，search方法用于查找一个单词是否存在于前缀树中，startsWith方法用于查找前缀是否存在于前缀树中。

    • 在insert方法中，我们从根节点开始遍历每个字符，如果在子节点中不存在该字符，则创建一个新的节点，并将其添加到子节点字典中。如果已经存在该字符的节点，则继续遍历下一个字符。在遍历完整个单词后，我们将最后一个节点的isWord标志设置为True，以表示该节点是一个单词的结尾。

    • 在search方法中，我们也从根节点开始遍历每个字符，如果在子节点中不存在该字符，则返回False。如果已经存在该字符的节点，则继续遍历下一个字符。在遍历完整个单词后，如果最后一个节点的isWord标志为True，则表示单词存在于前缀树中，返回True，否则返回False。

    • 在startsWith方法中，我们使用与search方法相同的方法遍历前缀中的每个字符。如果遍历完整个前缀后都能在前缀树中找到对应的节点，则返回True，否则返回False。

这里是使用字典实现的，没使用list。

使用字典和使用列表实现前缀树在时间和空间复杂度上有一些区别。

使用字典实现前缀树的优点是：

  • 访问节点的子节点的时间复杂度为O(1)。由于字典是通过哈希表实现的，因此查找子节点的时间与字典大小无关。
  • 可以使用Python的内置字典类型，无需额外实现。
  • 空间效率较高。由于只有在需要时才会创建新的节点，因此空间占用相对较小。

使用列表实现前缀树的优点是：

  • 实现相对简单。使用列表时，每个节点仅包含一个列表，其中存储了其子节点。这使得实现相对简单，易于理解。
  • 适用于具有固定字母表大小的语言。由于使用列表实现的前缀树需要为每个节点维护一个固定大小的数组，因此它对于具有固定字母表大小的语言（例如英语）可能更有效。

总的来说，使用字典实现前缀树是一种更通用和高效的方法，特别是对于任意大小的字母表和变化的数据集。然而，使用列表实现前缀树在某些情况下可能更适合，特别是对于具有固定字母表大小的语言。

其他相关题目

211. 添加与搜索单词 - 数据结构设计

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

  • WordDictionary() 初始化词典对象
  • void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
  • bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

 

示例：

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

 

提示：

  • 1 <= word.length <= 25
  • addWord 中的 word 由小写英文字母组成
  • search 中的 word 由 '.' 或小写英文字母组成
  • 最多调用 104 次 addWord 和 search
class WordDictionary:

    def __init__(self):
        self.isWord = False
        self.children = {}

    def addWord(self, word: str) -> None:
        node = self
        for c in word:
            if c not in node.children:
                node.children[c] = WordDictionary()
            node = node.children[c]
        node.isWord = True

    def search(self, word: str) -> bool:
        node = self
        n = len(word)

        def dfs(root, i):
            if i == n:
                return root.isWord
            if word[i] == '.':
                for c in root.children:
                    if dfs(root.children[c], i + 1):
                        return True
            else:
                if word[i] in root.children:
                    root = root.children[word[i]]
                    if dfs(root, i + 1):
                        return True
            return False

        return dfs(node, 0)

前缀树🌳