前缀树用来解决这样的问题：
有数组[“a”,”abc”,”abc”,”abcd”,”bcd”,”hello”] , 求整个数组中abc的个数或者以**ab**为前缀的单词的个数？
尽管通过遍历，然后对每一个单词进行逻辑判断也能够实现，但是时间复杂度过高，前缀树可以以O(logn)的复杂度完成单词的计数和前缀的计数。

结构实现

前缀树中，元素位于节点和节点之间的树枝上，在前缀树中查找任何一个元素或者前缀都只需要O(logn)。
image.png

  1. //前缀树结构
  2. public class Tire {
  3.     //前缀树的根节点
  4.     public TreeNode root;
  5.     //前缀树的元素个数
  6.     public int size;
  7.     public Tire() {
  8.         this.root = new TreeNode();
  9.         this.size = 0;
  10.     }
  11.     //在前缀树中插入元素
  12.     public int insert(String word) {
  13.         if (null == word) {
  14.             return size;
  15.         }
  16.         char[] chars = word.toCharArray();
  17.         //根节点+1,表示多了一个元素
  18.         this.root.pass++;
  19.         //元素数+1
  20.         this.size++; 
  21.         //如果是空字符串，就说明以头节点为结尾的元素+1
  22.         if (chars.length == 0) {
  23.             this.root.end++; 
  24.             return size; 
  25.         }
  26.         TireNode node = root;
  27.         for (char c : chars) {
  28.             if (node.nexts.get(c) == null) {
  29.                 //如果没有这个字符，就新建
  30.                 node.nexts.put(c) = new TireNode();
  31.             }
  32.             node = node.nexts.get(c);
  33.             node.pass++;
  34.          }
  35.         node.end++;
  36.         return size; 
  37.     }
  38.     //在前缀树中查询单词的个数
  39.     public int search(String word) {
  40.         if (null == word) {
  41.             return 0;
  42.         }
  43.         char[] chars = word.toCharArray();
  44.         TireNode node = root;
  45.         for (char c : chars) {
  46.             //如果没有遍历完全chars，就说明没有这个单词
  47.             if (!node.nexts.containsKey(c)) {
  48.                 return 0;
  49.             }
  50.             node = node.nexts.get(c);
  51.         }
  52.         return node.end; 
  53.     }
  54.     //在前缀树中查找以prefix为前缀的单词的个数
  55.     public int searchPrefix(String prefix) {
  56.         if (null == prefix) {
  57.             return 0;
  58.         }
  59.         char[] chars = word.toCharArray();
  60.         TireNode node = root;
  61.         for (char c : chars) {
  62.             if (!node.nexts.containsKey(c)) {
  63.                 return 0;
  64.             }
  65.             node = node.nexts.get(c);
  66.         }
  67.         return node.pass; 
  68.     }
  69.     //从前缀树中删除元素
  70.     public int delete(String word) {
  71.         if (null == word || search(word) == 0) {
  72.             return 0;
  73.         }
  74.         char[] chars = word.toCharArray();
  75.         TireNode node = root;
  76.         //头节点pass--,代表少了一个word
  77.         node.pass--;
  78.         size--;
  79.         for (char c : chars) {
  80.             if (--node.nexts.get(c).pass == 0) {
  81.                 //要是直接删除没了，那就直接把这一条路径设置为null
  82.                 node.nexts.remove(c);
  83.                 return size;
  84.             }
  85.             node = node.nexts.get(c);
  86.         }
  87.         node.end--;
  88.         return size; 
  89.     }
  90. }
  91. //前缀树中节点的结构
  92. class TreeNode {
  93.     //通过该节点的元素个数
  94.     public int pass;
  95.     //以该节点结尾的元素个数
  96.     public int end;
  97.     //节点的下属节点(即字符串的下一个字符)
  98.     public HashMap<Character,TreeNode>();
  99.     public TreeNode() {
  100.         this.pass = 0;
  101.         this.end = 0;
  102.         this.nexts = new HashMap<>();
  103.     }
  104. }