Trie (트라이)

Trie의 주요 특징

• 문자 기반 트리: 각 노드는 문자를 저장하며, 루트 노드에서부터 각 문자 노드를 따라가면서 문자열을 구성합니다.
• 공유된 경로: 문자열의 공통된 접두사를 공유하므로 메모리를 절약할 수 있습니다.
• 효율적인 검색: 단어 검색, 삽입, 삭제가 매우 빠릅니다. 검색 시간은 문자열의 길이에 비례합니다.

Trie의 구조

• 노드(Node): 각 노드는 하나의 문자 또는 값(보통은 문자)을 저장하며, 자식 노드들을 가리킵니다.
• 루트 노드: 트리의 최상위 노드로, 빈 값(또는 특별한 값)을 가집니다.
• 자식 노드: 각 노드는 여러 자식 노드를 가질 수 있으며, 자식 노드는 다른 문자로 이어지는 경로를 나타냅니다.
• 종료 표시(End of Word): 노드에는 단어가 끝나는지 여부를 표시하는 플래그가 있을 수 있습니다. 이 플래그를 통해 트라이가 저장한 문자열이 해당 위치에서 끝나는지 확인할 수 있습니다.

삽입 및 검색 성능

• 삽입 및 검색 시간 복잡도: 문자열의 길이를 L이라고 할 때, Trie에서 삽입 및 검색은 **O(L)**입니다. 즉, 문자열의 길이에 비례한 시간이 소요됩니다.
• 접두사 검색: Trie는 접두사 검색에 최적화되어 있어, 특정 접두사로 시작하는 모든 단어를 빠르게 찾을 수 있습니다. 이는 해시 테이블로는 할 수 없는 작업입니다.

메모리 사용

• 메모리 효율성: Trie는 메모리를 많이 사용합니다. 특히 저장하는 문자열이 많을수록 각 문자를 노드로 분리하여 저장하므로, 공간 복잡도가 커집니다. 그러나 문자열들 사이에 공통된 접두사가 많을 경우, 이 접두사를 공유하므로 일부 메모리를 절약할 수 있습니다.
• 공통 접두사 공유: 공통 접두사들은 메모리를 공유하므로, 같은 접두사를 가진 단어들이 많을 때는 오히려 공간 효율이 좋아질 수 있습니다.

Trie 구현

class TrieNode {
    TrieNode[] children = new TrieNode[26]; // 알파벳 소문자 26개
    boolean isEndOfWord; // 해당 노드가 단어의 끝인지 여부

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = null;
        }
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // 문자열 삽입
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a'; // 'a'를 기준으로 인덱스 계산
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    // 문자열 검색
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node != null && node.isEndOfWord;
    }

    // 접두사 검색
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

Trie vs. Hash Table

Trie의 장점

• 접두사 검색 최적화: Trie는 접두사 기반 검색에 매우 유리합니다. 예를 들어, 자동 완성 기능이나 사전에서 특정 접두사로 시작하는 단어를 찾는 데 적합합니다.
• 순서 보존: 트라이 구조는 문자 순서를 보존하므로, 특정 순서에 따른 정렬된 데이터를 쉽게 관리할 수 있습니다.

Trie의 단점

• 메모리 사용량: 문자열이 많아질수록 트라이의 노드 수가 증가하고, 메모리 사용이 커집니다. 특히, 저장할 단어들의 접두사가 공통된 부분이 없을 경우에는 비효율적일 수 있습니다.
• 속도: 해시 테이블과 비교했을 때 문자열의 길이에 따라 검색 속도가 느릴 수 있습니다.

Hash Table의 장점

• 빠른 검색과 삽입: 해시 테이블은 평균적으로 O(1)의 시간 복잡도로 매우 빠른 검색 및 삽입 성능을 제공합니다. 이로 인해 문자열 검색이 필요한 대부분의 일반적인 경우에 더 효율적일 수 있습니다.
• 효율적인 메모리 사용: 해시 테이블은 문자열 전체를 저장하지만, 메모리 사용량은 보통 트라이보다 효율적입니다.

Hash Table의 단점

• 접두사 검색 비효율: 해시 테이블은 접두사 기반 검색이 불가능하며, 모든 키를 검사해야 하므로 비효율적입니다.
• 해시 충돌: 충돌이 발생하면 성능이 저하될 수 있으며, 해시 함수가 적절하지 않으면 최악의 경우 O(n)까지 성능이 떨어질 수 있습니다.

언제 Trie가 Hash Table보다 더 좋은가?

• 접두사 검색이 빈번한 경우: 예를 들어, 자동 완성 기능을 구현하거나 사전에서 특정 접두사로 시작하는 단어를 찾을 때 Trie가 유리합니다.
• 정렬된 데이터를 다룰 때: 트라이는 알파벳 순서대로 데이터를 저장할 수 있어, 자동으로 정렬된 결과를 얻는 것이 가능합니다.

언제 Hash Table이 더 좋은가?

• 단순한 검색과 삽입: 검색 및 삽입만 필요하고 접두사 검색이 필요하지 않은 경우 해시 테이블이 더 빠르고 메모리 효율적일 수 있습니다.
• 데이터 크기가 크고, 검색이 빈번한 경우: 큰 데이터를 다루면서 접두사 검색이 필요하지 않다면 해시 테이블이 성능 면에서 더 나을 수 있습니다.