提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
Trie 树又叫字典树、前缀树、单词查找树，是一种二叉树衍生出来的高级数据结构，主要应用场景是处理字符串前缀相关的操作
public class TrieMap<V> {
//ASCII码个数
private static final int R = 256;
//当前存在map中的键值对的个数
private int size = 0;
//Trie 树的根节点
private TrieNode<V> root = null;
//孩子节点(私有静态类)
private static class TrieNode<V>{
V val = null;
TrieNode<V>[] children = new TrieNode[R];
}
/**
* 从节点node开始搜索key如果存在则返回，不存在返回null(寻找的是节点)
* @param node
* @param key
* @return
*/
public TrieNode<V> getNode(TrieNode<V>node, String key){
TrieNode<V> p = node;
for (int i = 0; i < key.length(); i++) {
char c = key.charAt(i);
if (p == null){
return null;
}
p = p.children[c];
}
return p;
}
/**
* 获取key值对应的value
* @param key
* @return
*/
public V get(String key){
TrieNode<V> node = getNode(root,key);
if(node != null && node.val != null){
return node.val;
}
return null;
}
/**
* 判断是否存在key
* @param key
* @return
*/
public boolean containsKey(String key){
return get(key) != null;
}
/**
* 是否存在前缀为predix的键
* @param prefix
* @return
*/
public boolean hasKeyWithPrefix(String prefix){
return getNode(root,prefix) != null;
}
/**
* 在所有键中寻找query的最短前缀
* @param query
* @return
*/
public String shortestPrefixOf(String query){
TrieNode<V> p = root;
for (int i = 0; i < query.length(); i++) {
char c = query.charAt(i);
if(p == null){
return "";
}
if(p.val != null){
return query.substring(0,i);
}
p = p.children[c];
}
if (p != null && p.val != null){
return query;
}
return "";
}
/**
* 在所有键中寻找query最长前缀
* @param query
* @return
*/
public String longestPrefixOf(String query){
int maxLen = 0;
TrieNode<V> p = root;
for (int i = 0; i < query.length(); i++) {
if(p == null){
return "";
}
char c = query.charAt(i);
if(p.val != null){
maxLen = i;
}
p = p.children[c];
}
if (p != null && p.val != null){
return query;
}
return query.substring(0,maxLen);
}
/**
* 找到所以以prefix为前缀的字符串
* @param prefix
* @return
*/
public List<String> keysWithPrefix(String prefix){
List<String> res = new LinkedList<>();
TrieNode<V> node = getNode(root,prefix);
if (node == null){
return res;
}
traverse(node, new StringBuilder(prefix),res);
return res;
}
/**
* 遍历以node节点为根的Trie树，找到所有的键
* @param node
* @param sb
* @param res
*/
private void traverse(TrieNode<V> node, StringBuilder sb, List<String> res) {
if (node == null){
return;
}
if (node.val != null){
res.add(sb.toString());
}
for (char i = 0; i < R; i++) {
sb.append(i);
traverse(node.children[i],sb,res);
sb.deleteCharAt(sb.length() -1);
}
}
/**
* 匹配模式串pattern得到所有的key
* @param pattern
* @return
*/
public List<String> keysWithPattern(String pattern){
List<String> res = new LinkedList<>();
traverse(root, new StringBuilder(), pattern, 0, res);
return res;
}
/**
* 遍历函数，尝试在「以 node 为根的 Trie 树中」匹配 pattern[i..]
* @param node
* @param path
* @param pattern
* @param i
* @param res
*/
private void traverse(TrieNode<V> node, StringBuilder path, String pattern, int i, List<String> res) {
if (node == null){
return;
}
if (i == path.length()){
if (node.val != null){
res.add(path.toString());
}
return;
}
char ch = pattern.charAt(i);
if (ch == '.'){
for (char c = 0; c < R; c ++){
path.append(c);
traverse(node.children[c],path,pattern,i+1,res);
path.deleteCharAt(path.length()-1);
}
}else {
path.append(ch);
traverse(node.children[ch],path,pattern,i +1,res);
path.deleteCharAt(path.length()-1);
}
}
/**
* 判断是否存在模式串pattern
* @param pattern
* @return
*/
public boolean hasKeyWithPattern(String pattern){
return hasKeyWithPattern(root,pattern, 0);
}
/**
* 函数定义：从 node 节点开始匹配 pattern[i..]，返回是否成功匹配
* @param node
* @param pattern
* @param i
* @return
*/
private boolean hasKeyWithPattern(TrieNode<V> node, String pattern, int i) {
if (node == null){
return false;
}
if (i == pattern.length()){
if (node.val != null){
return true;
}
}
char ch = pattern.charAt(i);
if (ch == '.'){
for (char c = 0; c < R; c ++){
if (hasKeyWithPattern(node.children[ch],pattern, i +1)){
return true;
}
}
}else {
return hasKeyWithPattern(node.children[ch],pattern,i+1);
}
return false;
}
/**
* 在TrieMap中添加或者修改键值对
* @param key
* @param val
*/
public void put(String key, V val){
if (!containsKey(key)){
size ++;
}
root = put(root, key, val,0);
}
/**
* 定义：向以 node 为根的 Trie 树中插入 key[i..]，返回插入完成后的根节点
* @param node
* @param key
* @param val
* @param i
* @return
*/
private TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
if (node == null){
node = new TrieNode<>();
}
if (i == key.length()){
node.val = val;
return node;
}
char c = key.charAt(i);
node.children[c] = put(node.children[c],key,val,i+1);
return node;
}
/**
* 在 Map 中删除 key
* @param key
*/
public void remove(String key) {
if (!containsKey(key)) {
return;
}
// 递归修改数据结构要接收函数的返回值
root = remove(root, key, 0);
size--;
}
/**
* 定义：在以 node 为根的 Trie 树中删除 key[i..]，返回删除后的根节点
* @param node
* @param key
* @param i
* @return
*/
private TrieNode<V> remove(TrieNode<V> node, String key, int i) {
if (node == null) {
return null;
}
if (i == key.length()) {
// 找到了 key 对应的 TrieNode，删除 val
node.val = null;
} else {
char c = key.charAt(i);
// 递归去子树进行删除
node.children[c] = remove(node.children[c], key, i + 1);
}
// 后序位置，递归路径上的节点可能需要被清理
if (node.val != null) {
// 如果该 TireNode 存储着 val，不需要被清理
return node;
}
// 检查该 TrieNode 是否还有后缀
for (int c = 0; c < R; c++) {
if (node.children[c] != null) {
// 只要存在一个子节点（后缀树枝），就不需要被清理
return node;
}
}
// 既没有存储 val，也没有后缀树枝，则该节点需要被清理
return null;
}
}