曾续缘

切换主题

前缀树（Trie），也称为字典树或检索树，是一种有序的树状数据结构，通常用于存储动态集合或者关联数组，其中的键通常是字符串。与二叉搜索树不同的是，Trie不是基于比较操作来查找节点，而是通过逐个字符地检查关键字来实现高效的检索。

Trie的主要优点是可以非常快速地找到具有相同前缀的所有键，这使得它非常适合于自动完成和拼写检查等应用。此外，Trie在插入和查找操作上都提供了相对较低的时间复杂度。

基本概念 ​

  • 根节点：空节点，不包含任何字符。
  • 子节点：每个节点可能有多个子节点，每个子节点代表一个字符。
  • 路径：从根节点到某个节点的路径表示了该节点所代表的字符串。
  • 结束标记：如果某节点是单词的结尾，则会有一个特殊的标志（如isEnd）来表示。

Trie树结构 ​

Trie树的每个节点需要存储27个信息，包括1个终结标志和26个字母。具体实现可以采用一个布尔类型来表示终结标志，并使用一个长度为26的数组来分别对应字母a-z。数组中的每个元素都是一个Trie树节点本身，体现了递归特性。

我们可以利用布尔类型来表示是否存在终结标志，而数组中某个元素是否为空对象则可以表示对应的字母是否存在。

  • 每个 Trie 节点包含一个长度为 26 的 Trie 数组 children，对应英文字母 a-z。
  • 每个节点还包含一个布尔值 isEnd，表示该节点是否为一个单词的结尾。

基本操作 ​

  1. 插入（Insert）：将一个字符串插入到前缀树中。
  2. 查找（Search）：查找前缀树中是否存在某个字符串。
  3. 前缀查找（StartsWith）：查找前缀树中是否存在以某个字符串为前缀的字符串。

插入操作 ​

  1. 从根节点开始遍历要插入的字符串 word 中的每个字符。
  2. 对于每个字符，计算其在 children 数组中的索引（即将字符转换为数组下标）。
  3. 如果当前节点的对应子节点为空，则创建一个新的 Trie 节点并赋值给当前节点的对应子节点。
  4. 将当前节点移动到该子节点。
  5. 最终将最后一个字符所在的节点的 isEnd 置为 true，表示一个单词的结束。

查找操作 ​

  1. 从根节点开始遍历要搜索的字符串，逐个字符在 children 数组中查找对应的子节点。
  2. 如果遇到某个字符对应的子节点为空，说明 Trie 中不存在该字符串，返回 false。
  3. 若搜索完所有字符后，最终节点的 isEnd 为 true，则说明 Trie 中存在该字符串，返回 true；否则返回 false。

前缀匹配 ​

  1. 与搜索操作类似，从根节点开始遍历要匹配的前缀字符串。
  2. 如果遇到某个字符对应的子节点为空，说明 Trie 中不存在以该前缀开头的字符串，返回 false。
  3. 若成功遍历完前缀字符串，返回 true，表示存在以该前缀开头的字符串，与搜索操作不同的是不需要判断isEnd。

Java实现 ​

查看代码
java
class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie cur = this;
        for(int i = 0; i < word.length(); i++){
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(cur.children[index] == null){
                cur.children[index] = new Trie();
            }
            cur = cur.children[index];
        }
        cur.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie cur = this;
        for(int i = 0; i < word.length(); i++){
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(cur.children[index] == null){
                return false;
            }
            cur = cur.children[index];
        }
        return cur.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        Trie cur = this;
        for(int i = 0; i < prefix.length(); i++){
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if(cur.children[index] == null){
                return false;
            }
            cur = cur.children[index];
        }
        return true;
    }
}