字典树/前缀树 trie

https://blog.csdn.net/hongxue8888/article/details/103116667

从Trie树（字典树）谈到后缀树

中缀树

在数据结构中，没有 “中缀树” 这种特定的数据结构类型。不过，中缀表达式可以用二叉树来表示，这种二叉树通常被称为表达式树。 表达式树是一种将中缀表达式转换为树形结构的表示方法，其中运算符作为非叶子节点，操作数作为叶子节点。例如，对于中缀表达式a+bc，其表达式树的根节点是+运算符，左子树是操作数a，右子树的根节点是运算符，*运算符的左子树是b，右子树是c。通过这种方式，可以方便地对中缀表达式进行分析、计算和处理。 在构建表达式树时，通常需要借助栈来辅助操作，通过扫描中缀表达式，根据运算符的优先级和栈的状态来逐步构建树形结构。

后缀树

后缀树（Suffix Tree）

前缀树、后缀树和中缀树是三种不同的树形数据结构，它们在计算机科学中有不同的应用场景。以下是它们的定义、特点及应用的详细介绍：

1. 前缀树（Trie 树，字典树）

定义： 前缀树是一种多叉树结构，用于高效存储和检索字符串集合。每个节点代表一个字符，从根到某节点的路径连接起来构成一个字符串前缀。

特点：

  • 根节点不包含字符，除根节点外每个节点只包含一个字符。
  • 从根到某一节点的路径上所有字符连接起来，即为该节点对应的字符串。
  • 每个节点的子节点字符各不相同。
  • 常用于自动补全、拼写检查、IP 路由等。

示例： 插入单词 apple, app, bat 后的前缀树：

plaintext

        root
       /    \
      a      b
     /        \
    p          a
   / \          \
  p   l          t
 /   / \
l   e   e

应用：

  • 搜索引擎的自动补全功能。
  • 输入法的候选词推荐。
  • IP 路由表的最长前缀匹配。

2. 后缀树（Suffix Tree）

定义： 后缀树是一种特殊的前缀树，它存储了一个字符串的所有后缀。对于长度为 n 的字符串，后缀树包含其 n 个后缀的压缩表示。

特点：

  • 压缩路径：将无分支的路径压缩为单个边，减少节点数。
  • 快速解决字符串问题：如子串匹配、最长公共子串、最长重复子串等。
  • 构建复杂度高：直接构建的时间复杂度为 O(n2)，优化算法（如 Ukkonen 算法）可达 O(n)。

示例： 字符串 banana 的后缀树（简化版）：

plaintext

        root
      / | | \
     b  a n  $
     |  | |
    ana na a$
     |  |
     na $
     |
     $

应用：

  • 生物信息学中的 DNA 序列分析。
  • 文本编辑器中的快速搜索。
  • 数据压缩算法。

3. 中缀树（Infix Tree）

定义： 中缀树通常指表达式树（Expression Tree），用于表示算术或逻辑表达式。树的内部节点是运算符，叶子节点是操作数。

特点：

  • 中缀表达式的树形表示：通过中序遍历可还原中缀表达式。
  • 常用于表达式求值和转换：如中缀表达式转后缀表达式（逆波兰式）。

示例： 表达式 (3+4)*5 的中缀树：

plaintext

      *
     / \
    +   5
   / \
  3   4

应用：

  • 编译器的语法分析。
  • 计算器的表达式求值。
  • 逻辑电路设计。

对比总结

数据结构核心用途典型应用场景时间复杂度
前缀树快速检索字符串前缀自动补全、拼写检查插入 / 查询 O(m)
后缀树处理字符串的所有后缀子串匹配、生物信息学构建 O(n)，查询 O(m)
中缀树表示和计算数学 / 逻辑表达式编译器、计算器求值 O(n)

补充说明

  • 后缀数组（Suffix Array）：是后缀树的一种空间更高效的替代方案，本质是后缀的排序数组，常用于字符串匹配。
  • 前缀树的变体：如压缩前缀树（Radix Tree）、AC 自动机（用于多模式匹配）。
  • 中缀表达式转后缀表达式：通过中缀树的后序遍历可直接得到后缀表达式（如 3 4 + 5 *）。
最近更新：:
Contributors: luokaiwen