第 1 节 Trie 的思想与基本结构

Trie 树又称「字典树」「前缀树」，音同 Tree，它的典型应用对象是字符串，可以用于保存、统计。

其特点是：用边表示字符。当走到叶子结点的时候，沿途所经过的边组成了一个字符串。

其优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

以下是根据示例： "bad"、 "dad"、 "mad" 组建的 Trie 树，结点值为 表示这是一个单词的结尾（这里 的含义是 false， 的含义是 true）。

重点概括：Trie 是一棵多叉树，只用于存储字符串，有相同前缀的单词在多叉树上的路径有共同的部分。

Trie 的设计思想

• Trie 设计很巧妙，它不像一般的字典那样，把一整个单词存在数据结构里。Trie 利用单词的前缀去匹配一棵树，能匹配上，则说明这个字典里有这个单词；
• Trie 的结构有那么一点点像链表，只不过链表的 next 指针指向的是一个 Node 结点，而 Trie 的 next 指针指向的是一个 Map；
• Trie 本身携带的内容仅仅只是 isWord 这样一个布尔型变量，而沿着 next 指针一路走下来的路径，就能表示一个单词。
• 能匹配这件事情，是体现在边上的。

下面是一个 Trie 树的基本结构：

参考代码：

import java.util.TreeMap;

public class Trie {

    private class Node {
        // isWord 表示沿着根结点往下走，走到这个结点的时候是否是一个单词的结尾
        public boolean isWord;
        // 因为这里不涉及排序操作，用哈希表也是可以的
        public TreeMap<Character, Node> next;

        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie() {
        root = new Node();
        size = 0;
    }

    public int getSize() {
        return size;
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/trie 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。