[자료구조] Trie(트라이)

1. Trie(트라이)란?

---

다음과 같은 문자열 집합이 있습니다.
S = {"HE", "HELLO", "WORLD", "SHE"}

 

위 문자열 집합에 "SHE"라는 문자열이 포함되어 있는지 확인하고 싶다면 어떻게해야 할까요? 🤔

Naive한 방법으로는 이중 반복문으로 일일이 비교하는 방법이 있습니다. 문자열 집합의 갯수를 N, 문자열의 최대길이를 M이라고 했을 때,
이 방법의 시간 복잡도는 O(NM)입니다.

 

Trie는 문자열 집합에서 특정 문자열이 존재하는지 찾을 때 O(M)의 시간 복잡도로 해결할 수 있습니다.
Trie는 문자열을 트리의 형태로 자료구조화하는 자료구조입니다. 위 문자열 집합을 Trie로 표현하면 다음과 같습니다.

[그림 1] 문자열 집합을 Trie로 자료구조화했을 때의 형태

이해가 되시나요? 
위 트리에서 빨간색 테두리로 된 노드는 문자열의 마지막 지점을 의미합니다.
이것이 필요한 이유는 "HE", "HELLO" 와 같이 앞의 문자가 중복되는 문자열을 위해서인데요, 문자열 집합에서 "HE"라는 문자열이 있는지 확인해야한다고 해보겠습니다. 그럼 탐색 과정은 다음과 같습니다.

1. root에서부터 시작해서 child 노드 중 H를 가지는 노드가 있는지 찾습니다.
2. 찾았다면, H를 가지는 노드로 이동합니다. (없다면 return해서 해당 문자가 없다고 해주면 되겠죠? 🙂 )
3. child 노드로 E를 가지는 노드가 있는지 찾습니다.
4. 찾았다면, 해당 E가 문자열의 끝임을 알리는 flag값이 설정되어 있는지 확인합니다.
5. 설정되어 있다면, 문자열 집합에 해당 문자열이 존재하는 것임을 알 수 있습니다.

트리를 구현할 줄 아신다면, 코드는 그리 어렵지 않게 구현하실 수 있으실 겁니다. 

public class TrieTest {

    public static void main(String[] args) {
        String[] strArr = {"HE", "HELLO", "WORLD", "SHE"};
        Trie trie = new Trie();
        for (String str : strArr) {
            trie.insert(trie.root, str, 0);
        }

        System.out.println(trie.contains(trie.root, "HELLO", 0));
    }

    private static class Trie {

        private Node root = new Node();

        public void insert(Node head, String str, int idx) {
            int charIdx = str.charAt(idx) - 65;
            if (head.child[charIdx] == null) {
                head.child[charIdx] = new Node();
            }
            if (idx == str.length() - 1) {
                head.child[charIdx].finish = true;
            } else {
                insert(head.child[charIdx], str, idx + 1);
            }
        }

        public boolean contains(Node head, String str, int idx) {
            int charIdx = str.charAt(idx) - 65;
            if (head.child[charIdx] == null) {
                return false;
            }
            if (idx == str.length() - 1) {
                return head.child[charIdx].finish;
            }
            return contains(head.child[charIdx], str, idx + 1);
        }

        private static class Node {
            Node[] child = new Node[26];
            boolean finish = false;
        }
    }
}