package com.yan.algorithm.string;
import java.util.LinkedList;
import java.util.Queue;
public class TrieTree {
private static int R = 256;
private Node root = new Node();
private class Node {
private Node[] next = new Node[R];
private Object value;
}
/**
* add value to trie tree
* @param key
* @param value
*/
public void put(String key, Object value) {
root = put(root, key, value, 0);
}
private Node put(Node x, String key, Object value, int d) {
if (x == null)
return null;
if (key.length() == d)
return x;
char c = key.charAt(d);
x.next[c] = put(x.next[c], key, value, d + 1);
return x;
}
/**
* search value by key
* @param key
* @return
*/
public Node get(String key) {
return get(root, key, 0);
}
private Node get(Node x, String key, int d) {
if (x == null)
return null;
if (key.length() == d)
return x;
char c = key.charAt(d);
return get(x.next[c], key, d + 1);
}
/**
* remove value from trie tree by key
* @param key
*/
public void remove(String key) {
root = remove(root,key,0);
}
/**
* delete one element from trie tree
* @param x
* @param key
* @param d
* @return
*/
private Node remove(Node x, String key, int d) {
if(x == null) return null;
if(key.length()==d) {
x.value = null;
} else {
char c = key.charAt(d);
x.next[c] = remove(x.next[c],key,d+1);
}
if(x.value != null) return x;
for(char e = 0;d<R;d++) {
if(x.next[e] != null)
return x;
}
return null;
}
private void collect(Node x, String pre,Queue<String> q) {
if(x == null) return;
if(x.value != null) q.add(pre);
for(char c=0;c<R;c++) {
collect(x.next[c],pre+c,q);
}
}
/**
* get all keys which start with pre
*/
public Iterable<String> keysWithPrefix(String pre) {
Queue<String> q = new LinkedList<String>();
collect(root,pre,q);
return q;
}
/**
* get all keys
*/
public Iterable<String> keys() {
return keysWithPrefix("");
}
/**
* return a key which is the longest prefix of a string
* @param str
* @return
*/
public String longPrefixOf(String str) {
return str.substring(0,search(root,0,0,str));
}
private int search(Node x,int d,int length,String str) {
if(x == null) return length;
if(x.value != null) length = d;
if(d == str.length()) return length;
char c = str.charAt(d);
return search(x.next[c],d+1,length,str);
}
}
分享到:
相关推荐
C#,单词查找树(Trie Tree)的插入与搜索算法与源代码 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统...
trie - 单词查找树实现Go实现,极快的前缀/模糊字符串搜索的数据结构和相关算法
[原网页] 程序员编程艺术第三十~三十一章:字符串转换成整数,通配符字符串匹配 [原网页] 程序员编程艺术第二十八~二十九章:最大连续乘积子串、字符串编辑距离 [原网页] 数据挖掘中所需的概率论与数理统计知识、...
Patricia Tree 简称PAT tree。 它是 trie 结构的一种特殊形式。是目前信息检索领域应用十分成功的索引方法,...其算法中最突出的特点就是采用半无限长字串(semi-infinite string 简称 sistring) 作为字符串的查找结构
字符串包含算法 StringContains 20160622 字典树 trietree 20160624 KMP算法 KMP 20160701 排序算法,插入排序算法、合并排序算法 sort 20160702 MongoDB应用示例 mongoDBDemo 20160703 Redis的java应用示例 ...
| 最短公共祖先(多个短字符串) 33 Geometry 计算几何 34 | GRAHAM 求凸包 O(N * LOGN) 34 | 判断线段相交 34 | 求多边形重心 34 | 三角形几个重要的点 34 | 平面最近点对 O(N * LOGN) 34 | LIUCTIC 的...
字符串hash 堆 二维树状数组 Trie树 二叉查找树 线段树 RMQ LCA+RMQ SB-Tree 数论 生成紧凑素数表 分解质因子 最大公约数 a^b mod n 扩张欧几里德算法 素数表质因子分解 Stirling公式 中国剩余定理...
字符串匹配算法 Deliberate practicing 刻意练习。刻意地,反复地练习相关领域的知识点。在初期地时候,它可能带给你的直接感受是:不舒服、不爽、枯燥,但是只要能够坚持下来长期练习,必定能够获得成功。 Feedback...
###字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 ###图的算法 图的存储结构和基本操作(建立,遍历,删除节点,添加节点) 最小生成树 拓扑排序 关键路径 最短路径: Floyd,Dijkstra,bellman-...
字符串匹配(KMP) Knuth-Morris-Pratt 最小生成树(Kruskal) Kruskal 最近公共祖先(Tarjan) Least-Common-Ancestor(Tarjan) 使用后缀数组求解最长公共子串 Longest-Common-Substring 最长上升子序列(n·log...
字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 二叉树 二叉树 二叉查找树 伸展树(splay tree 分裂树) 平衡二叉树AVL 红黑树 B树,B+,B* R树 Trie树(前缀树) 后缀树 最优二叉树(赫夫曼树) 二叉堆 ...
字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 二叉树 二叉树 二叉查找树 伸展树(splay tree 分裂树) 平衡二叉树AVL 红黑树 B树,B+,B* R树 Trie树(前缀树) 后缀树 最优二叉树(赫夫曼树) 二叉堆 ...
字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 树 二叉树 二叉查找树 伸展树(splay tree 分裂树) 平衡二叉树AVL 红黑树 B树,B+,B* R树 Trie树(前缀树) 后缀树 最优二叉树(赫夫曼树) 二叉堆 ...
字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 二叉树 二叉树 二叉查找树 伸展树(splay tree 分裂树) 平衡二叉树AVL 红黑树 B树,B+,B* R树 Trie树(前缀树) 后缀树 最优二叉树(赫夫曼树) 二叉堆 ...
字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 二叉树 二叉树 二叉查找树 伸展树(splay tree 分裂树) 平衡二叉树AVL 红黑树 B树,B+,B* R树 Trie树(前缀树) 后缀树 最优二叉树(赫夫曼树) 二叉堆 ...
字符串算法 BF算法 KMP算法 BM算法 图的算法 图的存储结构和基本操作(建立,遍历,删除节点,添加节点) 最小生成树 拓扑排序 关键路径 最短路径: Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换...
字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 二叉树 二叉树 二叉查找树 伸展树(splay tree 分裂树) 平衡二叉树AVL 红黑树 B树,B+,B* R树 Trie树(前缀树) 后缀树 最优二叉树(赫夫曼树) 二叉堆 ...
字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 树 二叉树 二叉查找树 伸展树(splay tree 分裂树) 平衡二叉树AVL 红黑树 B树,B+,B* R树 Trie树(前缀树) 后缀树 最优二叉树(赫夫曼树) 二叉堆 ...
数组/字符串(Array/String) 链表(Linked-list) 栈(Stack) 队列(Queue) 双端队列(Deque) 树(Tree) 哈希表 高级数据结构 优先队列(Priority Queue) 图(Graph) 前缀树(Trie) 线段树(Segment Tree) ...