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

说实话，讲到这一章，我心里有点小激动。为什么？因为这几个数据结构，是我在实际项目中真正“救过火”的利器。Trie树帮我搞定过千万级词库的快速匹配，后缀数组让我在基因序列比对时没被性能拖垮，KD树则是我做空间索引时的首选。

嗯，咱们一个一个来。别急，我会把每个结构的核心思想、适用场景、还有我踩过的坑，都掰开揉碎了讲给你听。

一、Trie树（字典树）

Trie树，说白了就是一棵专门为字符串设计的树。它的核心思想是：利用字符串的公共前缀来节省存储空间和查询时间。

我习惯叫它“前缀树”。你想想看，如果我们要存"cat"、"car"、"dog"这三个词，用哈希表得存三个完整的字符串。但用Trie树呢？"ca"这个前缀只存一次，后面分叉成"t"和"r"。省空间，更省时间。

核心特性：

  • 根节点不包含字符，除根节点外每个节点包含一个字符
  • 从根节点到某个节点路径上的字符连接起来，就是该节点对应的字符串
  • 每个节点的所有子节点包含的字符都不相同

我在项目中遇到过这样一个场景：需要实现一个敏感词过滤系统，词库有几十万条。用哈希表？内存爆炸。用二分查找？速度太慢。最后我选了Trie树，查询时间复杂度稳定在O(L)，L是待查字符串长度，跟词库大小无关。爽不爽？

Trie树的C语言实现

#define MAX_CHAR 26  // 假设只处理小写字母

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

TrieNode* createNode() {
    TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEnd = 0;
    for (int i = 0; i < MAX_CHAR; 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]) {
            cur->children[idx] = createNode();
        }
        cur = cur->children[idx];
        word++;
    }
    cur->isEnd = 1;
}

int search(TrieNode *root, const char *word) {
    TrieNode *cur = root;
    while (*word) {
        int idx = *word - 'a';
        if (!cur->children[idx]) return 0;
        cur = cur->children[idx];
        word++;
    }
    return cur != NULL && cur->isEnd;
}

我的小技巧：如果内存紧张，可以用数组代替指针，或者用双数组Trie（Double-Array Trie）。我曾经把一个占用500MB的Trie树优化到只剩80MB，靠的就是这个。

注意：Trie树虽然查询快，但每个节点都要存26个指针（如果是全字母表），内存开销不小。我曾经见过有人用Trie树存中文词库，每个节点开几千个指针...那叫一个惨不忍睹。中文场景建议用双数组Trie或者AC自动机。

二、后缀树与后缀数组

后缀树和后缀数组，这俩是处理字符串匹配问题的“核武器”。

后缀树，就是把一个字符串的所有后缀都塞进一棵Trie树里。比如"banana"的后缀有："banana"、"anana"、"nana"、"ana"、"na"、"a"。把这些后缀建成一棵树，就是后缀树。

后缀数组呢？更省空间。它就是一个数组，存的是所有后缀按字典序排序后的起始位置。

我为什么说它们是核武器？因为有了它们，很多原本复杂的问题变得异常简单：

  • 查找一个子串是否出现：O(L)时间，L是子串长度
  • 查找最长重复子串：线性时间搞定
  • 查找两个字符串的最长公共子串：也是线性时间

我记得有一次做基因序列分析，需要在一段几百万字符的DNA序列中查找重复片段。用暴力法？跑一天都出不来结果。后来我用后缀数组+最长公共前缀（LCP）数组，几分钟就搞定了。

后缀数组的构建（倍增法）

// 简化版：计算后缀数组的排名
void buildSA(const char *s, int *sa, int n) {
    int *rk = (int*)malloc(n * sizeof(int));
    int *tmp = (int*)malloc(n * sizeof(int));
    
    // 初始化：按第一个字符排序
    for (int i = 0; i < n; i++) {
        rk[i] = s[i] - 'a';
        sa[i] = i;
    }
    
    // 倍增过程
    for (int k = 1; k < n; k *= 2) {
        // 按(rk[i], rk[i+k])双关键字排序
        // 这里省略了排序的具体实现，实际用基数排序
        // ...
    }
    
    free(rk);
    free(tmp);
}

关键理解：后缀数组本身只是一个排序后的索引数组，真正强大的是配合LCP（最长公共前缀）数组一起使用。LCP[i]表示排名第i的后缀和排名第i-1的后缀的最长公共前缀长度。有了LCP，很多问题就迎刃而解了。

