Trie树的类型：从标准到后缀

Trie（发音类似 "try"）是一种树形的信息检索数据结构，其节点存储字母表的字母。它也被称为数字树、基数树或前缀树。通常我们将Trie分为以下三类：

• 标准Trie
• 压缩Trie
• 后缀Trie

标准Trie (Standard Trie)

标准Trie具有以下特性：

• 标准Trie具有以下数据结构：

class Node {
   
    // 存储树节点的数组
    Node[] children = new Node[26];

    // 用于检查字符串是否结束
    boolean isWordEnd;
}

• 它是一种像有序树一样的数据结构。
• 在标准Trie中，每个节点（除了根节点）都标有一个字符。
• 一个节点的子节点按字母顺序排列。
• 每个节点或分支代表键或单词的一个可能字符。
• 每个节点或分支可能有多个分支。
• 每个键或单词的最后一个节点用于标记单词或节点的结束。

下面是标准Trie的图示：

<img src="https://media.geeksforgeeks.org/wp-content/uploads/20200413192323/Trie1.jpg" alt="image" />

压缩Trie (Compressed Trie)

压缩Trie具有以下特性：

• 压缩Trie具有以下数据结构：

class Node {

    // 存储树节点的数组
    Node[] children = new Node[26];

    // 用于存储边标签
    StringBuilder[] edgeLabel = new StringBuilder[26];

    // 用于检查字符串是否结束
    boolean isEnd;
}

• 压缩Trie是标准Trie的进阶版本。
• 每个节点（除了叶子节点）至少有2个子节点。
• 它主要用于实现空间优化。
• 为了从标准Trie得到压缩Trie，我们需要对冗余节点链进行压缩。
• 它包含对字符键的分组、重新分组和取消分组。
• 在执行插入操作时，可能需要对已分组的字符进行取消分组。
• 在执行删除操作时，可能需要对已分组的字符进行重新分组。
• 存储s个字符串（键）的压缩TrieT有s个外部节点，节点总数为O(s)。

下面是压缩Trie的图示：

<img src="https://media.geeksforgeeks.org/wp-content/uploads/20200413192317/CompressedTrie.jpg" alt="image" />

后缀Trie (Suffix Trie)

后缀Trie具有以下特性：

• 后缀Trie通常具有以下数据结构（以C++为例）：

struct SuffixTreeNode { 

    // 存储节点的数组
    struct SuffixTreeNode *children[256]; 
   
    // 通过后缀链接指向其他节点的指针 
    struct SuffixTreeNode *suffixLink; 
   
    // (start, end) 区间指定了边，
    // 通过这条边将节点连接到其父节点
    int start; 
    int *end; 
   
    // 对于叶子节点，它存储从根到叶子路径的
    // 后缀索引
    int suffixIndex; 
}

• 后缀Trie是压缩Trie的进阶版本。
• 后缀Trie最常见的应用是模式匹配。
• 在执行插入操作时，我们会同时存储单词及其所有后缀。
• 后缀Trie也用于单词匹配和前缀匹配。
• 为了生成后缀Trie，我们将给定字符串的所有后缀视为单独的单词。
• 利用这些后缀，我们可以构建出一棵压缩Trie。

下面是后缀Trie的图示：

<img src="https://media.geeksforgeeks.org/wp-content/uploads/20200413192511/SuffixTrie.jpg" alt="image" />