前缀树（Trie）深度解析：字符串匹配的终极方案，从原理到 Java 实战全拆解

果酱带你啃java

发布于 2026-04-14 14:24:47

540

在搜索引擎输入“jav”时，瞬间弹出“java”、“javascript”、“javadoc”的联想提示；拼写“appl”时，输入法自动补全“apple”；路由器转发数据包时，通过最长前缀匹配找到目标IP的路由规则——这些场景背后，都藏着一种高效的字符串处理数据结构：前缀树（Trie）。

作为解决字符串前缀匹配、快速检索问题的“利器”，Trie以其O(L)（L为字符串长度）的查询效率，远超哈希表、红黑树等结构在特定场景下的表现。本文将从底层原理出发，拆解Trie的设计逻辑，结合Java代码实现核心操作，并通过实战案例落地应用，让你彻底掌握这一数据结构的精髓。

一、Trie的本质：用公共前缀“压缩”字符串

1.1 什么是Trie？

Trie（发音类似“try”），又称字典树或前缀树，由Edward Fredkin于1960年提出，是一种树形数据结构，核心目标是利用字符串的公共前缀减少重复存储和查询开销。

举个直观例子：存储“apple”、“app”、“apricot”、“banana”四个字符串时，普通数组或哈希表会完整存储每个字符串，而Trie会将公共前缀“ap”、“app”合并，仅存储一次：

根节点 → a → p → p（标记为“app”结束）→ l → e（标记为“apple”结束）
根节点 → a → p → r → i → c → o → t（标记为“apricot”结束）
根节点 → b → a → n → a → n → a（标记为“banana”结束）

这种“共享前缀”的特性，让Trie在处理前缀相关操作时拥有天然优势。

1.2 Trie的核心特性

根节点无数据：根节点不存储任何字符，仅作为所有字符串的起点。
节点存储状态：每个节点包含两部分信息——子节点指针（或数组）、是否为单词结束的标记（isEndOfWord）。
子节点唯一性：每个节点的子节点对应不同字符，不存在重复字符的子节点。
路径即字符串：从根节点到任意节点的路径拼接，即为一个字符串（或前缀）。

二、Trie的结构拆解：节点设计与树形逻辑

2.1 节点结构定义

Trie的最小单元是TrieNode，每个节点需满足：

指向子节点的引用（数组或哈希表）：若处理英文字母，可用长度为26的数组（对应a-z），效率更高；若处理任意字符（如中文），用Map<Character, TrieNode>更灵活。
布尔标记：标识该节点是否为某个单词的结尾。

用下图可视化节点关系（以存储“apple”为例）：

注：“app”的结束标记在第二个p节点，“apple”的结束标记在e节点。

2.2 树形结构的核心逻辑

Trie的树形结构严格遵循“前缀共享”原则：

所有具有相同前缀的字符串，会共享从根节点到前缀最后一个字符的路径。
每个字符串的结束节点必须标记isEndOfWord=true，否则仅代表前缀而非完整单词。

三、Trie的核心操作：插入、查询、删除（原理+Java实现）

3.1 基础实现：TrieNode与Trie类定义

首先定义节点类TrieNode，再实现Trie的核心操作。

3.1.1 TrieNode类

package com.jam.demo;

import lombok.Getter;
import lombok.Setter;

/**
 * Trie树节点定义
 * @author ken
 */
@Getter
@Setter
publicclass TrieNode {
    /**
     * 子节点数组：针对英文字母（a-z），索引0对应a，1对应b...25对应z
     * 相比Map，数组访问效率更高（O(1)）
     */
    private TrieNode[] children;
    
    /**
     * 标记当前节点是否为单词的结束
     */
    privateboolean isEndOfWord;

    public TrieNode() {
        // 初始化26个英文字母的子节点
        this.children = new TrieNode[26];
        this.isEndOfWord = false;
    }
}

