Trie，又经常叫前缀树，字典树等，

基本性质

1，根节点不包含字符，除根节点意外每个节点只包含一个字符。

2，从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。 

3，每个节点的所有子节点包含的字符串不相同

 

优点：

可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。

　　跟哈希表比较：

　　　　1，最坏情况时间复杂度比hash表好

　　　　2，没有冲突，除非一个key对应多个值（除key外的其他信息）

　　　　3，自带排序功能（类似Radix Sort），中序遍历trie可以得到排序。

缺点：

内存消耗非常大

应用场景：

（1） 字符串检索

（2）文本预测、自动完成，see also，拼写检查

（3）词频统计

（4）排序

（5）字符串最长公共前缀

（6）字符串搜索的前缀匹配

（7） 作为其他数据结构和算法的辅助结构

 

 

递归实现样例：

定义树

class TrieNode{

        // 节点内容
        char word;
        // 子节点
        Map<Character,TrieNode> childMap;
        // 是否字符串结尾
        Boolean isEnd= true;

        public TrieNode(){
            this.isEnd=false;
            this.childMap = new HashMap<>();
        }
 }

 

新增

    public void recursionAdd(TrieNode root,String word) {
        add(root, word, 0);
    }

    /**
     * 递归写法调用方法实现递归添加
     *
     * @param node 传入要进行添加的节点
     * @param word 传入要进行添加的单词
     */
    public void add(TrieNode node, String word, int index) {
        if (!node.isEnd && index == word.length()) {
            node.isEnd = true;
        }

        if (word.length() > index) {
            char addLetter = word.charAt(index);
            if (node.childMap.get(addLetter) == null) {
                node.childMap.put(addLetter, new TrieNode());
            }
            // 基于已经存在的字符进行下个字符的递归查询
            add(node.childMap.get(addLetter), word, index + 1);
        }
    }

 

删除

    public  void deleteWord(TrieNode root , String word){
        if(!recursionContains(root, word)){
            return;
        }
        delete(root,word,0);
    }
    /**
     * 删除Trie中word递归写法(1,叶子节点删除；2，公用节点设置结尾标示为false)
     *
     * @param node
     * @param word
     * @param index
     * @return
     */
    public  Boolean delete(TrieNode node,String word,int i){

        Boolean isDel = false;

        // 字符串最后一个字节
        if(i == word.length()){
            if(CollectionUtils.isEmpty(node.childMap)){
                node = null;
                isDel = true;
            }else{
                node.isEnd = false;
                isDel  = false;
            }
        }
        else{
            char local = word.charAt(i);
            if(delete(node.childMap.get(local),word,i+1)){
                if(node.isEnd){
                    isDel = false;
                }else if(!CollectionUtils.isEmpty(node.childMap)){
                    isDel = false;

                }else{
                    node = null;
                    isDel = true;
                }
            }else{
                isDel = false;
            }
        }
        return isDel;

    }

 

查询

    public boolean recursionContains(TrieNode root,String word) {
        return contains(root, word, 0);
    }

    /**
     * 查询word中是否在Trie中递归写法
     *
     * @param node
     * @param word
     * @param index
     * @return
     */
    private boolean contains(TrieNode node, String word, int index) {
        if (index == word.length()) {
            return node.isEnd;
        }
        char c = word.charAt(index);
        if (node.childMap.get(c) == null) {
            return false;
        } else {
            return contains(node.childMap.get(c), word, index + 1);
        }
    }