为了避免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外,一次插入或命中的查找会比较一次被查找的键中的每一个字符。