实现Trie前缀树

Java非递归版

​

class Trie {
    private class Node{
        boolean isTrie;
        Map<Character, Node> children = new HashMap<>();
    }
    
    private Node root = new Node();
    /** Initialize your data structure here. */
    public Trie() {
        
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node node = root;
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
            if(!node.children.containsKey(c)){
                node.children.put(c, new Node());
            }
            node = node.children.get(c);
        }
        node.isTrie = true;
        return;
        
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node node = root;
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
            Node temp = node.children.get(c);
            if(temp == null)
                return false;
            node  = temp;
        }
        return node.isTrie;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node node = root;
        for(int i=0; i<prefix.length(); i++){
            char c = prefix.charAt(i);
            Node temp = node.children.get(c);
            if(temp == null)
                return false;
            node  = temp;
        }
        return node!=null;
    }
}

​

关于Trie

• 核心思想：空间换取时间

• Trie 树又叫又叫字典树、前缀树、单词查找树，它是一颗多叉查找树。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。

• 如果 海量数据 是字符串数据，那么就可以用很小的空间开销构建一颗 Trie 树，空间开销和树高有关。

{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”}

• 基本性质：

  • 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
  • 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符互不相同。

• 优点

  • 插入和查询效率很高，都是O(m)，m是待插入/查询字符串长度；（关于查询，会有人认为hash表时间复杂度O(1)不是更快？确实，但是哈希搜索的效率通常取决于hash函数的好坏，因为这决定着冲突的概率）。
  • Trie树中不同关键字不会冲突；
  • 可以对关键字按字典排序。

• 缺点

  • 当hash函数很好时，Trie树的查找效率会低于哈希查找；
  • 空间消耗比较大。
• 主要应用：字符串检索、词频统计、字符串排序、前缀匹配等