Trie

1、概述

• 1、Trie又叫前缀树、字典树、单词查找树。
• 2、Trie搜索字符串的效率主要和搜索字符串的长度有关。
• 3、假设使用Trie存储cat、dog、doggy、does、cast、add六个单词。

image.png
上图中红色表示是一个完整单词的结尾。从上图可知：

• 1、Trie是一个多叉树。
• 2、每个字符都对应一个节点。
• 3、存储的单词是不可能重复的。类似于一个Set一样

2、接口设计

public class Trie<V> {
    private int size;

    // 返回前缀树中单词的数量
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
    }

    /**
     * @param key
     * @return 是否包含某个单词
     */
    public boolean contains(String key) {
        return false;
    }

    /**
     * 返回key对应的value
     * @param key
     * @return
     */
    public V get(String key) {
        return null;
    }

    /**
     * @param key
     * @param value
     * @return 返回旧的value
     */
    public V add(String key, V value) {
        return null;
    }

    /**
     * 删除前缀中中存储的单词str并返回对应的value
     * 
     * @param key
     * @return
     */
    public V remove(String key) {
        return null;
    }

    /**
     * 返回前缀树中是否存储有prefix前缀的单词
     * 
     * @param prefix
     * @return
     */
    public boolean startWith(String prefix) {
        return false;
    }
}

• 1、既然前缀树的逻辑结构是一个多叉树，那么就需要节点Node。节点中需要存储parent、char、isWord（是否是单词的结尾）、value（value存入单词结尾的节点中，不需要每个节点都存）等信息。
• 2、Trie是一个多叉树，如何维护节点的子树呢？从上图中可知，每个字符对应一个节点，所以这里我们可以使用HashMap<Character,Node>来维护子树。故在Node中增加一个属性：HashMap<Character,Node> children。

private static class Node<V> {
    Node<V> parent;
    HashMap<Character, Node<V>> children;
    Character c;
    V value;
    // 是否是一个完整单词
    boolean isWord;

    public Node(Node<V> parent) {
        this.parent = parent;
    }
}

2.1、get(String key) 和 contains(String key)

方法get()和contains()实现的功能类似，这里可以定义一个方法node(String key)用于获取key对应Node。

/**
 * 返回key对应的Node
 * 
 * @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;
}

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

/**
 * 返回key对应的value
 * 
 * @param key
 * @return
 */
public V get(String key) {
    Node<V> node = node(key);
    return node != null && node.isWord ? node.value : null;
}

2.2、add(String key, V value)

添加需要遍历key中的字符，如果找不到字符对应的节点就需要创建新的节点，如果之前已经存在单词key，那么就需要对value进行覆盖，如果不是完整的单词需要修改isWorld=true。

/**
 * @param key
 * @param value
 * @return 返回旧的value
 */
public V add(String key, V value) {
    keyCheck(key);

    // 创建根节点
    if (root == null)
        root = new Node<>(null);

    int len = key.length();
    Node<V> node = root;
    for (int i = 0; i < len; i++) {
        if (node.children == null)
            node.children = new HashMap<>();
        char c = key.charAt(i);
        Node<V> childeNode = node.children.get(c);
        if (childeNode == null) {
            childeNode = new Node<>(node);
            childeNode.character = c;
            node.children.put(c, childeNode);
        }
        node = childeNode;
    }

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

    // 新增一个单词
    node.isWord = true;
    node.value = value;
    size++;

    return null;
}

2.3、startWith(String prefix)

该方法是判断是否有前缀为prefix的Node，并不要求prefix是一个完整的单词，所以这里可以使用node(String key)实现

/**
 * 返回前缀树中是否存储有prefix前缀的单词
 * 
 * @param prefix
 * @return
 */
public boolean startWith(String prefix) {
    Node<V> node = node(prefix);
    return node != null;
}

2.4、remove(String key)

删除需要先判断下单词是否存在，如果存在且最后一个节点有子节点，那么不能直接删除；否则需要从下向上进行删除，当删除到的节点是另一个单词的末尾或有子节点则不再继续删除。

/**
 * 删除前缀树中存储的单词key并返回对应的value
 * 
 * @param key
 * @return
 */
public V remove(String key) {
    // 找到最后一个节点
    Node<V> node = node(key);
    // 如果不是单词的末尾不用处理
    if (node == null || !node.isWord)
        return null;

    size--;
    V oldValue = node.value;

    // 如果node有子节点，说明key是其他单词的一部分所以不能直接删除
    if (node.children != null && !node.children.isEmpty()) {
        node.isWord = false;
        node.value = null;
        return oldValue;
    }

    // 如果node没有子节点，需要从下向上进行删除
    Node<V> parent = null;
    while ((parent = node.parent) != null) {
        parent.children.remove(node.character);
        if (parent.isWord || !parent.children.isEmpty())
            break;
        node = parent;
    }

    return oldValue;
}

3、完整代码

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

    // 返回前缀树中单词的数量
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
    }

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

    /**
     * 返回key对应的value
     * 
     * @param key
     * @return
     */
    public V get(String key) {
        Node<V> node = node(key);
        return node != null && node.isWord ? node.value : null;
    }

    /**
     * @param key
     * @param value
     * @return 返回旧的value
     */
    public V add(String key, V value) {
        keyCheck(key);

        // 创建根节点
        if (root == null)
            root = new Node<>(null);

        int len = key.length();
        Node<V> node = root;
        for (int i = 0; i < len; i++) {
            if (node.children == null)
                node.children = new HashMap<>();
            char c = key.charAt(i);
            Node<V> childeNode = node.children.get(c);
            if (childeNode == null) {
                childeNode = new Node<>(node);
                childeNode.character = c;
                node.children.put(c, childeNode);
            }
            node = childeNode;
        }

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

        // 新增一个单词
        node.isWord = true;
        node.value = value;
        size++;

        return null;
    }

    /**
     * 删除前缀中中存储的单词str并返回对应的value
     * 
     * @param key
     * @return
     */
    public V remove(String key) {
        // 找到最后一个节点
        Node<V> node = node(key);
        // 如果不是单词的末尾不用处理
        if (node == null || !node.isWord)
            return null;

        size--;
        V oldValue = node.value;

        // 如果node有子节点，说明key是其他单词的一部分所以不能直接删除
        if (node.children != null && !node.children.isEmpty()) {
            node.isWord = false;
            node.value = null;
            return oldValue;
        }

        // 如果node没有子节点，需要从下向上进行删除
        Node<V> parent = null;
        while ((parent = node.parent) != null) {
            parent.children.remove(node.character);
            if (parent.isWord || !parent.children.isEmpty())
                break;
            node = parent;
        }

        return oldValue;
    }

    /**
     * 返回前缀树中是否存储有prefix前缀的单词
     * 
     * @param prefix
     * @return
     */
    public boolean startWith(String prefix) {
        Node<V> node = node(prefix);
        return node != null;
    }

    /**
     * 返回key对应的Node
     * 
     * @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;
    }

    private void keyCheck(String key) {
        if (key == null || key.length() == 0)
            throw new IllegalArgumentException("key must be not null");
    }

    private static class Node<V> {
        Node<V> parent;
        HashMap<Character, Node<V>> children;
        Character character;
        // 当Node对应的是单词的末尾，将key对应的value存入Node中
        V value;
        // 是否是一个完整单词
        boolean isWord;

        public Node(Node<V> parent) {
            this.parent = parent;
        }
    }
}

总结：

• 1、Trie的优点：搜索字符串主要和字符串的长度有关。
• 2、Trie的缺点：占用内存较大，每个字符都要创建一个Node对象。