避坑指南：我曾经在实现后缀数组时，排序部分用了快速排序，结果数据量一大就超时。后来换成基数排序，速度提升了10倍不止。记住：后缀数组的构建，排序是关键，一定要用O(n)的基数排序。

三、KD树

KD树，全称K-Dimensional Tree，是一种用于组织K维空间点数据的数据结构。说白了，就是多维空间的二叉搜索树。

它的核心思想是：轮流按不同维度进行划分。比如二维空间，第一层按x坐标划分，第二层按y坐标划分，第三层又按x坐标划分...如此交替。

我为什么需要它？因为工作中经常遇到这样的问题：给定一个点，找离它最近的K个点（K近邻搜索）。如果数据量小，暴力遍历就行。但数据量一上来，比如几十万个点，暴力法就扛不住了。KD树可以把搜索时间从O(n)降到O(log n)。

KD树的应用场景

  • 最近邻搜索：找离目标点最近的点
  • 范围搜索：找某个矩形区域内的所有点
  • K近邻搜索：找离目标点最近的K个点

我在做地理信息系统时，需要快速查找某个坐标附近的兴趣点。几百万个点，用KD树做索引，每次查询只需要几十微秒。嗯，这个性能，客户很满意。

KD树的构建与搜索

typedef struct KDNode {
    double point[2];  // 二维点
    struct KDNode *left;
    struct KDNode *right;
    int depth;        // 当前深度，用于决定按哪个维度划分
} KDNode;

// 构建KD树（简化版）
KDNode* buildKDTree(Point *points, int n, int depth) {
    if (n <= 0) return NULL;
    
    int axis = depth % 2;  // 0: x轴, 1: y轴
    
    // 按axis维度排序，取中位数作为分割点
    sortByAxis(points, n, axis);
    int mid = n / 2;
    
    KDNode *node = (KDNode*)malloc(sizeof(KDNode));
    node->point[0] = points[mid].x;
    node->point[1] = points[mid].y;
    node->depth = depth;
    
    node->left = buildKDTree(points, mid, depth + 1);
    node->right = buildKDTree(points + mid + 1, n - mid - 1, depth + 1);
    
    return node;
}

// 最近邻搜索（伪代码）
void nearestSearch(KDNode *node, Point target, Point *best, double *bestDist) {
    if (!node) return;
    
    double dist = distance(node->point, target);
    if (dist < *bestDist) {
        *bestDist = dist;
        *best = node->point;
    }
    
    int axis = node->depth % 2;
    double diff = target[axis] - node->point[axis];
    
    // 先搜索可能更近的一侧
    KDNode *first = (diff < 0) ? node->left : node->right;
    KDNode *second = (diff < 0) ? node->right : node->left;
    
    nearestSearch(first, target, best, bestDist);
    
    // 检查另一侧是否需要搜索
    if (fabs(diff) < *bestDist) {
        nearestSearch(second, target, best, bestDist);
    }
}

注意：KD树在高维空间（比如超过20维）性能会急剧下降，这就是所谓的“维度灾难”。如果你要处理高维数据，建议改用球树（Ball Tree）或者近似最近邻搜索（如LSH）。

知识体系总览

下面这张图，是我自己梳理的这三个数据结构的核心脉络。你看一眼，心里就有数了。

高级数据结构（三）知识体系 Trie树（字典树） 后缀树 & 后缀数组 KD树 核心：利用公共前缀 查询：O(L)，L为字符串长度 应用：词库匹配、自动补全 核心：所有后缀的排序 LCP数组是关键辅助 应用：子串查找、重复检测 核心：轮流按维度划分 搜索：O(log n) 平均 应用：K近邻、范围搜索 共同特点 都是为特定场景优化的索引结构，用空间换时间

总结一下

这三个数据结构，各有各的用武之地：

  • Trie树：字符串前缀匹配的首选，简单粗暴有效
  • 后缀树/后缀数组：字符串子串问题的终极武器，但实现稍复杂
  • KD树：多维空间搜索的利器，但要注意维度灾难

我个人建议，初学者先把Trie树吃透，它最直观也最常用。后缀数组可以慢慢啃，一旦掌握了，很多字符串问题在你眼里就变成了“模板题”。KD树嘛，等你真正遇到空间搜索的需求时再深入也不迟。

好了，这一章就到这里。代码我都给了，建议你亲手敲一遍。数据结构这东西，光看是学不会的，得动手。

公众号:蓝海资料掘金营，微信deep3321

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