-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathTST.java
More file actions
65 lines (58 loc) · 1.05 KB
/
TST.java
File metadata and controls
65 lines (58 loc) · 1.05 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
/**
基于三向单词查找树的符号表
*/
public class TST<Value>{
private Node root;
private class Node{
char c;
Node left;
Node mid;
Node right;
Value val;
}
public Value get(String key){
Node x = get(root, key, 0);
return (x != null) ? (Value) x.val : null;
}
private Node get(Node x, String key, int d){
if (x == null){
return null;
}
char c = key.charAt(d);
if (c < x.c){
return get(x.left, key, d);
}
else if (c > x.c){
return get(x.right, key, d);
}
else if (d < key.length() - 1){
return get(x.mid, key, d+1);
}
else{
return x;
}
}
public void put(String key, Value val){
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d){
char c = key.charAt(d);
if (x == null){
x = new Node();
x.c = c;
}
if (c < x.c){
x.left = put(x.left, key, val, d);
}
else if (c > x.c){
x.right = put(x.right, key, val, d);
}
else if (d < key.length() - 1){
x.mid = put(x.mid, key, val, d+1);
}
else{
x.val = val;
}
return x;
}
}