前缀树
前缀树是什么
前缀树是一种树结构,其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
前缀树基本性质
1，根节点不包含字符，除根节点意外每个节点只包含一个字符。 2，从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。 3，每个节点的所有子节点包含的字符串不相同。 优点： 可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。 跟哈希表比较： 1，最坏情况时间复杂度比hash表好 2，没有冲突，除非一个key对应多个值（除key外的其他信息） 3，自带排序功能（类似Radix Sort），中序遍历trie可以得到排序。
缺点： 1，虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针（不包含卫星数据）。 每个结点的子树的根节点的组织方式有几种。1>如果默认包含所有字符集，则查找速度快但浪费空间（特别是靠近树底部叶子）。2>如果用链接法(如左儿子右兄弟)，则节省空间但查找需顺序（部分）遍历链表。3>alphabet reduction: 减少字符宽度以减少字母集个数。,4>对字符集使用bitmap，再配合链接法。 2，如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）。
如何生成前缀树
结点的值由结点的位置决定,比如该树是一个字符串树. 我们可以定义结点有一个长度为26的结点数组,利用字符和'a'的差值 确定字符要存的位置,比如a-'a'=0,则a字符存到root[0]位置,c-'a'=2,那么c存到root[2]位置
前缀树代码实现和测试:
package com.algorithm.practice.tree;
import org.omg.PortableInterceptor.INACTIVE;
public class CreatTrieTree {
public static class TrieTree {
int path;//略过的次数---有多少字符串包含此结点到根结点的所有字符
int end;//以该结点为最后一个字符的字符串
TrieTree[] nodes;
public TrieTree() {
path = 0;
end = 0;
nodes = new TrieTree[26];
}
}
public static class Trie {
private TrieTree root;
public Trie() {
root = new TrieTree();
}
public void insert(String word) {
if (word == null || "".equals(word)) {
return;
}
TrieTree node = root;
int index;
for (char c : word.toCharArray()//遍历字符串中的每一个字符
) {
index = c - 'a';
if (node.nodes[index] == null) {
node.nodes[index] = new TrieTree();
}
node = node.nodes[index];
node.path++;
}
node.end++;
}
public int search(String str) {
if (str == null || "".equals(str)) {
return 0;
}
char[] chars = str.toCharArray();
TrieTree node = root;
int index;
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if (node.nodes[index] == null) {
return 0;
}
node = node.nodes[index];
}
return node.end;
}
public void delete(String str) {
if (search(str)!=0){ //前缀树中有才进行删除
char[]chars=str.toCharArray();
int index;
TrieTree node=root;
for(int i=0;i<chars.length;i++){
index=chars[i]-'a';
if (--node.nodes[index].path==0){
node.nodes[index]=null;
return;
}
node=node.nodes[index];
}
node.end--;
}
}
public int preFixNumber(String str){
if (str==null||"".equals(str)){
return 0;
}
char[] chars=str.toCharArray();
TrieTree node=root;
int index;
for(int i=0;i<chars.length;i++){
index=chars[i]-'a';
if (node.nodes[index]==null){
return 0;
}
node=node.nodes[index];
}
return node.path;
}
}
public static void main(String[] args) {
Trie trie = new Trie();
System.out.println(trie.search("zuo"));
trie.insert("zuo");
System.out.println(trie.search("zuo"));
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.insert("zuo");
trie.insert("zuo");
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.insert("zuoa");
trie.insert("zuoac");
trie.insert("zuoab");
trie.insert("zuoad");
trie.delete("zuoa");
System.out.println(trie.search("zuoa"));
System.out.println(trie.preFixNumber("zuo"));
}
}腾讯云开发者
