Trie树的两种JAVA实现方式

Trie树，又叫字典树，是一种用于快速检索查找字符串的树形数据结构
说白了就是把字符串树化，每个节点是一个字符，每个节点最多有字典长度个数的子节点（比如总共有26个小写字母，那每个节点最多就有26个子节点）

图中的Trie树中有三个字符串ap.ad.bd 根节点没有字符
Trie主要有两种实现方式 二维数组和树，按照LEETCODE208题的格式来实现

 class TrieNode{
       boolean isEnd;
       TrieNode[] arr=new TrieNode[26];

   }

创建节点，假设Trie中的字符串都是小写字母（26个），用一个TrieNode数组来表示这26个子节点，通过下标按照字母顺序来记录是哪个字母，a是0，b是1…

class Trie {
   class TrieNode{
       boolean isEnd;
       TrieNode[] arr=new TrieNode[26];

   }
   TrieNode root;

    public Trie() {
      root=new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node=root;
         for(int i=0;i
             int x=word.charAt(i)-'a';
             if(node.arr[x]==null) node.arr[x]=new TrieNode();
              node=node.arr[x];
         }
        node.isEnd=true;   
    }
    
    public boolean search(String word) {
         TrieNode node=root;
         for(int i=0;i
             int x=word.charAt(i)-'a';
             if(node.arr[x]==null) return false;
             node=node.arr[x];
         }         
          return node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
             TrieNode node=root;
             for(int i=0;i
                 int x=prefix.charAt(i)-'a';
                 if(node.arr[x]==null) return false;
                 node=node.arr[x];
             }  
             return true;
    }
}

通过二维数组实现比较抽象
如下图，其中：
index是一个编号，意思是字符插入的顺序，代表该字符是第index执行插入的，如果字符已经存在（在公共前缀里），则不会进行插入
count[i] 意思是编号是i的字符是几个字符串的结束点，如果count[i]==0说明他不是一个结束点
trie[p] [u]中存储的是编号，意思是当前这个字符（u号字符）的下一个字符的位置（也就是p）这个位置也就是trie的行号，比如trie[3][4]=5;意思就是e（a+4=e）的下一个字符是第6行的,具体是哪个字符要看u

class Trie {
    int N=100000;
    int[][] trie;
    int[] count;
    int index;

    public Trie() {
       trie=new int[N][26];
       count=new int[N];
       index=0;
    }
    
    public void insert(String word) {
         int p=0;
         for(int i=0;i
             int x=word.charAt(i)-'a';
             if(trie[p][x]==0) trie[p][x]=++index;
             p=trie[p][x];
         }
        count[p]++;

    }
    
    public boolean search(String word) {
          int p=0;
          for(int i=0;i
              int x=word.charAt(i)-'a';
              if(trie[p][x]==0) return false;
              p=trie[p][x];
          }
          return count[p]!=0;
    }
    
    public boolean startsWith(String prefix) {
          int p=0;
          for(int i=0;i
              int x=prefix.charAt(i)-'a';
              if(trie[p][x]==0) return false;
              p=trie[p][x];
          }
          return true;
    }
}

trie这个数组很抽象，做个测试，插入app.apple.banana.orange,数组为：

第一个插入的是app，index是1，2，3 在0，1，2行
第二个插入的是apple，这是又从第一行开始检索，因为apple的前缀app已经在数组中了，所以不会插入，直到走到 “l” 的时候，才会进行插入（此时p从3到4）.
第三个插入的是banana，index此时已经到6了。。插入banana对应的是6，7，8，9，10，11。b在第0行，其余的在6，7，8，9，10行
第四个插入的是orange，与banana同理，o在第一行，其他的在对应的index-1行

具体是行中的第几个需要看u，也就是字母顺序

app：

apple：

banana：

orange：

总结：二维数组难理解 效率也不是很高 还是用tree吧