高级数据结构：Trie树、后缀数组、AC自动机、红黑树

说实话，嵌入式开发做到一定深度，你会发现光靠数组和链表根本不够用。字符串匹配、关键词过滤、海量数据排序——这些场景下，普通数据结构要么慢得离谱，要么内存炸裂。今天聊的这四个家伙，都是实战中能救命的硬核工具。

我个人习惯把这类数据结构叫做「带脑子的容器」。它们不是简单存数据，而是存了一种「关系」——字符之间的前后关系、模式之间的跳转关系、节点之间的平衡关系。理解了这一点，你才算真正入门。

1. Trie树（字典树）

Trie树，说白了就是一棵「按字符分叉」的树。每个节点代表一个字符，从根到叶子的一条路径，就是一个完整的字符串。

举个例子，你要存 "cat"、"car"、"dog" 三个词。普通做法是三个字符串分别存，查找 "cat" 要逐个字符比较。Trie树怎么做？根节点分出 'c' 和 'd' 两个分支，'c' 下面再分 'a'，'a' 下面分 't' 和 'r'。查找时顺着字符走，三步到位。

核心优势： 查找时间复杂度 O(L)，L 是字符串长度。跟数据量无关。

我在项目中遇到过用 Trie 树做命令解析器。一个嵌入式设备要识别上百条 AT 指令，每条指令长度不一。用 if-else 链？代码能写到吐。用 Trie 树？建好树之后，输入一个字符走一步，走到叶子节点就命中指令。清爽得很。

// Trie树节点定义（C语言）
#define MAX_CHILDREN 26  // 假设只有小写字母

typedef struct TrieNode {
    struct TrieNode* children[MAX_CHILDREN];
    int is_end;  // 标记是否为单词结尾
} TrieNode;

TrieNode* create_node() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->is_end = 0;
    for (int i = 0; i < MAX_CHILDREN; i++) {
        node->children[i] = NULL;
    }
    return node;
}

// 插入单词
void insert(TrieNode* root, const char* word) {
    TrieNode* cur = root;
    while (*word) {
        int idx = *word - 'a';
        if (cur->children[idx] == NULL) {
            cur->children[idx] = create_node();
        }
        cur = cur->children[idx];
        word++;
    }
    cur->is_end = 1;
}
避坑指南： 我曾经在内存受限的 MCU 上硬上 Trie 树，结果每个节点 26 个指针占掉一大片 RAM。后来改用「孩子兄弟表示法」——每个节点只存第一个孩子和下一个兄弟，空间省了 80%。记住，嵌入式环境里，空间和时间永远要权衡。

2. 后缀数组

后缀数组，名字听着吓人，其实思路很朴素。你把一个字符串的所有后缀拿出来，按字典序排个序，存下每个后缀的起始位置——这就是后缀数组。

比如 "banana" 的后缀有：banana, anana, nana, ana, na, a。排序后是：a, ana, anana, banana, na, nana。对应的起始位置数组就是 [5, 3, 1, 0, 4, 2]。

为什么要搞这么个东西？因为很多字符串问题——比如找最长重复子串、找两个字符串的最长公共子串——在后缀数组上都能高效解决。配合 LCP（最长公共前缀）数组，威力更大。

我记得有一次做 DNA 序列比对，要在几百万个碱基里找重复片段。暴力法 O(n²) 根本跑不动。用后缀数组 + LCP，O(n log n) 搞定。嗯，这就是算法的魅力。

构建方法： 朴素排序 O(n² log n)，倍增法 O(n log n)，DC3 算法 O(n)。实战中倍增法最常用。 
// 后缀数组的倍增法构建（伪代码思路）
// 1. 对每个位置，按第一个字符排序
// 2. 按前2个字符排序（利用第一轮结果）
// 3. 按前4个字符排序（利用第二轮结果）
// 4. 重复直到覆盖整个字符串
// 每次排序用基数排序，总复杂度 O(n log n)
注意： 后缀数组的代码实现细节很多，边界条件容易出错。我建议你先把原理吃透，再去看具体实现。别一上来就啃 DC3，那玩意儿连我都要画半天图才能理清。

3. AC自动机

AC自动机，全称 Aho-Corasick 自动机。它解决的是「多模式串匹配」问题——给你一堆关键词，在一段长文本里找出所有出现的位置。

你想想看，如果关键词有 1000 个，每个都跑一遍 KMP？太慢了。AC自动机的做法是：先把所有关键词建成一棵 Trie 树，然后给每个节点加一个「失败指针」。匹配时，如果当前字符匹配不上，就顺着失败指针跳转，继续匹配。

