CS61B 课程笔记（Lecture 37 Tries)

搜索问题的动机

在搜索问题中，我们有一个数据流，目标是检索感兴趣的信息。搜索问题的不同实例有不同的解决方法，但都需要合适的数据结构来解决。以下是一些常见的数据结构和它们的应用：

数据结构	存储操作	主要检索操作	检索方式
List	`add(key)`, `insert(key)`	`get(index)`	索引
Map	`put(key, value)`	`get(key)`	键值对
Set	`add(key)`	`containsKey(key)`	键值判断
优先队列	`add(key)`	`getSmallest()`	键的顺序（从小到大）
并查集	`connect(int_a, int_b)`	`isConnected(a, b)`	两个整数值的关系

这些抽象数据类型（ADT）定义了数据结构的行为，但不限定具体实现。可以通过层层抽象来创建更复杂的数据结构。

抽象概念

抽象是关注行为，而非实现细节。
例如，键盘是一个抽象，背后电路不同但功能一致。
当实现优先队列时，可以使用堆排序树而无需关心树的具体实现。
通过这种方式，我们可以分层次地应用抽象来构建复杂数据结构。

改进方案：Tries (字典树)

字符键映射： 如果键是ASCII字符，可以使用字符索引数组替代通用哈希表，避免存储桶（bucket）的消耗，直接映射字符到数组位置。
字符串键映射： 若键为字符串，可以使用一种特殊的数据结构：字典树（Trie），它能高效地进行字符串的插入、检索以及特殊字符串操作。

Trie的工作原理

每个节点存储一个字符，节点可以被多个键共享。
例子：存储 "sam", "sad", "sap", "same", "a", 和 "awls"。
问题：我们无法区分是否一个前缀是有效的单词。
- 解决：通过对节点进行颜色标记，标识哪些字符是完整单词。

Trie 的优缺点

时间复杂度：
- 插入：\(\Theta(L)\)，其中 \(L\) 是键的长度
- 检索：\(\Theta(L)\)
- 无需担心键的均匀分布或调整大小。
空间消耗：
- 每个节点有128个可能的子节点链接，导致大量内存浪费。

改进Trie的空间效率

哈希表Trie: 动态调整数组大小，根据负载因子增加或缩小存储空间。
二叉搜索树Trie: 只在必要时创建子节点，节点的子节点存储在二叉树中，虽然增加了搜索时间，但节省了空间。

通过不同的实现，我们可以灵活利用每种方式的优势来优化字典树。

Tries 在 Java 中的实现

Trie 的基本结构

class TrieNode {
    // 字符节点的子节点
    TrieNode[] children;
    // 标识当前节点是否是某个单词的结束
    boolean isEndOfWord;

    // 构造函数，初始化Trie节点
    public TrieNode() {
        children = new TrieNode[26];  // 假设只包含小写字母 a-z
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    // 构造函数，初始化根节点
    public Trie() {
        root = new TrieNode();
    }

    // 插入单词到Trie中
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int index = c - 'a';  // 计算字符的数组索引
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();  // 创建新节点
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;  // 标识插入结束
    }

    // 搜索单词是否存在于Trie中
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEndOfWord;
    }

    // 检查是否存在以某个前缀开头的单词
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    // 辅助方法：根据前缀进行节点查找
    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            int index = c - 'a';
            if (node.children[index] == null) {
                return null;  // 若不存在对应的路径，返回 null
            }
            node = node.children[index];
        }
        return node;
    }
}

代码解释

TrieNode 类：这是 Trie 中的基本节点。每个节点都包含一个 children 数组，它包含 26 个位置（用于存储字母 'a' 到 'z'）。isEndOfWord 表示是否有单词在该节点结束。
Trie 类：Trie 类负责提供 Trie 数据结构的操作，如插入单词和查找单词。
insert 方法：这是将单词插入到 Trie 的方法。我们遍历单词中的每个字符，并根据字符的 ASCII 值减去 'a' 来确定该字符对应的数组索引。如果该索引处没有节点，则新建一个节点。插入结束后，将 isEndOfWord 置为 true。
search 方法：用于查找给定的单词是否在 Trie 中。它使用 searchPrefix 方法查找单词，并且返回 isEndOfWord 是否为 true，以确保找到的是完整的单词，而不仅仅是前缀。
startsWith 方法：用于检查是否存在以某个前缀开头的单词。它只需要通过 searchPrefix 确认前缀是否存在即可。
searchPrefix 方法：这是一个辅助方法，用于从根节点开始，沿着前缀中的每个字符进行查找。如果中途某个字符找不到对应的子节点，则返回 null，否则返回最后的节点。

时间复杂度分析

插入单词的时间复杂度：插入一个长度为 L 的单词需要 O(L) 的时间。每次插入操作都需要遍历单词的所有字符，而对于每个字符，我们最多需要访问 children 数组中的一个元素。
查找单词的时间复杂度：查找单词或前缀同样需要 O(L) 的时间，其中 L 是单词或前缀的长度。
空间复杂度：每个节点最多需要 26 个子节点指针，且每个插入的单词都需要占用其字符所对应的路径上的节点。总体空间复杂度取决于 Trie 中的单词数和它们共享的前缀数量。

进一步优化

为了节省空间，您可以考虑使用 压缩 Trie（也称为 Radix Tree 或 Patricia Tree）。这类 Trie 会将具有公共前缀的节点合并，减少空间浪费。

class CompressedTrieNode {
    Map<String, CompressedTrieNode> children;
    boolean isEndOfWord;

    public CompressedTrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}