Tries 或 Prefix Trees（前缀树）

1. 概述

本文将介绍 Trie（也称前缀树）这种数据结构的基本概念，并演示如何实现其核心功能：插入、查找和前缀搜索。

2. 什么是 Trie？

Trie（前缀树）是一种特殊的树形结构，常用于字符串的高效检索。

它特别适合用于实现集合（Set）和关联数组（Map）这类结构，尤其是在需要按顺序遍历或查找具有相同前缀的键时表现优异。

✅ 应用场景包括但不限于：

自动补全
拼写检查
IP 路由查找

3. Trie 的结构

在 Trie 的基本实现中，每个节点保存一个字符，并维护指向其子节点的指针列表。

节点的 key 并不直接存储，而是通过从根节点到当前节点的路径推导而来。

下面是一个简单的 Trie 示例图，存储了 "geek"、"genius"、"gene" 和 "genetic" 这几个词：

Trie 示例图

为了标识哪些节点是有效的 key，我们使用一个布尔标志（isKey）。如果是用 Trie 实现 Map，还可以在节点中存储值。

⚠️ 注意：叶子节点通常是有效 key，但中间节点也可能是，因此必须手动设置 isKey 标志。

4. 插入操作

插入操作是从根节点开始，逐字符遍历 Trie，只有在子节点不存在时才创建新节点。

插入完成后，将最后一个节点标记为有效 key。

举个例子：

如果 Trie 中已有 "gene"，现在插入 "genetic"：
1. 沿着 "gene" 路径走
2. 依次创建 't'、'i'、'c' 节点
3. 将 'c' 节点标记为有效 key

反之，如果已有 "genetic"，插入 "gene" 时，不需要新增节点，只需将 'e' 节点标记为有效 key 即可。

以下是插入操作的伪代码：

algorithm insert(trie, key, value):
    node <- trie.root
    for i <- 0 to key.length:
        char <- key[i]
        if not node.hasChild(char):
            node.addChild(char)
        node <- node.getChild(char)
    node.setValue(value)
    node.setKey(true)

5. 查找操作

查找操作用于判断某个 key 是否存在于 Trie 中，并返回其对应的值（如果有的话）。

实现逻辑与插入类似：

从根节点开始，逐字符向下查找
如果某字符对应的子节点不存在，说明 key 不存在
查找完整个 key 后，检查是否为有效 key

伪代码如下：

algorithm lookup(trie, key):
    node <- trie.root
    for i <- 0 to key.length:
        char <- key[i]
        if not node.hasChild(char):
            return null
        node <- node.getChild(char)
    if node.isKey():
        return node
    else:
        return null

⚠️ 注意：整个查找过程不需要深度优先或广度优先遍历，因为输入 key 本身已经提供了完整的查找路径。

6. 前缀搜索

前缀搜索是 Trie 的一大亮点功能，用于查找所有以某个前缀开头的 key。

实现步骤如下：

找到前缀对应的路径终点节点 L
从 L 开始遍历其所有后代节点
收集所有 isKey 为 true 的节点

伪代码如下：

algorithm prefixSearch(trie, prefix):
    if prefix.length = 0:
        return {}
    
    results <- {}
    
    node <- trie.root
    
    for i <- 0 to prefix.length:
        char <- prefix[i]
        if not node.hasChild(char):
            return {}
        node <- node.getChild(char)
    
    foreach d in node.getDescendants():
        if d.isKey():
            results.add(d)
    
    return results

✅ 这个功能在自动补全、模糊搜索等场景非常实用。

7. 小结

本文介绍了 Trie（前缀树）的基本原理与实现方法，包括：

Trie 的结构特点
插入操作的实现逻辑
查找 key 是否存在的方法
如何高效进行前缀搜索

Trie 是一种非常适合处理字符串集合的高效数据结构，尤其在需要频繁进行前缀匹配的场景下优势明显。掌握其原理与实现，有助于我们在实际开发中解决一些高性能检索类问题。

Persistence

REST

Security