字符串查找----三向单词查找树
为了避免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外，一次插入或命中的查找会比较一次被查找的键中的每一个字符。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.01.25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读