高级数据结构（三）：跳表、Trie树、后缀树与后缀数组

说实话，每次讲到这几种数据结构，我都有点感慨。它们不像数组、链表那么基础，但一旦你掌握了，很多棘手的问题就有了优雅的解法。我在做嵌入式协议栈的时候，就靠跳表解决过一个性能瓶颈——嗯，这个后面细说。

今天咱们一口气聊四个东西：跳表、Trie树、后缀树、后缀数组。它们各自解决不同的问题，但有一个共同点——都是在基础结构上做了“聪明”的扩展。

一、跳表（Skip List）

跳表是什么？说白了，就是给有序链表加上了“快速通道”。

普通链表查找一个元素，你得从头走到尾，O(n)。跳表呢，它让一部分节点“跳”到前面去，让你能像坐电梯一样，跳过中间一大段。

跳表的结构

每个节点不止存一个next指针，而是存一个指针数组。数组的长度叫“层高”。层高越高，这个节点在越多的索引层中出现。

// 跳表节点定义
typedef struct skip_node {
    int key;
    void *value;
    int level;           // 当前节点层高
    struct skip_node **next;  // 柔性数组，指向各层的后继
} skip_node_t;

// 跳表结构
typedef struct {
    int max_level;       // 最大允许层高
    float p;             // 层高生成概率，通常0.5
    int count;           // 节点数
    skip_node_t *head;   // 头节点，层高=max_level
} skip_list_t;

这里有个细节：next 是柔性数组，每个节点实际占用的内存是 sizeof(skip_node_t) + level * sizeof(pointer)。我在项目中习惯用 p=0.5，这样平均层高是2，空间开销可控。

查找操作

从最高层开始，往右走。如果下一个节点的key比目标小，就继续往右；否则往下走一层。重复直到找到或确认不存在。

void *skip_list_search(skip_list_t *list, int key) {
    skip_node_t *cur = list->head;
    // 从最高层往下
    for (int i = list->max_level - 1; i >= 0; i--) {
        while (cur->next[i] != NULL && cur->next[i]->key < key) {
            cur = cur->next[i];
        }
    }
    // 现在cur在第0层，检查下一个
    cur = cur->next[0];
    if (cur != NULL && cur->key == key) {
        return cur->value;
    }
    return NULL;
}

你想想看，这个循环其实很巧妙——每一层都在“缩小范围”。平均时间复杂度O(log n)。

插入操作

插入时，先随机生成一个层高。然后从高层往下，记录每一层需要插入的位置。最后从下往上逐层插入。

int random_level(float p, int max_level) {
    int level = 1;
    while ((rand() / (float)RAND_MAX) < p && level < max_level) {
        level++;
    }
    return level;
}

跳表 vs 平衡树

对比项	跳表	红黑树
实现难度	低，代码量少	高，旋转逻辑复杂
范围查询	天然支持，第0层是链表	需要中序遍历
内存占用	稍高（索引指针）	较低（2个指针）
并发友好	好，锁粒度可以很细	差，全局锁常见

我曾经在一个嵌入式数据库项目中用跳表替代了红黑树。原因很简单——我们需要支持范围查询，而且多线程读写频繁。跳表的锁粒度可以控制到每个节点每层，红黑树就没这么方便了。

二、Trie树（字典树）

Trie树，也叫前缀树。它专门用来处理字符串的快速查找和前缀匹配。

它的结构很简单：每个节点代表一个字符，从根到叶子的一条路径就是一个字符串。共享前缀的字符串共用前面的节点。

节点定义

#define ALPHABET_SIZE 26

typedef struct trie_node {
    struct trie_node *children[ALPHABET_SIZE];
    int is_end;  // 标记是否为一个单词的结尾
    int count;   // 经过该节点的单词数（可选）
} trie_node_t;

这里有个坑：children 数组的大小取决于字符集。如果是小写字母，26就够了；如果是ASCII，那就得256。我做过一个中文分词的项目，字符集是几千个常用汉字，用数组就不现实了——得换成哈希表或者动态数组。

