Algorithm(五)：String Part II：Searching

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
public class TrieST<Value>{
	
	private static final int R = 256;
	private Node root = new Node();
	private static class Node {
		private Object value;
		private Node[] next = new Node[R];
	}
	
	public void put(String key, Value val){ 
		root = put(root, key, val, 0); 
	}
	private Node put(Node x, String key, Value val, int d){
		if (x == null) x = new Node();
		if (d == key.length()) { x.value = val; return x; }
		char c = key.charAt(d);
		x.next[c] = put(x.next[c], key, val, d+1);
		return x;
	}
	
	public boolean contains(String key){ 
		return get(key) != null; 
	}

	 public Value get(String key){
		 Node x = get(root, key, 0);
		 if (x == null) return null;
		 return (Value) x.value;
	 }
	 private Node get(Node x, String key, int d){
		 if (x == null) return null;
		 if (d == key.length()) return x;
		 char c = key.charAt(d);
		 return get(x.next[c], key, d+1);
	 }
}

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
public class TST<Value>{
	
	private Node root;
	private class Node{
		 private Value val;
		 private char c;
		 private Node left, mid, right;
	}
 
	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;
 	}
 	
 	public boolean contains(String key){ 
 		return get(key) != null; 
 	}

 	public Value get(String key){
 		Node x = get(root, key, 0);
 		if (x == null) return null;
 		return x.val;
 	}
 	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;
 	}
 }