3.1.2 Trie核心操作类

package com.jam.demo;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;

/**
 * Trie树核心操作实现
 * @author ken
 */
@Slf4j
publicclass Trie {
    /**
     * 根节点（无字符）
     */
    privatefinal TrieNode root;

    public Trie() {
        this.root = new TrieNode();
        log.info("Trie树初始化完成");
    }

    /**
     * 插入字符串到Trie树
     * @param word 待插入的字符串（仅小写英文字母）
     * @throws IllegalArgumentException 若字符串为空
     */
    public void insert(String word) {
        if (!StringUtils.hasText(word)) {
            thrownew IllegalArgumentException("插入的字符串不能为空");
        }

        TrieNode current = root;
        // 遍历字符串的每个字符
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // 计算字符对应的数组索引（a→0，b→1...）
            // 若当前字符的子节点不存在，创建新节点
            if (current.getChildren()[index] == null) {
                current.getChildren()[index] = new TrieNode();
                log.debug("创建字符'{}'的节点", c);
            }
            // 移动到子节点
            current = current.getChildren()[index];
        }
        // 标记当前节点为单词结束
        current.setEndOfWord(true);
        log.info("字符串'{}'插入完成", word);
    }

    /**
     * 查询字符串是否存在于Trie树中
     * @param word 待查询的字符串
     * @return true：存在；false：不存在
     * @throws IllegalArgumentException 若字符串为空
     */
    public boolean search(String word) {
        if (!StringUtils.hasText(word)) {
            thrownew IllegalArgumentException("查询的字符串不能为空");
        }

        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            // 若字符对应的子节点不存在，直接返回false
            if (current.getChildren()[index] == null) {
                log.debug("字符串'{}'不存在（字符'{}'未找到）", word, c);
                returnfalse;
            }
            current = current.getChildren()[index];
        }
        // 必须确认当前节点是单词结束，否则仅为前缀
        boolean exists = current.isEndOfWord();
        log.info("字符串'{}'查询结果：{}", word, exists);
        return exists;
    }

    /**
     * 查询是否存在以指定前缀开头的字符串
     * @param prefix 前缀字符串
     * @return true：存在；false：不存在
     * @throws IllegalArgumentException 若前缀为空
     */
    public boolean startsWith(String prefix) {
        if (!StringUtils.hasText(prefix)) {
            thrownew IllegalArgumentException("前缀字符串不能为空");
        }

        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.getChildren()[index] == null) {
                log.debug("前缀'{}'不存在（字符'{}'未找到）", prefix, c);
                returnfalse;
            }
            current = current.getChildren()[index];
        }
        // 只要前缀路径存在，无需检查结束标记
        log.info("前缀'{}'查询结果：存在", prefix);
        returntrue;
    }

    /**
     * 删除Trie树中的字符串
     * @param word 待删除的字符串
     * @throws IllegalArgumentException 若字符串为空
     */
    public void delete(String word) {
        if (!StringUtils.hasText(word)) {
            thrownew IllegalArgumentException("删除的字符串不能为空");
        }
        deleteRecursive(root, word, 0);
        log.info("字符串'{}'删除操作完成", word);
    }

    /**
     * 递归删除字符串（核心逻辑：回溯判断节点是否可删除）
     * @param current 当前节点
     * @param word 待删除字符串
     * @param index 当前遍历的字符索引
     * @return true：当前节点可删除（无后续子节点且非单词结束）；false：不可删除
     */
    private boolean deleteRecursive(TrieNode current, String word, int index) {
        // 递归终止条件：遍历到字符串末尾
        if (index == word.length()) {
            // 若当前节点不是单词结束，说明字符串不存在
            if (!current.isEndOfWord()) {
                log.debug("字符串'{}'不存在，无需删除", word);
                returnfalse;
            }
            // 取消单词结束标记
            current.setEndOfWord(false);
            // 若当前节点无子节点，可删除
            return current.getChildren() == null || current.getChildren().length == 0;
        }

        char c = word.charAt(index);
        int charIndex = c - 'a';
        TrieNode child = current.getChildren()[charIndex];
        // 字符对应的子节点不存在，直接返回
        if (child == null) {
            log.debug("字符串'{}'不存在，无需删除", word);
            returnfalse;
        }

        // 递归处理子节点
        boolean canDeleteChild = deleteRecursive(child, word, index + 1);

        // 若子节点可删除，移除引用
        if (canDeleteChild) {
            current.getChildren()[charIndex] = null;
            // 若当前节点非单词结束且无其他子节点，可继续删除
            return !current.isEndOfWord() && checkNoChildren(current);
        }

        returnfalse;
    }

    /**
     * 检查节点是否有子节点
     * @param node 待检查节点
     * @return true：无子节点；false：有子节点
     */
    private boolean checkNoChildren(TrieNode node) {
        for (TrieNode child : node.getChildren()) {
            if (child != null) {
                returnfalse;
            }
        }
        returntrue;
    }
}

