数据结构学习:Trie树

一、概念

• Trie树,也叫"字典树",顾名思义,是一种专门处理字符串匹配的树形结构,用来解决在一组字符串集合中快速找到某个字符串
• 类似于这种字符串匹配问题,可以使用RF暴力匹配、RK哈希匹配、散列表、红黑树等,但Trie树有它特有的优势

• 如上图所示,就是一颗Trie树,头节点’/'是无意义字符,节点存储了hi、how、see、so、her、hello等单词；
• 可以看到Tire树就是利用字符串的公共前缀,将公共前缀存储在一起

二、代码实现

可以看到,Tire树是一颗多叉树,二叉树可以每个节点存储左右节点的指针,那多叉树怎么存储呢?

• 可以利用散列表的思想,利用一个数组和下标来存储子节点的指针

package StringMatch;

/*
    Trie树
 */
public class Trie_zhu {
    private TrieNode head = new TrieNode('/'); //头节点,存储无意义字符

    static class TrieNode{
        private char value;
        private TrieNode[] Children = new TrieNode[26];
        private boolean isEnding = false;

        public TrieNode(char value){
            this.value = value;
        }
    }

    public void insert(String value){
        TrieNode p = head;
        char[] text = value.toCharArray();
        for (int i = 0; i < text.length;i++){
            int index = text[i] - 'a';
            if (p.Children[index] == null){
                TrieNode newNode = new TrieNode(text[i]);
                p.Children[index] = newNode;
            }
            p = p.Children[index];
        }
        p.isEnding = true;
    }

    public boolean find(String value){
        char[] text = value.toCharArray();
        TrieNode p = head;
        for (int i = 0; i < text.length;i++){
            int index = text[i] - 'a';
            if (p.Children[index] == null){
                return false;
            }
            p = p.Children[index];
        }
        return p.isEnding;
    }
}

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

三、Tire树的时间复杂度和空间复杂度

如果要在一组字符串中,频繁地查询某些字符串,用Trie树会非常高效,

• 构建trie树:需要扫描所有的字符串,时间复杂度为O(n),(n表示所有字符串的长度和)
• 查询trie树:如果要查询的字符串长度为k,那么只需要比对k个节点,就能完成查询操作,时间复杂度为O(k)

Trie对于匹配字符串的效率是很高的,但是会比较耗内存,是一种"空间换时间"的思路

• Trie树在实现的时候,如果是用数组,且字符串中包含’a’-'z’这26个字符,那每个节点都要存储一个长度为26的数组,并且每个数组元素还需要维护指针
• Trie树的本质是避免重复存储一组字符串的相同的前缀子串,但是现在每个字符(对应一个节点)的存储远远大于1个字节,而且,如果字符串中不仅包含小写字母,还包含大写字母、数字甚至是中文,重复前缀也不多,trie树不仅不能节省内存,还有可能浪费更多的内存

四、Tire树的优势

在一组字符串中查找某个字符串,Trie树表现的并不好,它对要处理的字符串有极其严苛的要求

• 字符串中的字符集不能太大,如果字符集太大,存储空间就会浪费很多
• 要求字符串的前缀重合比较多,不然空间消耗会大很多
• 如果要用Trie树解决问题,那我们就要从零开始实现一个Trie树,还要保证没有bug,这是在将简单的问题复杂化
• 通过指针串起来的数据块是不连续的,而Trie树中用到了指针,对缓存并不友好,性能上会打折扣

因此,这种问题更适合用红黑树或散列表来解决
Trie树的优势在于查找前缀匹配的字符串,比如浏览器中输入object,会跳出相关选项

还包括一些自动输入补全,比如输入法自动补全功能、IDE代码编辑器自动补全等