插入与查找

void trie_insert(trie_node_t *root, const char *word) {
    trie_node_t *cur = root;
    while (*word) {
        int idx = *word - 'a';
        if (cur->children[idx] == NULL) {
            cur->children[idx] = create_node();
        }
        cur = cur->children[idx];
        cur->count++;
        word++;
    }
    cur->is_end = 1;
}

int trie_search(trie_node_t *root, const char *word) {
    trie_node_t *cur = root;
    while (*word) {
        int idx = *word - 'a';
        if (cur->children[idx] == NULL) return 0;
        cur = cur->children[idx];
        word++;
    }
    return cur->is_end;
}

查找的时间复杂度是O(m)，m是字符串长度。跟字典里有多少单词无关。这就是Trie树的魅力。

前缀匹配

这个功能太实用了。比如输入法里的联想词、搜索引擎的自动补全。你只需要沿着前缀走到对应节点，然后DFS遍历所有以该节点为根的子树，就能拿到所有候选词。

我记得有一次做嵌入式设备的命令补全功能，用户输入一半命令按Tab键，要自动补全。用Trie树实现，代码不到100行，效果非常好。

三、后缀树与后缀数组

这两个东西放在一起讲，因为它们解决的是同一类问题——字符串的子串查找、重复子串、最长公共子串等。

后缀树是把一个字符串的所有后缀都插入到一棵Trie树里，然后压缩路径。后缀数组呢，就是把所有后缀按字典序排序，存成一个数组。

后缀数组的构造

假设字符串 s = "banana"，它的后缀有：

• "banana"
• "anana"
• "nana"
• "ana"
• "na"
• "a"

按字典序排序后，得到后缀数组 SA = [5, 3, 1, 0, 4, 2]，对应的是起始位置。

// 后缀数组简单构造（倍增法，O(n log n)）
// 这里只展示核心思路，完整实现较长
void build_sa(const char *s, int *sa, int n) {
    // 1. 初始化：按第一个字符排序
    // 2. 倍增：每次按2^k个字符排序
    // 3. 用基数排序优化
}

实际工程中，我很少手写后缀数组的构造。除非是性能敏感的场景，否则直接用现成的库。但理解原理很重要——它本质上是一个排序问题。

最长公共前缀（LCP）

有了后缀数组，再配合LCP数组，就能高效解决很多字符串问题。LCP[i] 表示 SA[i] 和 SA[i-1] 的最长公共前缀长度。

索引	SA	后缀	LCP
0	5	"a"	-
1	3	"ana"	1
2	1	"anana"	3
3	0	"banana"	0
4	4	"na"	0
5	2	"nana"	2

你看，LCP数组能告诉我们哪些后缀是相似的。最长重复子串就是LCP的最大值——这里是3，对应"ana"。

后缀树 vs 后缀数组

后缀树更直观，但内存开销大。后缀数组更紧凑，配合LCP数组能模拟大部分后缀树的功能。

我个人的经验是：如果字符串长度在10万以内，后缀树可以接受；超过100万，老老实实用后缀数组。曾经有个基因序列匹配的项目，字符串长度上亿，后缀树直接内存爆炸，换成后缀数组才跑起来。

知识体系总览

下面这张图帮你理清这四种数据结构的关系和适用场景：

总结

这四种数据结构，说白了都是在“加速查找”这件事上做文章。跳表给链表加索引，Trie树给字符串共享前缀，后缀树和后缀数组给字符串的所有后缀建立索引。

我在实际项目中，用得最多的是跳表和Trie树。跳表用来做内存中的有序映射，Trie树用来做命令解析和关键词匹配。后缀数组更多是在离线分析场景，比如日志去重、DNA序列比对。

嗯，今天就聊到这儿。这些结构你动手实现一遍，感受会更深。代码量都不大，但每一行都值得琢磨。