Trie

시간복잡도(N : 문자열의 길이) : O(N)

• 개요

  • 문자 단위로 Tree의 하위로 내려가며 추가한다.

  • 문자열의 마지막에 도달하면 해당 글자가 문자열의 끝이라는 표시를 한다

    static class TrieNode {
    				private Map<Character, TrieNode> childNodes = new HashMap<>();
    				private boolean isLast;
    
    				public Map<Character, TrieNode> getChildNodes() {
    					return childNodes;
    				}
    
    				public boolean isLast() {
    					return isLast;
    				}
    
    				public void setLast(boolean last) {
    					isLast = last;
    				}
    			}
    
    			static class Trie {
    				private TrieNode root;
    
    				Trie() {
    					root = new TrieNode();
    				}
    
    				void insert(String word) {
    					TrieNode node = this.root;
    					for (int i = 0; i < word.length(); i++) {
    						node = node.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
    					}
    					node.setLast(true);
    				}
    
    				boolean contains(String word) {
    					TrieNode node = this.root;
    					char cur;
    					for (int i = 0; i < word.length(); i++) {
    						cur = word.charAt(i);
    						if (!node.getChildNodes().containsKey(cur))
    							return false;
    						node = node.getChildNodes().get(cur);
    					}
    					return node.isLast();
    				}
    
    				void delete(String word) {
    					delete(this.root, word, 0);
    				}
    
    				private void delete(TrieNode node, String word, int index) {
    					if (index == word.length()) {
    						if (!node.isLast())
    							throw new Error("not exist");
    						node.setLast(false);
    						return;
    					}
    					char cur = word.charAt(index);
    					if (!node.getChildNodes().containsKey(cur))
    						throw new Error("not exist");
    					TrieNode child = node.getChildNodes().get(cur);
    					delete(node.getChildNodes().get(cur), word, index + 1);
    					if (child.getChildNodes().isEmpty()) {
    						if (!child.isLast())
    							node.getChildNodes().remove(cur, child);
    					}
    				}
    			}