关于数据结构:一文搞懂字典树

什么是字典树

字典树，是一种 空间换工夫 的数据结构，又称 Trie 树、前缀树，是一种树形构造(字典树是一种数据结构)，典型用于统计、排序、和保留大量字符串。所以常常被搜索引擎零碎用于文本词频统计。它的长处是：利用字符串的公共前缀来缩小查问工夫，最大限度地缩小无谓的字符串比拟，查问效率比哈希树高。

可能大部分状况你很难直观或者有接触的体验，可能对前缀这个玩意没啥概念，可能做题遇到前缀问题也是暴力匹配蒙混过关，如果字符串比拟少应用哈希表等构造可能也能蒙混过关，但如果字符串比拟长、雷同前缀较多那么应用字典树能够大大减少内存的应用和效率。一个字典树的利用场景：在搜寻框输出局部单词上面会有一些神关联的搜寻内容，你有时候都很神奇是怎么做到的，这其实就是字典树的一个思维。

对于字典树，有三个重要性质：

1：根节点不蕴含字符，除了根节点每个节点都只蕴含一个字符。root 节点不含字符这样做的目标是为了可能包含所有字符串。

2：从根节点到某一个节点，路过字符串起来就是该节点对应的字符串。

3：每个节点的子节点字符不同，也就是找到对应单词、字符是惟一的。

设计实现字典树

下面曾经介绍了什么是字典树，那么咱们开始设计一个字典树吧！

对于字典树，可能不同的场景或者需要设计上有一些粗疏的区别，但整体来说个别的字典树有插入、查问(指定字符串)、查问(前缀)。

咱们首先来剖析一下简略状况吧，就是字符串中全副是 26 个小写字母，刚好力扣 208 实现 Trie 树能够作为一个实现的模板。

实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前曾经插入）；否则，返回 false。
• boolean startsWith(String prefix) 如果之前曾经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

怎么设计这个字典树呢？

对于一个字典树 Trie 类，必定是要有一个根节点 root 的，而这个节点类型 TrieNode 也有很多设计形式，在这里咱们为了简略放一个 26 个大小的 TrieNode 类型数组，别离对应 ’a’-‘z’ 的字符，同时用一个 boolean 类型变量 isEnd 示意是否为字符串开端完结(如果为 true 阐明)。

class TrieNode {TrieNode son[];
    boolean isEnd;// 完结标记
    public TrieNode()// 初始化
    {son=new TrieNode[26];
    }
}

用数组的话如果字符比拟多的话可能会耗费一些内存空间，然而这里 26 个间断字符还好的，如果向一个字典树中增加big,bit,bz 那么它其实是这样的：

那么再剖析一下具体操作：

插入操作 ：遍历字符串，同时从字典树 root 节点开始遍历，找到每个字符对应的地位首先判断是否为空，如果为空须要创立一个新的 Trie。比方插入big 的枚举第一个 b 时候创立 TrieNode, 前面也是同理。不过重要的是要在进行的那个 TrieNode 将 isEnd 设为 true 表明这个节点是形成字符串的开端节点。

这部分对应的要害代码为：

TrieNode root;
/** 初始化 */
public Trie() {root=new TrieNode();
}

/** Inserts a word into the trie. */
public void insert(String word) {
    TrieNode node=root;// 长期节点用来枚举
    for(int i=0;i<word.length();i++)// 枚举字符串
    {int index=word.charAt(i)-'a';// 找到 26 个对应地位
        if(node.son[index]==null)// 如果为空须要创立
        {node.son[index]=new TrieNode();}
        node=node.son[index];
    }
    node.isEnd=true;// 最初一个节点
}

查问操作 ：查问是建设在字典树曾经建好的状况下，这个过程和查问有些相似但不须要创立 TrieNode，如果枚举的过程一旦发现该 TrieNode 未被初始化(即为空) 则返回 false，如果顺利到最初看看该节点的 isEnd 是否为 true(是否已插入已改字符结尾的字符串)，如果为 true 则返回 true。

这里用一个例子可能更好懂。插入 big 串，如果查找 ba 会因为第二次 a 对应 TrieNode 为 null 为为空。如果查找 bi 也会返回失败，因为之前插入的 big 只在 g 字符对应 TrieNode 标识 isEnd=true，但 i 字符上面的 isEnd 为 false，即不存在 bi 字符串。

该局部对应的外围代码为：

public boolean search(String word) {
    TrieNode node=root;
    for(int i=0;i<word.length();i++)
    {int index=word.charAt(i)-'a';
        if(node.son[index]==null)// 为 null 间接返回 false
        {return false;}
        node=node.son[index];
    }
    return node.isEnd==true;
}

