###单词查找树
单词查找树是由字符串键中的所有字符构造而成,允许使用被查找键中的字符进行查找。比如说有一个字典,我们想要查询一个单词的释义,我们就可以根据单词生成一个单词查找树,然后将释义保存在值中。由于单词查找树的查找时间为单词字符串的长度,所以查找效率有时比排序的算法还要高。

图一所示的是一棵单词查找树。Tries是由链接的节点所组成的数据结构,这些链接可能为空,也可能指向其他节点。但是每个节点都只可能有一个指向它的节点,称为它的父节点。每个节点都有R个链接,其中R为字母表的大小。(因为Tries一般都含有大量的空链接,所以图中就把空链接忽略掉了)。有一点需要注意,图中虽然每个节点都有一个字符,但是每一个节点并没有显示存储字符,而是根据链接是否为空来间接表示。每个节点除了存储R个链接之外,还存有一个相应的值,可以是空也可以是符号表中的某个键所关联的值。我们将每个键所关联的值都存储在该键的最后一个字母所对应的节点中。

trie1

####节点的表示
如图二所示,Tries有如下两个重要的性质:

  1. 每个节点都含有R个链接,对应着每个有可能出现的字符;
  2. 字符和键均隐式地保存在数据结构中。

trie2

####查找
在单词查找树中查找是可能会出现三种情况:
1.键的尾字符所对应的节点中的值非空。如图三中shells的查找。这是一次命中的查找–键所对应的值就是键的尾字符所对应的节点中所保存的值。

2.键的尾字符所对应的节点中的值为空。如图三中shell的查找。这是一次失败的查找–符号表中不存在该键。

3.查找结束于一条空链接。这也是一次失败的查找。

trie3

####插入
和二叉查找树一样,在插入之前进行一次查找。此时可能会出现两种情况。

1.在到达键的尾字符之前就遇到一个空链接。在这种情况下,就需要为建中还未被检查的每个字符创建一个节点并将键的值保存在最后一个字符的节点中。

2.在遇到空链接之前就到达了尾字符。在这种情况下,就将该节点的值设为键所对应的值。

下面给出TrieST的java实现:

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

###三向单词查找树(Ternary search tries TSTs)
为了避免R向单词查找树过度的空间消耗, 还有另一种数据的表示方法:三向单词查找树(TST)。在三向单词查找树中,每个节点都含有一个字符、三条链接和一个值。这三条链接分别对应着当前字母小于、等于和大于节点字母的所有键。

####节点表示
图四表示了R向单词查找树到三向单词查找树的转化。和R向单词查找树不一样的是,字符和键都是显示的存储在节点中的。

trie3

下面是TST的java实现:

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