数据结构之字典树（Trie）_基于字典的数据结构

字典树又叫前缀树，一种专门针对字典设计的数据结构，通常使用这种数据结构来处理字符串。

知识点

产生背景

假如有n个单词，放入map中（底层以树实现）搜索时时间复杂度为o（logn）假如有100万个单词logn 大约为20，而字典树这种数据结构做到了与个数n无关，只与单词的个数有关，单词有几个字母，时间复杂度就是几。优于单词的字母一般都是20以内，大大提高了效率。

设计推导

1、字典树

1、字典树是一个多叉树，树的内部存储了每个单词的字母。
2、我们可以设计如下节点从根节点开始，每个节点都有26个子节点。如下图（图中省略了一些没存单词的节点没画出）

2、设计节点

 class{
          char c; // 节点代表的字符
          Node next[26]; //指向26个子节点
        }
1
2
3
4

根据语言的不同，情景的不同这个子节点的设计也是有变化的，如上我们写死26只代表，存的为英文单词字符串，而且只考虑纯大写，或者纯小写的。当单词大小写混合时这里子节点就应该这样了如下：

class{
          char c; // 节点代表的字符
          Node next[52]; //指向52个子节点
        }
1
2
3
4

其实当你设计的Trie能够存url，email address时这里能都存的不仅仅是26个字符了，还要存更多字符，显然写死子节点是不合理的。其实应该设计成：每个节点指向若干个节点的指针。这里就可以使用map来实现如下：

如上图，其实存单词，取单词时我们存(取)当前节点时，下一节点的单词就已经知道了。故 char c 这个变量就不在使用了，放map中即可，我们添加了isWord 来表明当前节点是否为单词结尾

       class{
          boolean isWord;// 当前节点是否为单词结尾
          Map<Character,Node> next;//此单词，指向的下一节点
        }
1
2
3
4

3、Trie基础设计

/**
 * Create by SunnyDay on 2020/08/24
 * 默认设计为字符（Character）类型，这里不使用泛型。因为英文最为广泛。每个分隔单元就是一个字符
 */
public class Trip {

    /**
     * 节点的设计：每个单词的字母就是一个节点
     */
    private class Node {
        /**
         * 当前节点是否为单词的结尾。除了叶子节点，中间的节点也可能为单词的结尾。
         * 例如：panda，前三个pan 也是一个单词。
         */
        private boolean isWord;
        /**
         * 当前节点的下一节点。
         * 一般来说我们只考虑大写或者小写的话，设计一个trie时每个单词节点后面可能有26个节点，
         * 此时应该设计为  Node next[26]，但是这26个节点并不一定存在值，所以不用使用数组申请
         * 固定的空间。可以使用映射来申请。即：
         * TreeMap<Character, Node> next
         * 表示当前字符对应的下一节点。
         */
        private TreeMap<Character, Node> next;

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

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

    private Node root;
    private int size;

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

    /**
     * trie 中存储的单词数量
     */
    public int getSize() {
        return size;
    }
  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

Trie add 设计

 /**
     * 向trie 中添加单词（添加单词不重复）
     *
     * @param word 要添加的单词字符串
     */
    public void add(String word) {
        Node current = root;//树、链表的遍历都要从头开始。所以创建头结点的副本。
        //遍历单词的每个字符，作为节点加入trie
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (current.next.get(c) == null) {// 当前字符对应的下节点未存储在trie中时，存入。
                current.next.put(c, new Node());
            }
            current = current.next.get(c);//节点往下遍历
            //最后一个单词时，标志结束。
            if (!current.isWord) {
                current.isWord = true;
                size++;
            }

        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里注意单词结尾的处理

Trie 查询

    /**
     * 查询 word 是否在 trie中
     *
     * @param word 要查询的单词
     */
    public boolean contains(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        /**
         * 节点遍历完，cur代表最后一个节点。这时不应该返回true，应该返回此节点的isWord值。
         * 因为：可能存在这种情况用户存了panda 这个单词，未存pan这个单词。若遍历到n返回true
         * 而用户未存储，所以出现逻辑错误。应该使用此节点的isWord判断比较精确。
         */
        return cur.isWord;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里注意单词结尾判断

Trie 的前缀搜索

Trie 有时也叫前缀搜索树，就是因为Trie的前缀搜索。Trie提供了单词的前缀搜索。

 /**
     * 查询trie中是否有单词前缀为 prefix
     *
     * @param prefix 要查询前缀
     */
    public boolean isPrefix(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.next.get(c) == null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        /**
         * 遍历到结尾直接返回true，前缀并不是单词。可直接返回true这里。
         * */
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

这里吧这种数据结构基本实现了一遍。诸如目录其实trie牵涉到好多知识点，这些我们日后慢慢了解吧！

end

源码