前缀查找 ：和查问很类似然而有点区别，查找失败的话返回 false，然而如果能进行到最初一步那么返回 true。下面例子插入big 查找 bi 同样返回 true，因为存在以它为前缀的字符串。

该对应对应的外围代码为：

public boolean startsWith(String prefix) {
    TrieNode node=root;
    for(int i=0;i<prefix.length();i++)
    {int index=prefix.charAt(i)-'a';
        if(node.son[index]==null)
        {return false;}
        node=node.son[index];
    }
  // 能执行到最初即返回 true
    return  true;
}

下面代码合在一起就是残缺的字典树了，最根底的版本。完整版为：

字典树小思考

字典树根底班很容易，但很可能会呈现一些延长。

对于下面是 26 个字符的，咱们很容易用 ASCII 找到对应索引，如果字符可能性比拟多，用数组可能节约的空间比拟大，那咱们也能够用 HashMap 或者 List 来存储元素啊，用 List 的话就须要程序枚举，用 HashMap 就能够间接查问，这里就解说一个应用 HashMap()实现的字典树。

应用 HashMap 代替数组(不过应用哈希就不自带排序功能了)，其实逻辑是一样的，只须要判断时候用 HashMap 判断是否存在对应的 key 即可，HashMap 的类型为：

Map<Character,TrieNode> sonMap;

应用 HashMap 实现的字典树残缺代码为：

import java.util.HashMap;
import java.util.Map;

public  class Trie{
    class TrieNode{
        Map<Character,TrieNode> sonMap;
        boolean idEnd;
        public TrieNode()
        {sonMap=new HashMap<>();
        }
    }
    TrieNode root;
    public Trie()
    {root=new TrieNode();
    }
   
    public void insert(String word) {
        TrieNode node=root;
        for(int i=0;i<word.length();i++)
        {char ch=word.charAt(i);
            if(!node.sonMap.containsKey(ch))// 不存在插入
            {node.sonMap.put(ch,new TrieNode());
            }
            node=node.sonMap.get(ch);
        }
        node.idEnd=true;
    }
    
    public boolean search(String word) {
        TrieNode node=root;
        for(int i=0;i<word.length();i++)
        {char ch=word.charAt(i);
            if(!node.sonMap.containsKey(ch))
            {return false;}
            node=node.sonMap.get(ch);
        }
        return node.idEnd==true;// 必须标记为 true 证实有该字符串
    }


    public boolean startsWith(String prefix) {
        TrieNode node=root;
        for(int i=0;i<prefix.length();i++)
        {char ch=prefix.charAt(i);
            if(!node.sonMap.containsKey(ch))
            {return false;}
            node=node.sonMap.get(ch);
        }
        return true;// 执行到最初一步即可
    }
}

后面讲了，字典树用于大量字符的统计、排序、贮存，其实排序就是和采纳数组的形式能够进行排序，因为字符的 ASCII 有序，在读取时候能够依照这个规定读取，这个思维就和基数排序有点像了。

而统计的话可能会面临数量上统计，可能是呈现过次数或者前缀单词数量统计，如果每次都枚举可能有点浪费时间，但你能够 TrieNode 中增加一个变量，每次插入的时候能够统计次数。如果字符串有反复那能够间接增加，如果字符串要去重那能够确定插入胜利再给门路上前缀单词总数别离自增。这个的话就要具体问题具体分析了。

此外，字典树还有一个在 ACM 中用于解决求异或最值的问题，咱们称之为：01 字典树，大家感兴趣也能够自行理解(前面可能会介绍)。

总结

通过本文，想必你对字典树有了一个较好的意识，本篇的话目标还是在于让读者可能意识和学会根底的字典树，对其它变形优化能有个初步的意识。

字典树能够最大限度地缩小无谓的字符串比拟，用于词频统计和大量字符串排序。自带排序功能，应用中序遍历序列即可失去排序序列。然而如果字符很多雷同前缀很少的话那字典树就没啥效率劣势的(因为要一个一个拜访节点)。

字典树的实在利用有很多，例如字符串检索、文本预测、主动实现，see also，拼写查看、词频统计、排序、字符串最长公共前缀、字符串搜寻的前缀匹配、作为其余数据结构和算法的辅助构造等等，这里就不再介绍啦。

原创不易，还请点赞、关注、珍藏三连反对，微信搜一搜【bigsai】, 关注我，第一工夫获取干货内容！