字符串查找算法分析

算法对比：

算法（数据结构）	优点
二叉查找树（BST）	适用于随机排列的键
2-3树查找（红黑树）	有性能保证
线性探测法（并行数组）	内置类型，缓存散列值
R向单词查找树	适用于较短键和较小的字母表
三向单词查找树	适用于非随机的键

如果空间足够，R向单词查找树的速度是最快的，能够在常数次次数比较内完成查找。对于大型字母表，R向单词查找树所需空间可能无法满足时，三向单词查找树是最佳选择，因为它对字符比较次数是对数级别的，而二叉查找树中键的比较次数是对数级别的。散列表也很有用，但它不支持有序性符号表操作，也不支持扩展的字符类API操作。

R向单词查找树

单词查找树的数据结构是一种树型结构，它由字符串键中所有字符构造而成，允许使用被查找键中的字符进行查找。

算法实现：

结点类：

private static class Node{
	private Object val;
	private Node[] next = new Node[R];
}

其中R是字母表的大小，如ASCII码是256。结点的值val可以是空，也可以是符号表中某个键所关联的值。具体来说，将某个键所关联的值保存在这个键最后一个字母所对应的结点中。

查找操作：

单词查找树以被查找的键中的字符为导向的。每个结点包含下一个可能出现的所有字符的链接，从根节点开始，首先经过的是键的首字母所对应的链接；在下一个结点中沿着第二个字符所对应的链接继续前进......如此这般知道最后一个结点或遇到一个空连接。

举例说明单词查找树的查找：比如树中存有“sea”字符串，那么根节点的next[]中下标s对应的数组元素非空（即有一条指向子结点的链接），该子结点中e下标对应的数组元素也非空，然后再根据e下标中的链接找到下一层结点，这个结点中 的val保存这该字符串“sea"。

查找过程中可能会出现三种情况：

• 键的尾字符所对应的结点中的值非空----这是一次命中的查找。
• 键的尾字符所对应的结点中的值为空----这是一次未命中的查找。
• 查找结束于一条空连接----这是一次未命中的查找。

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;
}

删除操作：

第一步是找到键所对应的结点并将它的值设置为空(null)。如果该结点含有某个非空的链接指向某个子结点，那么不需要进行其他操作；如果它的所有链接都为空，则从树中删去这个结点。如果删去它使得它的父结点的链接也全部空，就继续删去它的父结点，依此类推。

public void delete(String key) {
	root = delete(root,key,0);
}
private Node delete(Node x, String key,int d) {
	if(x==null)	return null;
	if(d==key.length())	x.val = null;
	else {
		char c = key.charAt(d);
		x.next[c] = delete(x.next[c],key,d+1);
	}
	if(x.val!=null)	return x;
	for(char c=0;c<R;c++)
		if(x.next[c]!=null)return x;
	return null;
}

R向单词查找树的性质：

1. 单词查找树的链表结构和插入或删除的顺序无关，对于给定的任意一组键，其单词查找树都是唯一的。
2. 在单词查找树中插入或查找一个键时，访问数组的次数最多为键的长度加一。
3. 字母表的大小为R，在一棵由N个键构造的单词查找树中，未命中查找平均所需检查的数量为~(logR)N。
4. 一棵单词查找树中链接总数在RN到RNw之间，其中w为键的平均长度。

三向单词查找树

为了避免R向单词查找树在空间上的过度消耗，产生了三向单词查找树。在三向单词查找树中，每个结点都含有一个字符，三条链接和一个值。这三条链接分别对应着当前字母小于、等于和大于节点字母的所有键。

三向单词查找算法实现查找和插入很简单。在查找时，我们首先比较键的首字母和根结点的字母，如果键的首字母较小，则选择左链接；如果较大，则选择右链接；如果相等，则选择中链接。然后，递归地使用相同的算法。如果遇到了一个空连接或当键结束之时结点值为空，则未命中，如果键结束时结点值非空，则命中。插入方法和R向单词查找树基本原理相同。

算法实现：

public class TST<Value> {
	private Node root;
	private class Node{
		char c;
		Node left,right,mid;
		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);
		if(c>x.c)	return get(x.right,key,d);
		else if(d<key.length()-1)	return get(x.mid,key,d);
		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;
	}
}

三向单词查找树性质：

• 由N个平均长度为w的字符串构造的三向单词查找树链接总数在3N~3Nw之间。
• 在一棵由N个随机字符串构成的三向单词查找树中，查找未命中平均需要比较字符~lnN次。除~lnN外，一次插入或命中的查找会比较一次被查找的键中的每一个字符。