Tries树的简单介绍
1、用字符集{bear，bid , sun，sunday }构建的Tries树如图所示。
特点：
1、根节点不存储字符，除根节点外每个字符包含字符。
2、从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串
3、每个单词的公共前缀作为一个字符节点保存。
2、Tries实现方式。
Tries 可以通过二维数组，链表，二叉树等结构实现。
3、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;
}
}
4、插入操作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();
}
}
5、时间复杂度
最坏情况O(N）；N为节点的个数。
搜索与插入操作的时间复杂度：O(p)。p为单词的长度。
6、应用：
Trie树的应用有很多，比如说拼写矫正，单词自动补充完整，IP路由的最长前缀匹配等。
