DX's Digital Garden

4._实现前缀树(Trie)

5 min read

  • 3.1
    • 这里是以数组下标是否为 null 来看有没有链表的下个字母
类名构造函数为什么这么写？
DLinkedList重载了两个既要创建“什么都不存”的哨兵节点，又要创建“存了数据”的业务节点。
TrieNode只需要一个每个节点出生时都必须把那 26 个槽位准备好，且大家出生时都是“干净”的，没有差异化需求。
 
class TrieNode{
    boolean flag;
    TrieNode[] node;
    public TrieNode(){
        node = new TrieNode[26];
        flag = false;
    }
}
 
class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode cur = root;
        for(int i=0;i<word.length();i++){
            char ch = word.charAt(i);
            if(cur.node[ch-'a']==null){
                cur.node[ch-'a'] = new TrieNode();
            }
            cur = cur.node[ch-'a'];
        }
        cur.flag = true;
    }
    
    public boolean search(String word) {
        TrieNode cur = root;
        for(int i=0;i<word.length();i++){
            char ch = word.charAt(i);
            if(cur.node[ch-'a']==null){
                return false;
            }
            cur = cur.node[ch-'a'];
        }
        return cur.flag;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for(int i=0;i<prefix.length();i++){
            char ch = prefix.charAt(i);
            if(cur.node[ch-'a']==null){
                return false;
            }
            cur = cur.node[ch-'a'];
        }
        return true;
    }
}

  • 1.30

  • 需要在外面定义TrieNode 节点，包含标志位与 next = TrieNode【26】

    • Trie 的构造函数，里 new TrieNode 为 root
    • 在三个函数中，判断用 node 传承 root，开始遍历当前是否存在后续，如果不存在，创建？返回错误？
    • search 与 prefix 只有一个区别是是否返回标志位

  • 11.15

    • 首先这其实跟图论美鸡毛关系(但其实有点像邻接矩阵),更像多叉树:26叉树,用数组TrieNode[] children;表示
    • 类似于链表或二叉树,的val值,这里也有一个isEnd的标记
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}
 
class ListNode {
    int val;
    ListNode next;
}
 
class TrieNode {
    TrieNode[] children;
}
  • 在Trei类下,先声明全局根节点root
  • 在写构造函数(不需要返回值),自动执行root = new TrieNode();
  • 最后就是三个函数,其实就是二叉树往下走,但更像链表node = node.next,node.next = new ListNode();
  • 注意String word 的逐字母遍历!和idx的定位。x-‘a’
class Trie {
    public Trie() {
    }
    public void insert(String word) {
    }
    public boolean search(String word) {
    }
    public boolean startsWith(String prefix) {
    }
}
class TrieNode{
    TrieNode[] children;
    boolean isEnd;
    public TrieNode(){
        children = new TrieNode[26];// 26 个字母的子节点
        isEnd = false;// 是否是一个完整单词的结尾
    }
}
class Trie {
    private TrieNode root;
    public Trie() { 
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode node = root;
        for(char c:word.toCharArray()){
            int idx = c-'a';
            if(node.children[idx]==null){
                node.children[idx]=new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    public boolean search(String word) {
        TrieNode node = root;
        for(char c:word.toCharArray()){
            int idx = c-'a';
            if(node.children[idx]==null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for(char c:prefix.toCharArray()){
            int idx = c-'a';
            if(node.children[idx]==null) return false;
            node = node.children[idx];
        }
        return true;
    }
}
/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Trie ├── insert() → 构建路径 + 标记结尾 ├── search() → 走完整路径 + 检查 isEnd └── startsWith() → 走完整路径即可

Trie（发音 “try”）又叫字典树 / 前缀树， ​ 它是一种专门用于字符串检索的树形结构。 它能高效地解决这些问题：

  • 插入一个单词
  • 判断一个单词是否存在
  • 判断是否有某个前缀存在

📘 核心思想

Trie 的每个节点代表一个字符， ​ 从根节点到某个节点的路径，表示一个字符串的前缀。

Graph View