字符串查找----R向单词查找树
字符串查找----R向单词查找树
SuperHeroes
发布于 2018-05-30 18:00:22
发布于 2018-05-30 18:00:22
代码可运行
运行总次数：0
代码可运行
单词查找树的数据结构就是一种树型结构，它由字符串键中所有字符构造而成，允许使用被查找键中的字符进行查找。
先来看一下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;
}单词查找树的性质：
- 单词查找树的链表结构和插入或删除的顺序无关，对于给定的任意一组键，其单词查找树都是唯一的。
- 在单词查找树中插入或查找一个键时，访问数组的次数最多为键的长度加一。
- 字母表的大小为R，在一棵由N个键构造的单词查找树中，未命中查找平均所需检查的数量为~(logR)N。
- 一棵单词查找树中链接总数在RN到RNw之间，其中w为键的平均长度。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018.01.25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
