「Trie树」的实现

介绍

$Trie$ 树，又叫 $\lceil$ 前缀树 $\rfloor$、$\lceil$ 字典树 $\rfloor$，是一种多叉树，用来进行快速前缀匹配的一种数据结构。

与一般多叉树不同的是，

• $Trie$ 的节点不存储节点信息，仅仅存放一个标记位 $isEnd$ ，用来标记当前节点是否是路径的终点，即从 $root$ 到当前节点是一个单词。
• $Trie$ 的节点信息存放在树枝中。

应用

• 前缀匹配
• 单词补全
• 单词纠错

实现

1. $Trie$ 节点定义

   class TrieNode {
       boolean isEnd;          // 是否是单词结尾
       TrieNode[] children;     // 26叉树
       TrieNode() {
           isEnd = false;
           children = new TrieNode[26];
       }
   }

2. $Trie$ 建立

   对于给定的字符串 $word$，遍历其每个字符，一次在 $Trie$ 中检查其是否存在，

   • 如果存在，则继续往下查找；
   • 如果不存在，则在对应分支上创建节点，继续往下查找。直至遍历完 $word$

   最后，置 $isEnd=true$，表示以该节点为结尾的字符串是一个完整的单词

   public void insert(String word) {
       TrieNode p = root;
       for ( int i = 0; i < word.length(); i++ ) {
           int idx = word.charAt(i)-'a';
           if ( p.children[idx] == null ) {
               // 新建节点
               p.children[idx] = new TrieNode();
           }
           // 往下迭代
           p = p.children[idx];
       }
       // 标记为单词结尾
       p.isEnd = true;
   }

3. 查找整个字符串 $word$

   public boolean search(String word) {
       TrieNode p = root;
       for ( int i = 0; i < word.length(); i++ ) {
           int idx = word.charAt(i)-'a';
           if ( p.children[idx] == null ) {
               return false;
           }
           p = p.children[idx];
       }
       // 如果word最后一个字符是单词结尾，则查找成功；否则，word只是trie中的一个前缀
       return p.isEnd;
   }   

4. 查找前缀 $prefix$

   public boolean startsWith(String prefix) {
       TrieNode p = root;
       for ( int i = 0; i < prefix.length(); i++ ) {
           int idx = prefix.charAt(i)-'a';
           if ( p.children[idx] == null ) {
               return false;
           }
           p = p.children[idx];
       }
       // 查找到prefix，说明trie中肯定存在以prefix为前缀的单词
       return true;
   }   

5. 完整代码

   class TrieNode {
       boolean isEnd;          // 是否是单词结尾
       TrieNode[] children;     // 26叉树
       TrieNode() {
           isEnd = false;
           children = new TrieNode[26];
       }
   }    
   class Trie {
       // trie树，边存放字符信息，节点标记是否是单词结尾，及后续字符是什么
       TrieNode root;
   
       public Trie() {
           this.root = new TrieNode();
       }
       
       public void insert(String word) {
           TrieNode p = root;
           for ( int i = 0; i < word.length(); i++ ) {
               int idx = word.charAt(i)-'a';
               if ( p.children[idx] == null ) {
                   // 新建节点
                   p.children[idx] = new TrieNode();
               }
               // 往下迭代
               p = p.children[idx];
           }
           // 标记为单词结尾
           p.isEnd = true;
       }
       
       public boolean search(String word) {
           TrieNode p = root;
           for ( int i = 0; i < word.length(); i++ ) {
               int idx = word.charAt(i)-'a';
               if ( p.children[idx] == null ) {
                   return false;
               }
               p = p.children[idx];
           }
           // 如果word最后一个字符是单词结尾，则查找成功；否则，word只是trie中的一个前缀
           return p.isEnd;
       }
       
       public boolean startsWith(String prefix) {
           TrieNode p = root;
           for ( int i = 0; i < prefix.length(); i++ ) {
               int idx = prefix.charAt(i)-'a';
               if ( p.children[idx] == null ) {
                   return false;
               }
               p = p.children[idx];
           }
           // 查找到prefix，说明trie中肯定存在以prefix为前缀的单词
           return true;
       }
   }