[고급 자료구조] Tree: Trie

1. Trie 란?

• 문자열 탐색에 최적화된 트리 자료구조 입니다.
• 1959년 Edward Frendkin에 의해 처음 소개되었습니다.

 

2. 기능

사전 검색

• 완전한 단어나 문구를 입력하여 해당 단어를 찾아냅니다.

 

접두사 검색

• 뿌리부터 시작해서 각각의 가지가 알파벳 문자를 표현합니다.
  • 표시된 노드까지 문자열을 이루고 있음을 마크해둡니다. (각 단어가 끝나는 지점에 표시)

• 자동완성 기능을 구현할 수 있습니다.

 

3. 구현

public class MyTrie {
    class Node {    	
    	Map<Character, Node> children;
        boolean endOfWord;
        
        Node() {
            this.children = new HashMap<>();
            this.endOfWord = false;
        }
    }

    private Node root;

    public MyTrie() {
    	this.root = new Node();
    }

    public void insert(String word) {
    	insert(this.root, word, 0);
    }

    private void insert(Node node, String word, int idx) {
    	if (word.length() == idx) {
            node.endOfWord = true;
            return;
        }
    
    	char c = word.charAt(idx);
        
        if (!node.children.containsKey(c)) node.children.put(c, new Node());
        
        insert(node.children.get(c), word, idx+1);
    }

    public Node search(String word) {
    	return search(this.root, word, 0);
    }

    public Node search(Node node, String word, int idx) {
    	if (word.length() == idx) return node.endOfWord ? node : null;
        
    	char c = word.charAt(idx);
        Node child = node.children.get(c);
        
        return child != null ? search(child, word, idx+1) : null;
    }

    public List<String> autocomplete(String prefix) {
    	Node cur = this.root;
        
        for (char c : prefix.toCharArray()) {
            Node child = cur.children.get(c);
            if (child == null) return new ArrayList<>();
            
            cur = child;
        }
        
        return searchStartWith(cur, new StringBuffer(prefix));
    }

    private List<String> searchStartWith(Node node, StringBuffer prefix) {
    	List<String> result = new ArrayList<>();
        
        if (node.endOfWord) result.add(prefix.toString());
        
        for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
            prefix.append(entry.getKey());
            result.addAll(searchStartWith(entry.getValue(), prefix));
            prefix.setLength(prefix.length()-1);
        }
        
        return result;
    }
}

 

 

출처

• Wiki - Trie