前缀树

Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

浏览量:1846

前缀树是一种用于快速检索的多叉树结构,利用字符串的公共前缀来降低查询时间,核心思想是空间换时间,经常被搜索引擎用于文本词频统计。

优点:最大限度地减少无谓的字符串比较,查询效率高;

缺点:内存消耗较大;

特性:

(1)不同字符串的相同前缀只保存一份;

(2)结点不存放数据,数据存储在树的边上,结点存放字符经过的次数和结束的次数;

代码实现:


class Trie {

   private class TrieNode{

       private boolean isEnd;

       private TrieNode[] next;

       public TrieNode(){

           this.isEnd=false;

           next=new TrieNode[26];

       }

   }

   private TrieNode root;

   public Trie() {

       root=new TrieNode();

   }

   

   public void insert(String word) {

       TrieNode cur=root;

       for(int i=0,len=word.length(),ch;i<len;i++){

           ch=word.charAt(i)-'a';

           if(cur.next[ch]==null)

               cur.next[ch]=new TrieNode();

           cur=cur.next[ch];

       }

       cur.isEnd=true;

   }

   

   public boolean search(String word) {

       TrieNode cur=root;

       for(int i=0,len=word.length(),ch;i<len;i++){

           ch=word.charAt(i)-'a';

           if(cur.next[ch]==null)

               return false;

           cur=cur.next[ch];

       }

       return cur.isEnd;

   }

   

   public boolean startsWith(String prefix) {

       TrieNode cur=root;

       for(int i=0,len=prefix.length(),ch;i<len;i++){

           ch=prefix.charAt(i)-'a';

           if(cur.next[ch]==null)

               return false;

           cur=cur.next[ch];

       }

       return true;

   }

}