数据结构与算法（第一季）：Trie

一、概念

• Trie 也叫做字典树、前缀树(Prefix Tree)、单词查找树。
• Trie 搜索字符串的效率主要跟字符串的长度有关。
• 假设使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词。

image

• 假设要查找dog，首先在根节点搜索有没有d子节点，然后再查看d节点下是否有o子节点，最后在o节点下查看是否有g子节点。

二、接口设计

• 可以通过set或字典来实现一个Trie。

image

三、接口实现

1、Node接口

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;
    }
}
复制代码

2、查找

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;
}
复制代码