DSA Interview Prep · 课时

TrieNode 类：插入与搜索

使用子节点字典和 is_end 标志构建 TrieNode，实现插入和精确搜索，并分析每次操作的 O(m) 时间复杂度，其中 m 为单词长度。

TrieNode 类：插入与搜索 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

Trie 是什么

Trie（前缀树）是一种树形数据结构，其中每个节点表示一个字符。单词通过将字符从根节点依次连接到叶节点来存储。根节点表示空字符串。从根节点到 is_end = True 节点的每条路径都拼出了一个已存储的单词。Trie 树非常适合处理基于前缀的查询，例如 autocomplete、拼写检查和 IP 路由；在这些用例中，它的性能优于哈希映射。

TrieNode 类的设计

一个 TrieNode 有两个字段：children——将字符映射到子 TrieNodes 的字典；以及 is_end——用于标记该节点是否是已存储单词结尾的布尔值。使用字典而不是固定的 26 字符数组，可以适用于任意字符集，并节省稀疏 Trie 树的内存。Trie 中的每个节点恰好表示其下方单词中的一个字符位置。

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False  # True if a word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def __repr__(self):
        return f'Trie(root with {len(self.root.children)} children)'

t = Trie()
print(t)  # Trie(root with 0 children)

插入操作

要插入一个单词，请从根节点开始遍历：对于当前节点的 children 中尚不存在的每个字符，都创建一个新的 TrieNode。处理完所有字符后，在最后一个节点上设置 is_end = True。插入 'apple' 和 'app' 会创建 a→p→p→l→e 这一链条（'apple' 的结尾节点将 is_end 标记为真），其中第 3 个位置的 p 也会将 is_end 标记为真，表示 'app'。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)

搜索操作

要搜索一个精确单词，请沿着每个字符遍历 Trie。如果当前节点的 children 中缺少某个字符，则返回失败。如果找到了所有字符，就返回 node.is_end——只有当单词恰好在此处结束时结果才为真，而不仅仅是存在一个前缀。这一区分了“前缀存在”和“精确单词存在”，也是测试中经常考查的内容。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end  # must be a complete word

t = Trie()
t.insert('apple')
print(t.search('apple'))   # True
print(t.search('app'))     # False (app not inserted)
print(t.search('orange'))  # False

starts_with（前缀搜索）

starts_with 方法用于检查是否有任何已插入的单词具有给定前缀。它采用与 search 相同的遍历方式，但不检查 is_end，而是在成功沿着所有前缀字符前进后立即返回成功结果，这表示 Trie 中存在该前缀路径。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True  # prefix path exists

t = Trie()
t.insert('apple')
print(t.starts_with('app'))   # True
print(t.starts_with('ape'))   # False
print(t.search('app'))         # False (not inserted)

时间与空间复杂度

每个 Trie 操作（insert、search、starts_with）的时间复杂度都是 O(m)，其中 m 是单词长度，因为我们最多遍历 m 个节点。空间复杂度为：O(字母表大小 × N × M)，其中 N 是单词数量，M 是平均单词长度。在实际应用中，共享前缀会显著减少空间占用。基于哈希映射的 children 字典比固定的 26 字符数组更节省稀疏 Trie 树的空间，但每次查找的常数开销略高。

使用数组而非字典

如果只处理小写英文字母，可以使用固定大小的数组 children = [None] * 26，并使用索引 ord(c) - ord('a')。这种方式速度更快（子节点查找为 O(1)，而不是哈希映射查找），并且内存布局可预测。当字符集很大或未知时（例如统一码），请使用字典版本；对于只包含小写字母的竞赛类问题，请使用数组版本。

class TrieNodeArray:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class TrieArray:
    def __init__(self):
        self.root = TrieNodeArray()
    
    def insert(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = TrieNodeArray()
            node = node.children[idx]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None: return False
            node = node.children[idx]
        return node.is_end

t = TrieArray()
t.insert('cat')
print(t.search('cat'))  # True
print(t.search('car'))  # False

删除操作

从 Trie 中删除单词必须处理三种情况：(1) 单词不存在——不做任何操作；(2) 单词存在，但它是另一个单词的前缀——只取消设置 is_end；(3) 单词存在且不是前缀——从底向上删除节点，当节点仍有其他 children 或者也是另一个单词的结尾时停止。删除操作在面试中很少被考查，但从概念上了解它很有帮助。

统计具有某个前缀的单词

为每个节点添加一个 count 字段，在每次 insert 经过该节点时递增。要统计具有给定前缀的单词数量，请遍历到该前缀的结尾节点，并返回该字段的值。这样可以在 O(m) 时间内完成 autocomplete 查询，而不必遍历所有子节点，是实际 autocomplete 系统中很有用的扩展。

class TrieNodeCount:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # words passing through this node

class TrieCount:
    def __init__(self):
        self.root = TrieNodeCount()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNodeCount()
            node = node.children[c]
            node.count += 1  # increment on each level
        node.is_end = True
    
    def count_with_prefix(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return 0
            node = node.children[c]
        return node.count

t = TrieCount()
for w in ['apple','app','application','apply']:
    t.insert(w)
print(t.count_with_prefix('app'))   # 4
print(t.count_with_prefix('appl'))  # 3

Trie 与哈希映射对比

哈希映射可以在平均 O(m) 时间内完成精确查找，但无法高效回答前缀查询（需要扫描所有键）。Trie可以在 O(p) 时间内回答前缀查询，其中 p 是前缀长度；它会自然地按照共享前缀对单词进行分组，也不需要进行哈希运算。在以下情况下使用 Trie 树：需要频繁进行前缀查询、使用 autocomplete 或进行拼写检查。在以下情况下使用哈希映射：只需要精确查找。

现实系统中的 Trie 树

Trie 树在现实系统中的应用包括：autocomplete（搜索建议）、拼写检查器（查找最接近的匹配单词）、IP 路由（路由器中的最长前缀匹配）、T9 预测文本（消除字符歧义）以及 DNS 解析器（分层域名查找）。在每种情况下，Trie 树每次操作 O(m) 的时间复杂度和 O(ALPHABET × 节点数) 的空间开销之间的权衡，都使它成为大规模场景下进行快速、支持前缀查找的合适工具。

快速检查

检验您对本课数据结构与算法——编程面试准备相关概念的理解。

课程回顾

本课中您学到了：TrieNode 包含一个 children 字典和一个 is_end 布尔值，insert 会逐字符遍历，在需要时创建节点，并在末尾设置 is_end，以及search 会检查 is_end，而 starts_with 只检查前缀路径是否存在。接下来，我们将进一步学习基于前缀的 autocomplete 和 starts_with 方法。

常见问题解答

「TrieNode 类：插入与搜索」课时是免费的吗？

是的 — 「TrieNode 类：插入与搜索」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「TrieNode 类：插入与搜索」这节课中我会学到什么？

使用子节点字典和 is_end 标志构建 TrieNode，实现插入和精确搜索，并分析每次操作的 O(m) 时间复杂度，其中 m 为单词长度。你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 1 节课，共 4 节。

「TrieNode 类：插入与搜索」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 DSA Interview Prep