3.2 操作实例验证

通过测试类验证核心操作，确保代码可运行：

package com.jam.demo;

import lombok.extern.slf4j.Slf4j;

/**
 * Trie树操作测试类
 * @author ken
 */
@Slf4j
publicclass TrieTest {
    public static void main(String[] args) {
        Trie trie = new Trie();

        // 插入测试
        trie.insert("apple");
        trie.insert("app");
        trie.insert("banana");
        trie.insert("apricot");

        // 查询测试
        log.info("===== 查询测试 =====");
        trie.search("app"); // true
        trie.search("apple"); // true
        trie.search("appl"); // false（非单词结束）
        trie.search("banana"); // true
        trie.search("orange"); // false

        // 前缀查询测试
        log.info("===== 前缀查询测试 =====");
        trie.startsWith("ap"); // true
        trie.startsWith("ban"); // true
        trie.startsWith("ora"); // false

        // 删除测试
        log.info("===== 删除测试 =====");
        trie.delete("app");
        trie.search("app"); // false（已删除）
        trie.search("apple"); // true（共享前缀未被删除）
        trie.delete("apple");
        trie.search("apple"); // false
        trie.startsWith("ap"); // true（apricot仍存在）
    }
}

运行结果：

15:30:00.000 INFO  com.jam.demo.Trie - Trie树初始化完成
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'a'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'p'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'p'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'l'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'e'的节点
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'apple'插入完成
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'app'插入完成
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'b'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'a'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'n'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'a'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'n'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'a'的节点
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'banana'插入完成
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'r'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'i'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'c'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符'o'的节点
15:30:00.002 DEBUG com.jam.demo.Trie - 创建字符't'的节点
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'apricot'插入完成
15:30:00.002 INFO  com.jam.demo.TrieTest - ===== 查询测试 =====
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'app'查询结果：true
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'apple'查询结果：true
15:30:00.002 DEBUG com.jam.demo.Trie - 字符串'appl'不存在（字符'l'未找到结束标记）
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'appl'查询结果：false
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'banana'查询结果：true
15:30:00.002 DEBUG com.jam.demo.Trie - 字符串'orange'不存在（字符'o'未找到）
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'orange'查询结果：false
15:30:00.002 INFO  com.jam.demo.TrieTest - ===== 前缀查询测试 =====
15:30:00.002 INFO  com.jam.demo.Trie - 前缀'ap'查询结果：存在
15:30:00.002 INFO  com.jam.demo.Trie - 前缀'ban'查询结果：存在
15:30:00.002 DEBUG com.jam.demo.Trie - 前缀'ora'不存在（字符'o'未找到）
15:30:00.002 INFO  com.jam.demo.Trie - 前缀'ora'查询结果：存在？false
15:30:00.002 INFO  com.jam.demo.TrieTest - ===== 删除测试 =====
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'app'删除操作完成
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'app'查询结果：false
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'apple'查询结果：true
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'apple'删除操作完成
15:30:00.002 INFO  com.jam.demo.Trie - 字符串'apple'查询结果：false
15:30:00.002 INFO  com.jam.demo.Trie - 前缀'ap'查询结果：存在

