Trie树

Trie树定义

Tire树-字典树。一个树形结构，专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie树的本质，利用字符串之间的公共前缀，将重复的前缀合并在一起。
根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到各个“结尾节点”（不一定都是叶子节点）的一条路径表示一个字符串。

Trie树的构造过程的每一步都相当于往Trie树中插入一个字符串，当所有字符串都插入完成之后，Trie树就构造好了。
在Trie树中查找一个字符串的时候，将要查找的字符串分割成单个的字符，然后从Trie树的根节点开始匹配。

实现Trie树

将字符串集合构造成Trie树（将字符串插入到Trie树）。
Trie树是一个多叉树，借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针。
假设字符串中只有从a-z这26个小写字母，在数据中下标为0的位置，存储指向子节点a的指针，下标为1的位置存储指向子节点b的指针，以此类推，下标为25的位置，存储的是指向子节点z的指针，如果某个字符的子节点不存在，在对应下标的位置存储null。
在Trie树中查询一个字符串
在trie树中查找字符串的时候，通过字符的ASCII码减去“a”的ASCII码，迅速找到匹配的字节点的指针。

BF算法

public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
        this.data = data;
    }
}
public class Trie {
    private TrieNode root = new TrieNode('/');
    //往Trie树中插入一个字符串
    public void insert(char[] text) {
        TrieNode p = root;
        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.isEndingChar = true;
    }
    //在Trie树中查找一个字符串
    public boolean select(char[] pattern) {
        TrieNode p = root;
        for(int i = 0; i < pattern.length; i++) {
            int index = pattern[i] - 'a';
            if(p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if(p.isEndingChar == false)
            return false;
        else 
            return true;
    }
}

构建Trie树的过程要扫描所有字符串，时间复杂度为O(n)，n表示虽有字符串的长度和。
构建好Trie树后，在其中查找字符串的时间复杂度为O(k)，k表示要查找的字符串的长度。

Trie树缺点及优化

用数组存储一个节点的字节点的指针，如果字符串中包含从a到z这26个字符，那每个节点都要存储一个长度为26的数组，并且数组每个元素要存储一个8或者4字节指针。浪费内存。

优化：将每个节点的数组换成其他数据结构，来存储一个节点的子节点指针，有序数组、跳表、散列表、红黑树。
有序数组中的指针按照所指向的子节点中的字符的大小顺序排列。查询的时候，通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针。但是在往Trie树中插入一个字符串的时候，需要维护数组中数据的有序性。

变体：缩点优化，对于只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并。节省空间增加编码难度。

扩展：后缀树、DAT（双数组trie树）。

Trie树的使用场景

动态数据高效操作的数据结构：散列表、红黑树、跳表

字符串中包含的字符集不能太大。浪费存储空间。
字符串的前缀重合比较多。
需要从零开始实现一个Trie树。
用到了指针，数据块不连续，堆缓存不友好。

Trie树不适合精确匹配查找（散列表、红黑树），比较适合查找前缀匹配的字符串。搜索引擎提示关键词、输入法自动补全、IDE代码编辑器自动补全、浏览器啊网址输入自动补全、屏蔽字/敏感词检测。

其他问题

复杂中文实现
前缀匹配过多，选择展示
拼写错误，校正提示

参考

Apache Commons
PatriciaTrie
AbstractPatriciaTrie