Tries树的简单介绍

用字符集{bear，bid , sun，sunday }构建的Tries树如图所示。特点：1、根节点不存储字符，除根节点外每个字符包含字符。2、从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串3、每个单词的公共前缀作为一个字符节点保存。

Tries实现方式。Tries 可以通过二维数组，链表，二叉树等结构实现。

Tries节点的结构。JAVA 实现方式class TrieNode {    // R links to node children    private TrieNode[] links;    private final int R = 26;    private boolean isEnd;    public TrieNode() {        links = new TrieNode[R];    }    public boolean containsKey(char ch) {        return links[ch -'a'] != null;    }    public TrieNode get(char ch) {        return links[ch -'a'];    }    public void put(char ch, TrieNode node) {        links[ch -'a'] = node;    }    public void setEnd() {        isEnd = true;    }    public boolean isEnd() {        return isEnd;    }}

插入操作Java实现：class Trie {    private 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++) {            char currentChar = word.charAt(i);            if (!node.containsKey(currentChar)) {                node.put(currentChar, new TrieNode());            }            node = node.get(currentChar);        }        node.setEnd();    }}

时间复杂度最坏情况O(N）；N为节点的个数。搜索与插入操作的时间复杂度：O(p)。p为单词的长度。

应用：Trie树的应用有很多，比如说拼写矫正，单词自动补充完整，IP路由的最长前缀匹配等。