四、Trie的实战场景：从理论到落地

4.1 场景1：搜索引擎自动补全

自动补全是Trie最典型的应用，下面结合Spring Boot 3.2.5、MyBatis Plus 3.5.5和Swagger3实现一个简单的“单词提示”接口。

4.1.1 项目依赖（pom.xml）

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>3.2.5</version>
        <relativePath/><!-- lookup parent from repository -->
    </parent>
    <groupId>com.jam.demo</groupId>
    <artifactId>trie-demo</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <name>trie-demo</name>
    <description>Trie树实战demo</description>
    <properties>
        <java.version>17</java.version>
    </properties>
    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <dependency>
            <groupId>com.baomidou</groupId>
            <artifactId>mybatis-plus-boot-starter</artifactId>
            <version>3.5.5</version>
        </dependency>
        <dependency>
            <groupId>com.mysql</groupId>
            <artifactId>mysql-connector-j</artifactId>
            <scope>runtime</scope>
        </dependency>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>1.18.30</version>
            <scope>provided</scope>
        </dependency>
        <dependency>
            <groupId>com.alibaba.fastjson2</groupId>
            <artifactId>fastjson2</artifactId>
            <version>2.0.49</version>
        </dependency>
        <dependency>
            <groupId>org.springdoc</groupId>
            <artifactId>springdoc-openapi-starter-webmvc-ui</artifactId>
            <version>2.3.0</version>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
                <configuration>
                    <excludes>
                        <exclude>
                            <groupId>org.projectlombok</groupId>
                            <artifactId>lombok</artifactId>
                        </exclude>
                    </excludes>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>

4.1.2 数据库设计（MySQL 8.0）

CREATE TABLE`word` (
`id`bigintNOTNULL AUTO_INCREMENT COMMENT'主键',
`word`varchar(50) NOTNULLCOMMENT'单词',
`frequency`intDEFAULT0COMMENT'词频（搜索次数）',
`create_time` datetime DEFAULTCURRENT_TIMESTAMPCOMMENT'创建时间',
  PRIMARY KEY (`id`),
UNIQUEKEY`uk_word` (`word`) COMMENT'单词唯一'
) ENGINE=InnoDBDEFAULTCHARSET=utf8mb4 COMMENT='单词表';

4.1.3 实体类与Mapper

package com.jam.demo.entity;

import com.baomidou.mybatisplus.annotation.IdType;
import com.baomidou.mybatisplus.annotation.TableId;
import com.baomidou.mybatisplus.annotation.TableName;
import lombok.Data;

import java.time.LocalDateTime;

/**
 * 单词实体类
 * @author ken
 */
@Data
@TableName("word")
publicclass Word {
    @TableId(type = IdType.AUTO)
    private Long id;
    private String word;
    private Integer frequency;
    private LocalDateTime createTime;
}

package com.jam.demo.mapper;

import com.baomidou.mybatisplus.core.mapper.BaseMapper;
import com.jam.demo.entity.Word;
import org.apache.ibatis.annotations.Mapper;

/**
 * 单词Mapper
 * @author ken
 */
@Mapper
public interface WordMapper extends BaseMapper<Word> {
}

4.1.4 服务层：整合Trie与数据库

package com.jam.demo.service;

import com.baomidou.mybatisplus.core.conditions.query.LambdaQueryWrapper;
import com.baomidou.mybatisplus.extension.service.impl.ServiceImpl;
import com.jam.demo.entity.Word;
import com.jam.demo.mapper.WordMapper;
import com.jam.demo.Trie;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Service;
import org.springframework.util.CollectionUtils;

