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

📋 목차

• Trie 자료구조란?
• Trie 장/단점
• Trie 코드 구현
• Trie 관련 알고리즘 문제

 

1️⃣ Trie 자료구조란?

• 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 자료구조이다.
• 우리가 원하는 원소를 찾는 작업을 O(n)에 해결 할 수 있는 자료구조이다. 여기서 n은 문자열의 길이입니다.
• 루트 노드가 되는 가장 최상위 노드에는 어떠한 단어도 들어가지 않고, 루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다.

💡우리가 사전에서 단어를 찾을 때와 비슷한 메커니즘입니다. 한 글자씩 찾아가며 문자열에 도달합니다.

2️⃣ Trie 장단점

• 트라이(Trie)는 문자열 검색을 빠르게 한다.
• 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다.
• 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다. (메모리 측면에서 비효율적일 수 있음!)

→ 트라이의 치명적 단점은 공간 복잡도에서 나타난다.

→ 그 이유는 트라이에서 시간복잡도가 문자열의 길이만큼 나오기 위해서는 다음 문자를 가리키는 노드가 필요하다.

 

문자열이 모두 영소문자로 이루어져 있다고 해도, 자식 노드를 가리키는 26개의 포인터를 저장해야 한다. 최악의 경우에는 집합에 포함되는 문자열들의 길이의 총합만큼 노드가 필요하므로, 총 메모리는 O(포인터 크기 * 포인터 배열 개수 * 총 노드의 개수)가 된다.

 

트라이에서 메모리를 절약하기 위한 트리플 어레이트리(triple-array trie)와 같은 여러 기법들이 개발되어 있지만 이들은 코테나 알고리즘 대회에 사용하기에는 너무 복잡하고 작성하는데 오래 시간이 걸리는 경우가 대부분이다. 때문에 대회에서 트라이를 쓸 수 있는 경우는 다루는 문자열의 개수가 그렇게 많지 않은 경우로 제한된다.

 

참고) 실제로 카카오 코테의 효율성 문제에서 트라이(Trie)를 사용하는 문제가 나왔는데 전체 문자열의 길이를 10,000으로 제한을 뒀다.

 

3️⃣ Trie 코드 구현

[문자열 집합을 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;
        }
    }
}

 

4️⃣ Trie 관련 알고리즘 문제

• 백준 5052번 전화번호 목록
• 백준 14425번 문자열 집합

---

🌐 참고 링크

[알고리즘/ 자료구조] 트라이(Trie) 문자열 탐색 트리 개념 정리 (Java)

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

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

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