19_Trie

Trie也叫做字典树、前缀树(Prefix Tree)、单词查找树

Trie搜索字符串的效率主要跟字符串的长度有关

假设使用Trie存储cat、dog、doggy、dose、cast、add六个单词，那么Trie的样子如下： Snip20200910_5.png

接口设计

• int size(){}
• void clear(){}
• V add(String key,V value){}
• V remove(String key){}
• V get(String key){}
• boolean startsWith(String prefix){}
• boolean contains(String key){}

代码实现

package Trie;

import java.util.HashMap;

public class LZTrie<V> {
    private int size;
    private Node<V> root;

    /**
     * 元素的个数
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 清空
     */
    public void clear(){
        size = 0;
        root = null;
    }


    /**
     * 添加元素
     * @param key
     * @param value
     * @return
     */
    public V add(String key,V value){
        keyCheck(key);
        if (root == null){
            root = new Node<>(null);
        }
        Node<V> node = root;
        int len = key.length();
        for (int i = 0;i<len;i++){
            char c = key.charAt(i);
            boolean emptyChildren = node.children == null?true:false;
            Node<V> childNode = emptyChildren ? node.children.get(c) : null;
            if (childNode == null){
                childNode = new Node<>(node);
                childNode.character = c;
                node.children = emptyChildren ? new HashMap<>() : node.children;
                node.children.put(c,childNode);
            }
            node = childNode;
        }

        //单词已经存在
        if (node.word){
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }

        //新增一个单词
        node.word = true;
        node.value = value;
        size ++ ;
        return null;
    }

    /**
     * 删除
     * @param key
     * @return
     */
    public V remove(String key){

        //找到最后一个节点
        Node<V> node = node(key);

        if (node == null || !node.word) return null;
        size--;
        V oldValue = node.value;

        //如果还有子节点
        if (node.children != null  && !node.children.isEmpty()){
            node.word = false;
            node.value = null;
            return oldValue;
        }

        /**
         * 如果没有子节点
         * 找到父节点，将该节点从hashmap中移除
         * 判断父节点是否是单词的结尾和是否有其他子节点
         * 如果没有重复以上操作，继续向上查询
         * 如果有跳出循环
         */
        Node<V> parent = null;
        while ((parent = node.parent) !=null){
            parent.children.remove(node.character);
            if (parent.word || !parent.children.isEmpty()) break;
            node = parent;
        }
        return oldValue;
    }

    /**
     * 根据key获取value
     * @param key
     * @return
     */
    public V get(String key){
        Node<V> node = node(key);
        return (node != null && node.word)? node.value : null ;
    }

    /**
     * 是否有以prefix开头的单词
     * @param prefix
     * @return
     */
    public boolean startsWith(String prefix){
        return node(prefix) != null ;
    }

    /**
     * 是否包含key这个单词
     * @param key
     * @return
     */
    public boolean contains(String key){
        Node<V> node = node(key);
        return node != null && node.word;
    }

    /**
     * 根据key返回key对应的最后一个节点
     * @param key
     * @return
     */
    private Node<V> node(String key){
        keyCheck(key);
        Node<V> node = root;
        int len = key.length();
        for (int i = 0;i<len;i++){
            if (node == null || node.children == null || node.children.isEmpty()) return null;
            char c = key.charAt(i);
            node = node.children.get(c);
        }
        return node;
    }

    /**
     * key非空检查
     * @param key
     */
    private void keyCheck(String key){
        if (key == null || key.length() == 0){
            throw new IllegalArgumentException("key must not be null");
        }
    }

    private static class Node<V>{
        // 父节点
        Node<V> parent;
        // 子节点
        HashMap<Character,Node<V>> children;
        // 字符
        Character character;
        // 值
        V value;
        // 是否为单词的结尾
        boolean word;
        public Node(Node<V> parent){
            this.parent = parent;
        }

    }
}

总结

• Trie的优点：搜索前缀的效率主要和前缀的长度有关

• Trie的缺点：需要消耗大量的内存，因此还有待改进

• 更多Trie相关的数据结构和算法

  • Double-array Trie
  • Suffix Tree
  • Patricia Tree
  • Crit-bit Tree
  • AC自动机