对于字符串查找使用的算法,
查找命中所需的时间于被查找的键的长度成正比
查找未命中只需要检查几个字符
其中longestPrefixOf(String s) 接受一个字符串参数并返回符号表中该字符串中前缀最长的键
longestPrefixOf(“shell”)的结果是she
keysWithPrefix(“she”)的结果为she和shells
keysThatMatch(“s..”)的结果为she,和sea,字符串中的.可以匹配任意的字符
接下来引入的是
单词查找树
由链接的结点组成的数据结构,链接可以为空,每个结点只有个指向他的结点,称为父节点,却可以由多个子节点构成
且每个结点由R条链接,只不过我们将空链接不表示出来罢了,与对应单词的值保存在键中最后一个字符对应节点中
查找功能:
查找过程极为简单,因为每个结点都包含了下一个可能出现的字符的连接
如果查找的结点中没有对应的保存的值,则返回空
插入操作
在插入前,必然会进行一次查找操作,可能会出现两种情况,
到达尾字符前就遇到空连接,这时候需要为剩下的字符创建一个对应结点并保存
在空链接前到达了对应的尾字符,这样只需要将该结点的值设置为对应值就行
这个实现被称为R向单词查找树
具体的实现方式
private static int R = 256;//设置字母表
private Node root;
private static class Node{
private Object val;//设置保存的值
private Node[]next = new Node[R];//下一个结点也是一个数组
}
然后是get方法
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 id) {
if(x == null)
return null;//不存在直接返回
if(id == key.length()) {
return x;
}
char temp = key.charAt(id);//获取字符
return get(x.next[temp], key, id+1);//查找下一簇
}
对应的put如下
public void put(String key,Value val) {
root = put(root, key, val, 0);
}
public Node put(Node x,String key,Value val,int id) {
if (x == null) {
x = new Node();
}
if (id == key.length()) {
x.val = val;
return x;
}
char temp = key.charAt(id);//查找第id位的字符
x.next[temp] = put(x.next[temp], key, val, id+1);
return x;
}
对于上面API
KeysWithPrefix的方法的实现
使用一个类似size()api的递归方法collect实现
此方法维护了一个队列,只要在寻找路径上发现了有val的结点,就加入队列
对应的删除不放API,但是并不难实现
找到对应的键并将其的值设置为空
如果它的连接均为空,那么删除连接,如果删除该连接导致其父连接也为空,再删除父连接,依次类推
性能特点:
单词查找树的链表形状于插入顺序无关,给定的任意一组键,其查找树都是唯一的
其优点在于其处理数组的次数只为键的长度+1
而且对于未命中的查找,我们只需要检查几个键都可以了
其需要的空间,为RN-RNW之间,w为键的平均长度,R为字母表
每个键都有一个结点去保存着关联的值,每个结点也含有R条链接,因此链接数至少为RN条
如果首字母都不同,那么每个键中的每个字母都对应着一个对应结点,即RNW
所有的键均较短的,总数接近RN
所有键均较长时,总数接近RNw
所以R的长度至关重要
然后是三向单词查找树
在此树中,每个结点都含有一个字符,三条连接和一个值.
这三条连接分别对应着小于,等于,大于结点字母的值
和R向查找树不同的是,每个非空链接索引隐式的表示了它对应的字符,
在等价的三向查找树中,他们是显式的保存在结点中,只有沿着中间前进才会找到对应的值
查找和插入都会很简单
查找:首先比较根节点和键的首字母,大的话选择右链接,小的话选择左链接,相等的话,选择中间的
然后递归的选择相同的算法,如果递归到最后的键值为空或者遇到空链接,认为查找未命中
插入同样,先进行查找,然后如果有空的,进行补完
三向单词查找树的性质
虽然和三向单词查找树类似,但是两者的数据结构性质截然不同,其中空间上完全不同
每个结点只有三个结点,所以从空间上来说,比单词查找树小的多
其链接总数在3N和3NW之间
查找成本在于
最坏情况下,一个结点可能变成一个完全的R向结点,不平衡
之后对大多数字符也需要进行几次比较
未命中的查找也只需要若干次的比较并结束于某个高层空链接
三向单词查找树的字母表
使用这个三向单词查找树,不必太过于担心字母表的大小,
三向单词查找树特别适合于含有多种类型的java的标准键