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

优点：最大限度地减少无谓的字符串比较，查询效率高；

缺点：内存消耗较大；

特性：

（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;

   }

}