这个失败指针，说白了就是「失配时最长的可匹配后缀」。它让 AC自动机在 O(n) 时间内完成所有关键词的匹配，n 是文本长度。

实战场景： 敏感词过滤、病毒特征码匹配、基因序列模式查找。

我曾经给一个网络设备做内容过滤，要同时匹配几千条 URL 黑名单规则。用 AC自动机，建好自动机之后，每个数据包进来，线性扫描一遍就出结果。CPU 占用不到 5%。换成逐个匹配？CPU 直接飙到 80%。

// AC自动机节点结构
typedef struct ACNode {
    struct ACNode* children[MAX_CHILDREN];
    struct ACNode* fail;   // 失败指针
    int output;            // 是否匹配到模式串
} ACNode;

// 构建失败指针（BFS实现）
void build_fail(ACNode* root) {
    Queue* q = create_queue();
    // 第一层节点的失败指针指向根
    for (int i = 0; i < MAX_CHILDREN; i++) {
        if (root->children[i]) {
            root->children[i]->fail = root;
            enqueue(q, root->children[i]);
        }
    }
    while (!is_empty(q)) {
        ACNode* cur = dequeue(q);
        for (int i = 0; i < MAX_CHILDREN; i++) {
            if (cur->children[i]) {
                ACNode* next = cur->children[i];
                ACNode* f = cur->fail;
                while (f && !f->children[i]) {
                    f = f->fail;
                }
                next->fail = f ? f->children[i] : root;
                next->output |= next->fail->output;
                enqueue(q, next);
            }
        }
    }
}
我的经验： 失败指针的构建是 AC自动机的核心，也是最容易写错的地方。建议你画图理解——每个节点的失败指针，就是它父节点的失败指针的对应孩子。如果那个孩子不存在，就继续往上找。BFS 一层层构建，别用递归。

4. 红黑树

红黑树，一种自平衡的二叉查找树。它保证在最坏情况下，插入、删除、查找的时间复杂度都是 O(log n)。

怎么做到的？靠颜色约束。每个节点要么红要么黑，加上五条规则：

  • 节点是红色或黑色
  • 根节点是黑色
  • 叶子节点（NIL）是黑色
  • 红色节点的子节点必须是黑色（不能有连续红节点）
  • 从任一节点到其每个叶子的所有路径，包含相同数量的黑色节点

这五条规则保证了什么？保证了任何一条路径的长度，不会超过另一条路径的两倍。说白了就是「近似平衡」——不像 AVL 树那么严格，但插入删除的调整代价更小。

为什么嵌入式里常用红黑树？ 因为它的插入和删除操作是 O(1) 次旋转，而 AVL 树可能需要 O(log n) 次。在实时性要求高的场景，这个差别很关键。

我记得在做一个任务调度器时，需要按优先级动态管理几百个任务。用红黑树做优先队列，插入和删除都稳定在微秒级。换成普通二叉查找树？最坏情况下退化成链表，直接崩了。

// 红黑树节点（简化版）
typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int key;
    Color color;
    struct RBNode* left;
    struct RBNode* right;
    struct RBNode* parent;
} RBNode;

// 左旋操作（插入和删除的调整基础）
void left_rotate(RBNode** root, RBNode* x) {
    RBNode* y = x->right;
    x->right = y->left;
    if (y->left != NULL) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == NULL) {
        *root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}
千万别手写红黑树！ 除非你在做教学或者面试。实际项目中，直接用现成的库——Linux 内核里有 rbtree.h，C++ 里有 std::map。我曾经手写过一次，调试了整整三天，最后发现是旋转时 parent 指针没更新对。血的教训。

知识体系总览

这四个数据结构，各有各的用武之地。我画了张图帮你理清关系：

高级数据结构知识体系 Trie树 字符串前缀匹配 后缀数组 子串查找/比较 AC自动机 多模式串匹配 红黑树 有序键值存储 命令解析 / 词典 DNA比对 / 文本索引 敏感词过滤 / 病毒扫描 任务调度 / 内存管理 字符串处理类 平衡树类

这四个数据结构，Trie树和AC自动机是「字符串处理」这条线上的，后缀数组是「子串分析」的利器，红黑树则是「有序数据管理」的通用方案。你不需要一次性全掌握，但遇到对应场景时，脑子里要有这根弦——「嗯，这个问题用XX结构能搞定」。

好了，这一章的内容就到这儿。代码示例我都尽量精简了，核心是让你理解「为什么用」和「怎么用」。至于「怎么写得完美」——那是你动手敲代码之后的事。

← 上一章 📖 返回目录 下一章 →