欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

(数据结构):字典树 Trie

程序员文章站 2024-01-26 13:36:28
字典树 Trie【需求】如何判断一堆不重复的字符串是否以某个前缀开头?用Set\Map存储字符串遍历所有字符串进行判断时间复杂度 O(n)使用字典树处理。Trie简介Trie也叫做字典树、前缀树(Prefix Tree)、单词查找树Trie搜索字符串的效率主要跟字符串的长度有关示例:使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词注意单词结束是红色。接口设计public interface......

字典树 Trie

【需求】

  • 如何判断一堆不重复的字符串是否以某个前缀开头?
    • 用Set\Map存储字符串遍历所有字符串进行判断
    • 时间复杂度 O(n)
  • 使用字典树处理。

Trie简介

  • Trie 也叫做 字典树前缀树(Prefix Tree)单词查找树
  • Trie 搜索字符串的效率主要跟字符串的长度有关
  • 示例:使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词
    • 注意单词结束是红色。

(数据结构):字典树 Trie(数据结构):字典树 Trie

接口设计

(数据结构):字典树 Trie

public interface Trie <V> {
	int size(); 
	boolean isEmpty(); 
	void clear(); 
	boolean contains(String str); 
	V add(String str,V value); 
	V remove(String str); 
	boolean starswith(String prefix);
}

【代码实现】

/**
 * @author yusael
 * Trie 字典树
 */
public class Trie <V> {
	private int size;
	private Node<V> root;
	
	private static class Node<V>{
		Node<V> parent;
		HashMap<Character, Node<V>> children;
		Character character; // 为删除做准备
		V value;
		boolean word; // 是否为单词的结尾(是否为一个完整的单词)
		public Node(Node<V> parent) {
			this.parent = parent;
		}
	}
	
	public int size(){
		return size;
	}
	
	public boolean isEmpty(){
		return size == 0;
	}
	
	public void clear(){
		size = 0;
		root = null;
	}
	
	public V get(String key){
		Node<V> node = node(key);
		return (node!=null && node.word) ? node.value : null;
	}
	
	public boolean contains(String key){
		Node<V> node = node(key);
		return node!=null && node.word;
	}
	
	public V add(String key, V value){
		keyCheck(key);
		
		// 创建根节点
		if(root == null){
			root = new Node<>(null);
		}
		
		Node<V> node = root;
		int len = key.length();
		for(int i = 0; i < len; i++){
			char c = key.charAt(i);
			boolean emptyChildren = (node.children==null);
			Node<V> childNode = emptyChildren ? null : node.children.get(c);
			if(childNode == null){
				childNode = new Node<>(node);
				childNode.character = c;
				node.children = emptyChildren ? new HashMap<>() : node.children;
				node.children.put(c, childNode);
			}
			node = childNode;
		}
		
		if(node.word){ // 已经存在这个单词
			V oldValue = node.value;
			node.value = value;
			return oldValue;
		}
		
		// 新增一个单词
		node.word = true;
		node.value = value;
		size++;
		return null;
	}
	
	public V remove(String key){
		// 找到最后一个节点
		Node<V> node = node(key);
		// 如果不是单词结尾,不用作任何处理
		if(node==null || !node.word) return null;
		size--;
		V oldValue = node.value;
			
		// 如果还有子节点
		if(node.children!=null && !node.children.isEmpty()){
			node.word = false;
			node.value = null;
			return oldValue; 
		}
		
		// 没有子节点
		Node<V> parent = null;
		while((parent = node.parent) != null){
			parent.children.remove(node.character);
			if(parent.word || !parent.children.isEmpty()) break;
			node = parent;
		}
		return oldValue;
	}
	
	public boolean startsWith(String prefix){
		return node(prefix) != null;
	}
	
	/**
	 * 根据传入字符串,找到最后一个节点
	 * 例如输入 dog
	 * 找到 g
	 */
	private Node<V> node(String key){
		keyCheck(key);
		
		Node<V> node = root;
		int len = key.length();
		for(int i = 0; i < len; i++){
			if(node==null || node.children==null || node.children.isEmpty()) return null;
			char c = key.charAt(i);
			node = node.children.get(c);
		}
		return node;
	}
	
	private void keyCheck(String key){
		if(key==null || key.length()==0){
			throw new IllegalArgumentException("key must not be empty");
		}
	}
	
}

【测试】

public class Main {
	public static void main(String[] args) {
		Trie<Integer> trie = new Trie<>();
		trie.add("cat", 1);
		trie.add("dog", 2);
		trie.add("catalog", 3);
		trie.add("cast", 4);
		trie.add("小码哥", 5);
		System.out.println(trie.size() == 5);
		System.out.println(trie.startsWith("do"));
		System.out.println(trie.startsWith("c"));
		System.out.println(trie.startsWith("ca"));
		System.out.println(trie.startsWith("cat"));
		System.out.println(trie.startsWith("cata"));
		System.out.println(!trie.startsWith("hehe"));
		System.out.println(trie.get("小码哥") == 5);
		System.out.println(trie.remove("cat") == 1);
		System.out.println(trie.remove("catalog") == 3);
		System.out.println(trie.remove("cast") == 4);
		System.out.println(trie.size() == 2);
		System.out.println(trie.startsWith("小"));
		System.out.println(trie.startsWith("do"));
		System.out.println(!trie.startsWith("c"));
	}
}

总结

  • 优点:搜索前缀的效率主要跟前缀的长度有关
  • 缺点:需要耗费大量的内存,因此还有待改进
  • 更多Trie 相关的数据结构和算法:
    • Double-array Trie、Suffix Tree、Patricia Tree、Crit-bit Tree、AC自动机

 

本文地址:https://blog.csdn.net/baidu_41388533/article/details/110505914