字符串查找----三向单词查找树

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java学习网

Java中实现解码字符串的方法,实用代码

需求:给定一个经过编码的字符串,要求返回它的解码后的字符串。 编码规则是:k[str],这个编码的含义是str出现了k次,k是一个正整数。 具体例子: s = ...

30250
来自专栏琯琯博客

PHP 操作 Redis

Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。

21710
来自专栏mathor

Iterator

13140
来自专栏进击的君君的前端之路

面向对象、this

12730
来自专栏null的专栏

挑战数据结构与算法面试题——统计上排数在下排出现的次数

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 本题应该是一个确定的问题,即上排的是个数是题目中给定的...

33260
来自专栏noteless

-1-3 java集合框架基础 java集合体系结构 Collection 常用java集合框架 如何选择集合 迭代器 泛型 通配符概念 Properties 集合 迭代器

                        数组可以是基本类型,也可以是引用类型

13320
来自专栏IT可乐

Java关键字(四)——final

  对于Java中的 final 关键字,我们首先可以从字面意思上去理解,百度翻译显示如下:

10130
来自专栏函数式编程语言及工具

泛函编程(11)-延后计算-lazy evaluation

     延后计算(lazy evaluation)是指将一个表达式的值计算向后拖延直到这个表达式真正被使用的时候。在讨论lazy-evaluation之前...

21960
来自专栏小二的折腾日记

day5(面向对象2)

##set set:无序,不可以重复元素。 hashset:数据结构是哈希表,线程非同步的,保证元素唯一性的原理,判断元素的hashCode值是否相同。如果相同...

7130
来自专栏小灰灰

JDK容器学习之LinkedHashMap (一):底层存储结构分析

LinkedHashMap 底层存储结构分析 HashMap 是无序的kv键值对容器,TreeMap 则是根据key进行排序的kv键值对容器,而LinkedH...

21550

扫码关注云+社区

领取腾讯云代金券