-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrieTree.java
More file actions
154 lines (128 loc) · 3.24 KB
/
TrieTree.java
File metadata and controls
154 lines (128 loc) · 3.24 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//
//前缀树 TrieTree
//
import java.util.*;
public class TrieTree{
private class Node{
//经过该字符的次数
private int pass;
//以该字符结束的次数
private int end;
//下一个字符
private HashMap<Integer,Node> route;
public Node(int _pass,int _end){
pass = _pass;
end = _end;
route = new HashMap<Integer,Node>();
}
}
private Node head = null;
public TrieTree(){
head = new Node(0,0);
}
public void add(String str){
if(str.isEmpty()) return;
char[] charArr = str.toCharArray();
Node p = head;
for (int i=0; i<charArr.length; i++) {
if(p.route.get((int)charArr[i]) == null){
p.route.put((int)charArr[i], new Node(0,0));
}
p = p.route.get((int)charArr[i]);
p.pass += 1;
}
p.end += 1;
}
public void del(String str){
//判断即将删除的字符串是否存在树中
if(searchStr(str)>0){
char[] charArr = str.toCharArray();
Node p = head;
Node n = null;
for (int i=0; i<charArr.length; i++) {
n = p.route.get((int)charArr[i]);
if(n!=null && --n.pass == 0){
p.route.put((int)charArr[i],null);
}
p = n;
}
p.end-=1;
}
}
public int searchStr(String str){
if(str.isEmpty()) return 0;
char[] charArr = str.toCharArray();
Node p = head;
for (int i=0; i<charArr.length; i++) {
if(p.route.get((int)charArr[i])==null) return 0;
p = p.route.get((int)charArr[i]);
}
return p.end;
}
public int searchPre(String pre){
if(pre.isEmpty()) return 0;
char[] charArr = pre.toCharArray();
Node p = head;
for (int i=0; i<charArr.length; i++) {
if(p.route.get((int)charArr[i])==null) return 0;
p = p.route.get((int)charArr[i]);
}
return p.pass;
}
public static String getArray(int max){
char[] arr=new char[max];
for (int i=0; i<max; i++) {
arr[i] = (char)(Math.random()*127);
}
return String.valueOf(arr);
}
public static Boolean compareEquals(HashMap<String,Integer> map,TrieTree trie,String str){
HashMap<String,Integer> result = new HashMap<String,Integer>();
int count = 0;
for (String _str : map.keySet()) {
if(_str == str){
result.put(str,++count);
}
}
//System.out.println("str = "+str+",mapCount = "+result.get(str)+",treeCount="+trie.searchStr(str));
return trie.searchStr(str) == result.get(str);
}
public static Boolean comparePref(HashMap<String,Integer> map,TrieTree trie,String str){
HashMap<String,Integer> result = new HashMap<String,Integer>();
int count = 0;
for (String _str : map.keySet()) {
if(_str.startsWith(str)){
result.put(str,++count);
}
}
return trie.searchPre(str) == result.get(str);
}
public static Boolean isTrue(){
int loopCount = 99999;
for (int i=0; i<loopCount; i++) {
String str = getArray((int)(Math.random()*100));
if(str.isEmpty()) continue;
TrieTree trie=new TrieTree();
HashMap<String,Integer> map = new HashMap<String,Integer>();
int random = (int)Math.random()*9999;
if(random%2==0){
trie.add(str);
map.put(str,1);
}
else{
trie.del(str);
map.remove(str);
}
if(!compareEquals(map,trie,str)){
return false;
}
if(!comparePref(map,trie,str)){
return false;
}
}
return true;
}
public static void main(String[] args){
System.out.println("result = "+isTrue());
}
}