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

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

先来看一下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;
}

单词查找树的性质

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

10610
来自专栏Android开发小工

Java集合解惑

本文取自工匠若水的qq群里的Java基础题目,把里面有关Java集合放在一起。 全文github地址

14920
来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头...

471110
来自专栏JavaNew

Java集合:整体结构

29360
来自专栏码云1024

List Set Map比较

35740
来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

46060
来自专栏小勇DW3

ArrayList在foreach删除倒数第二个元素不抛并发修改异常的问题

平时我们使用ArrayList比较多,但是我们是否知道ArrayList在进行foreach的时候不能直接通过list的add或者move方法进行删除呢,

23630
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

29860
来自专栏恰童鞋骚年

剑指Offer面试题:12.在O(1)时间删除链表结点

  在单向链表中删除一个结点,最常规的做法无疑是从链表的头结点开始,顺序遍历查找要删除的结点,并在链表中删除该结点。这种思路由于需要顺序查找,时间复杂度自然就是...

8410
来自专栏mukekeheart的iOS之旅

Java基础——集合框架

  Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

29060

扫码关注云+社区

领取腾讯云代金券