import javax.annotation.PostConstruct;
import java.util.ArrayList;
import java.util.List;

/**
 * 单词服务实现
 * @author ken
 */
@Slf4j
@Service
publicclass WordService extends ServiceImpl<WordMapper, Word> {
    /**
     * 缓存常用单词的Trie树
     */
    privatefinal Trie trie = new Trie();

    /**
     * 项目启动时初始化Trie树（加载数据库中的单词）
     */
    @PostConstruct
    public void initTrie() {
        List<Word> wordList = list();
        if (CollectionUtils.isEmpty(wordList)) {
            log.warn("数据库中无单词数据，Trie树初始化为空");
            return;
        }

        for (Word word : wordList) {
            trie.insert(word.getWord());
        }
        log.info("Trie树初始化完成，共加载{}个单词", wordList.size());
    }

    /**
     * 添加单词（同步到数据库和Trie树）
     * @param word 单词
     * @return 添加结果
     */
    public boolean addWord(String word) {
        if (!org.springframework.util.StringUtils.hasText(word)) {
            thrownew IllegalArgumentException("单词不能为空");
        }

        // 检查数据库中是否已存在
        LambdaQueryWrapper<Word> queryWrapper = new LambdaQueryWrapper<Word>()
                .eq(Word::getWord, word);
        if (count(queryWrapper) > 0) {
            log.warn("单词'{}'已存在，更新词频", word);
            Word updateWord = new Word();
            updateWord.setFrequency(getOne(queryWrapper).getFrequency() + 1);
            return update(updateWord, queryWrapper);
        }

        // 新增单词
        Word newWord = new Word();
        newWord.setWord(word);
        newWord.setFrequency(1);
        boolean saveResult = save(newWord);
        if (saveResult) {
            trie.insert(word);
            log.info("单词'{}'添加成功并同步到Trie树", word);
        }
        return saveResult;
    }

    /**
     * 根据前缀获取提示单词
     * @param prefix 前缀
     * @return 提示单词列表
     */
    public List<String> getSuggestions(String prefix) {
        if (!org.springframework.util.StringUtils.hasText(prefix)) {
            thrownew IllegalArgumentException("前缀不能为空");
        }

        // 先检查前缀是否存在
        if (!trie.startsWith(prefix)) {
            returnnew ArrayList<>();
        }

        // 递归收集所有以prefix开头的单词
        List<String> suggestions = new ArrayList<>();
        TrieNode current = trie.getRoot();
        // 移动到前缀的最后一个节点
        for (char c : prefix.toCharArray()) {
            current = current.getChildren()[c - 'a'];
        }
        // 收集所有子路径的单词
        collectWords(current, prefix, suggestions);
        return suggestions;
    }

    /**
     * 递归收集节点下的所有单词
     * @param node 当前节点
     * @param currentWord 当前拼接的字符串
     * @param suggestions 结果列表
     */
    private void collectWords(TrieNode node, String currentWord, List<String> suggestions) {
        if (node.isEndOfWord()) {
            suggestions.add(currentWord);
        }

        // 遍历所有子节点
        for (int i = 0; i < node.getChildren().length; i++) {
            TrieNode child = node.getChildren()[i];
            if (child != null) {
                char c = (char) ('a' + i);
                collectWords(child, currentWord + c, suggestions);
            }
        }
    }
}

4.1.5 控制器层（Swagger3接口）

package com.jam.demo.controller;

import com.jam.demo.service.WordService;
import io.swagger.v3.oas.annotations.Operation;
import io.swagger.v3.oas.annotations.Parameter;
import io.swagger.v3.oas.annotations.tags.Tag;
import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.springframework.http.ResponseEntity;
import org.springframework.web.bind.annotation.*;

import java.util.List;

/**
 * 单词提示接口
 * @author ken
 */
