前缀树

什么是前缀树

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个术语来自于 retrieval。根据词源学，trie 的发明者 Edward Fredkin 把它读作/ˈtriː/ “tree”。但是，其他作者把它读作/ˈtraɪ/ “try”。trie 中的键通常是字符串，但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie 中的键是一串位元，可以用于表示整数或者内存地址。trie 树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

• 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
• 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符互不相同。
• 从第一字符开始有连续重复的字符只占用一个节点，比如上面的to，和ten，中重复的单词t只占用了一个节点。

前缀树的实现

重点在于节点数据结构，重要的插入和查找方法，以及递归和非递归两种形式。@pdai

节点数据结构定义

Node节点中使用map较为高效，用于映射到下一个节点：

public class Trie {
  private class Node{
      public boolean isWord; // 是否是某个单词的结束
      public TreeMap<Character, Node> next; //到下一个节点的映射
      public Node(boolean isWord){
          this.isWord = isWord;
          //初始化字典树
          next = new TreeMap<>();
      }
      public Node(){
          this(false);
      }
  }
  //根节点
  private Node root;
  //Trie单词个数
  private int size;
  public Trie(){
      root = new Node();
      size = 0;
  }
  // 获得Trie中存储的单词数量
  public int getSize(){
      return size;
  }
}