트라이 (Trie) - JAVA 구현

Trie 란?

• 문자열을 저장하는데 자주 사용되는 트리 구조
• 효율적인 탐색을 가능하게한다
• 자동 완성 기능, 사전 검색 등에서 사용된다
• 예) 문자열 high검색: (root node) -> h -> i -> g -> h 순서로 도달 (존재) + 해당 노드는 EOW (end of word) true (단어임) ==> 검색 완료

 

Trie의 장단점

장점

• 빠른 탐색: Trie의 검색 속도는 O(M)으로 매우 빠르며, 원소 유무를 검사할 때 자주 사용되는 이진 검색 트리 (Binary Search Tree)의 O(MlogN)에 비해서도 더 빠른 속도를 보인다.
  • M: 검색 문자열 길이
  • N: 노드 수
    • **Binary Search Tree의 원소 검색 수는 O(logN)이나, 문자열 검색의 경우 두 문자열의 비교를 위해 각각 M만큼의 시간이 추가로 걸린다.
• 빠른 삽입: 삽입의 경우에도 길이 M만큼 node를 따라 내려가며 node를 추가하거나 EOW 표시등 만을 하면 되기 때문에 이 또한 O(M)의 시간안에 가능하다.

단점

• 크기가 크다: 각 노드마다 필요한 포인터의 갯수가 매우 많기 때문에 저장 공간이 많이 필요한 자료구조이다. 검색 속도보다 저장 공간이 더 중요시 되는 경우에는 trie대한 ternary search tree를 사용하기도 한다.
  • Ternary Seach Tree의 검색속도는 O(h)이며 h는 tree의 heigh를 나타낸다.

구현 (Java)

Node

변수:

• Map<Character, Node> childNodes: 각 child node의 character을 key로, 실제 Node 객체를 value로 가지고있는 hashMap으로, hashMap을 사용함으로인해 필요한 character에만 메모리를 할당하여 메모리 절약하는 장점과 검색시간이 O(1)로 매우 짧다는 장점을 가지고있다.
• boolean endOfWord: 현재 Node가 단어의 마지막 character인지 표시하는 boolean. 위의 사진에서는 빨간색으로 표시되어 있는 Node들의 endOfWord값이 true로 설정되어있다.

class Node {
    Map<Character,Node> childNodes = new HashMap<>();
    boolean endOfWord;
}

Trie 생성, 삽입, 검색

public class Trie {
    Node rootNode;
    
    public void init() {
        rootNode = new Node(); //루트 노드 생성
    }
 
    public void insert(String str) {
        Node node = this.rootNode; //루트 노드에서 시작
        for(int i=0;i<str.length();i++) {
            //childNodes에 해당 key가 없다면 생성
            node = node.childNodes.computeIfAbsent(str.charAt(i), key->new Node());
        }
        node.endOfWord = true;
    }
 
    public boolean query(String str) {
        Node node = this.rootNode; //루트 노드에서 시작
 
        for(int i=0; i<buffer_size; i++) {
            //childNodes에 해당 key가 없다면 default(null)로 설정
            node = node.childNodes.getOrDefault(buf.charAt(i), null);
            if(node == null) {
                return false;	//null이라면 존재하지 않는 것이니 false 리턴
            }
        }
        
        return node.endOfWord; //해당 str이 완벽한 단어인지 리턴
        
        //만약 완벽한 단어가 아니더라도 str의 존재 여부만 알고 싶다면
        //return true;
    }
}

문제 예제

https://juyoungpang.tistory.com/25

[SWEA] (java) 문제 3135 - Trie