字符串查找----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的技术栈

自己动手写一个单链表

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

2176
来自专栏WD学习记录

牛客网 从上往下打印二叉树

711
来自专栏mukekeheart的iOS之旅

Java基础——集合框架

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

2576
来自专栏恰同学骚年

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

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

691
来自专栏郭耀华‘s Blog

Java集合框架(五)—— Map、HashMap、Hashtable、Properties、SortedMap、TreeMap、WeakHashMap、IdentityHashMap、EnumMap

Map Map用于保存具有映射关系的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另一组值用于保存Map里的value,key和v...

2897
来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

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

44911
来自专栏用户画像

HashSet和HashMap的区别 && HashTable和HashMap的区别

2.Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。

913
来自专栏Java后端技术栈

初探Java源码之LinkedList

上篇文章我们分析了常见的ArrayList源码,它的内部是由一个数组来实现的。那么今天,我们来分析另一个常见的类LinkedList。本文分析都来自Java8。...

1202
来自专栏JavaNew

Java集合:整体结构

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

LeetCode-49-Group-Anagrams

输入一个字符串数组,输出的是:将相同字符的字符串放在一个数组的二维数组。相同字符的处理,基本就是要对字符串排序的。然后需要考虑的就是排序好的那一个字符串怎么存的...

701

扫码关注云+社区