@Slf4j
@RestController
@RequestMapping("/api/words")
@RequiredArgsConstructor
@Tag(name = "单词管理接口", description = "单词添加、前缀提示等操作")
publicclass WordController {
    privatefinal WordService wordService;

    @PostMapping("/add")
    @Operation(summary = "添加单词", description = "添加单词到数据库并同步到Trie树")
    public ResponseEntity<String> addWord(
            @Parameter(description = "单词（小写英文字母）", required = true)
            @RequestParam String word) {
        boolean result = wordService.addWord(word);
        return result ? ResponseEntity.ok("单词添加成功") : ResponseEntity.badRequest().body("单词添加失败");
    }

    @GetMapping("/suggestions")
    @Operation(summary = "前缀提示", description = "根据前缀获取所有匹配的单词")
    public ResponseEntity<List<String>> getSuggestions(
            @Parameter(description = "前缀（小写英文字母）", required = true)
            @RequestParam String prefix) {
        List<String> suggestions = wordService.getSuggestions(prefix);
        return ResponseEntity.ok(suggestions);
    }
}

4.1.6 测试接口

启动项目后，访问http://localhost:8080/swagger-ui/index.html，通过Swagger UI测试：

调用/api/words/add接口添加单词：apple、app、apricot、banana。
调用/api/words/suggestions?prefix=ap，返回["app", "apple", "apricot"]，符合预期。

4.2 场景2：IP路由最长前缀匹配

路由器转发数据包时，需根据目标IP匹配最长的子网掩码前缀（如192.168.1.0/24比192.168.0.0/16更长），Trie是实现这一逻辑的高效结构。

核心思路：

将IP地址转换为32位二进制字符串（如192.168.1.1 → 11000000101010000000000100000001）。
构建二进制Trie树（每个节点只有0、1两个子节点），存储子网掩码对应的路由信息。
查询时遍历二进制字符串，记录最长匹配的路由规则。

五、Trie的性能分析与优化

5.1 时间复杂度

插入操作：O(L)，L为字符串长度（遍历每个字符并创建节点）。
查询操作：O(L)，只需遍历字符串一次即可判断存在性。
删除操作：O(L)，递归遍历字符串并回溯判断节点是否可删除。

相比哈希表的平均O(1)查询，Trie在长字符串前缀匹配场景下更高效（哈希表需计算完整哈希值，且无法直接支持前缀查询）。

5.2 空间复杂度

Trie的空间复杂度为O(N×L)，N为字符串数量，L为平均长度。若字符集较大（如中文Unicode），普通Trie会因节点过多导致空间爆炸。

5.3 优化方案

5.3.1 压缩Trie（Compact Trie）

合并单链节点（即只有一个子节点的连续节点），减少节点数量。例如“apple”的路径a→p→p→l→e，若没有其他共享前缀，可合并为“apple”一个节点。

5.3.2 双数组Trie（Double-Array Trie, DAT）

用两个数组（base和check）存储节点关系，将树形结构转化为数组结构，大幅降低空间消耗，且保持O(L)的查询效率。DAT是工业级Trie的主流实现（如Lucene的分词器）。

5.3.3 后缀Trie

针对后缀匹配场景优化，存储字符串的所有后缀（如“apple”的后缀：apple、pple、ple、le、e），适用于子串查询。

六、Trie与其他字符串匹配结构的对比

数据结构/算法	核心优势	适用场景	时间复杂度（查询）
Trie	前缀匹配高效，支持自动补全	前缀查询、自动补全、路由匹配	O(L)
哈希表	单点查询快	精确字符串匹配	平均O(1)，最坏O(N)
红黑树	有序存储，支持范围查询	有序字符串检索	O(logN)
KMP	单模式串匹配高效	长文本中匹配单个模式串	O(M+N)（M为模式串长度，N为文本长度）
AC自动机	多模式串匹配高效	敏感词过滤、日志分析	O(N)（N为文本长度）