Trie 자료구조

Trie(트라이)는 문자열 검색에 효과적인 자료 구조로, 특히 사전 검색이나 자동 완성 기능 등에 자주 사용된다.

이 자료 구조는 각 노드가 문자 하나를 나타내며, 각 노드 사이의 연결은 문자열의 일부를 나타낸다. Trie는 문자열 검색에 뛰어난 성능을 보이는데, 검색 시간은 문자열의 길이에 선형적으로 비례한다. 즉, O(문자열의 길이) 의 시간 복잡도를 갖는다.

 

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMa<>();
    }
}

class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        return searchNode(prefix) != null;
    }

    private TrieNode searchNode(String str) {
        TrieNode node = root;
        for (char c : str.toCharArray()) {
            if(node.children.get(c) == null){
                return null;
            }
            node = node.children.get(c);
        }
        return node;
    }
}

// 사용 예제
public class TrieExample {
    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("app"));     // false
        System.out.println(trie.startsWith("app")); // true

        trie.insert("app");
        System.out.println(trie.search("app"));     // true
    }
}