字典树(Trie)

前言

当我们在搜索引擎输入某个字符串时，会出现这个跟这个相关联的词。字典树就是针对于这种场景设计出的数据结构。

一、数据结构

字典树，即Trie，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

• 它的有点时最大限度地减少无谓的字符串比较，查询效率比Hash表高。

• 本质上就是用空间去换时间

• 每个结点都可以存储一些额外的信息。比如可以存储本结点一共查询了多少次。根据次数，可以给用户推荐一些相关的信息。

二、基本性质

• 结点本身不存储完整的单词。
• 从根节点到某一结点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个结点的所有子结点路径代表的字符都不相同

三、结点内部实现

1. 每一个结点都是一个字符数组。举个例子，如果只有英文的话，就是一个长度为26的字母数组。当然如果是现实场景，肯定不止26个字母。

2. 当前结点数组里的每一个元素存储的都是下一个结点的字符位置，如果数组里元素没有下一个字符，则指向null。

3. 当我们查找某个单词时，从单词的第一个字符开始，依次查找每个结点，如果结点中的数组对应的查找字符指向为null，说明不存在这个字符。比如：我们用上图的Trie查找abc这个单词的时候，根结点的a下标指向下一个结点的b的下标，b的下标指向洗一个结点的c的下标。所以至此我们能找到a、b、c三个字符的结点，所以这个Trie里就存在abc这个字符。

四、实现topK的单词检索

就像前言的截图那样，当我们在每个搜索引擎中输入某些字符的时候。我们都会与这些词相关的热门搜索词。

具体实现大概就是在每个Trie的结点中存储这个单词的搜索次数。当我们输入字符时，搜索引擎就会把我们输入的字符的最后一个结点作为根节点，遍历一定范围的子结点，找出topK的单词。

五、简单实现

这里我们简单用java实现一个，只有26个字母组成的单词的字典树

/**
 * leetcode208. 实现 Trie (前缀树)
 * 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
 *
 * @author walker
 * @date 2020/9/8
 */
public class Trie {

    private final TrieNode root;

    /**
     * 构造方法
     */
    public Trie() {
        root = new TrieNode(' ');
    }

    /**
     * @param str 要插入的字符串
     */
    public void insert(String str) {
        TrieNode node = root;
        char[] chars = str.toCharArray();
        for (char c : chars) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode(c);
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }

    /**
     * 查找字典树中是否有这个值
     *
     * @param word 要查找的值
     * @return 是否存在
     */
    public boolean search(String word) {
        TrieNode node = root;
        char[] chars = word.toCharArray();
        for (char c : chars) {
            if (node.children[c - 'a'] == null) {
                return false;
            }
            node = node.children[c - 'a'];
        }
        return node.isWord;
    }

    /**
     * 是否存在以目标字符串为前缀的字符串
     *
     * @param prefix 前缀
     * @return 是否存在
     */
    public boolean startWith(String prefix) {
        TrieNode node = root;
        char[] chars = prefix.toCharArray();
        for (char c : chars) {
            if (node.children[c - 'a'] == null) {
                return false;
            }
            node = node.children[c - 'a'];
        }
        return true;
    }
}

class TrieNode {
    char val;
    boolean isWord;
    TrieNode[] children = new TrieNode[26];

    TrieNode() {
    }

    TrieNode(char c) {
        TrieNode node = new TrieNode();
        node.val = c;
    }
}

复制代码