트라이 (Trie)

개요

1. Trie란?
2. LeetCode 208번 문제 - Implement Trie (Prefix Tree)

 

 

1.  Trie란?

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조이다.

Trie라고 적고 try로 발음되며, 다른 말로는 래딕스 트리(Radix Tree), 접두사 트리(Prefix Tree), 또는 탐색 트리(Retrieval Tree)라고도 한다. 

 

우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화된 자료구조이며,

디테일한 설명은 박지훈님이 작성한 [자료구조] 트라이(Trie)를 참고하자.

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

 

트라이 자료구조는 대표적으로 검색 기능의 자동완성, 워드와 같은 문서 입력의 문법 체크 기능, 또는 IP 라우팅에 활용된다고 한다.

검색 엔진의 자동 완성에 활용되는 자료구조

 

 

2.  LeetCode 208번 문제 - Implement Trie (Prefix Tree)

해당 문제를 풀다가 Trie 자료 구조를 처음 접하게됐다.

처음 문제를 풀때는 막연하게 HsahSet으로 로직을 구현했는데, 통과는 했지만 시간 복잡도가 비효율적으로 나왔다.

class Trie {
    private Set<String> trie;

    public Trie() {
        trie = new HashSet<>();    
    }
    
    public void insert(String word) {
        trie.add(word);
    }
    
    public boolean search(String word) {
        return trie.contains(word);
    }
    
    public boolean startsWith(String prefix) {
        for (String str : trie) {
            if (str.startsWith(prefix))
                return true;
        }

        return false;
    }
}

 

입력값의 조건이 1 <= word.length, prefix.length <= 2000으로 명시되어있다보니 어찌저찌 통과는 되겠지만,

실제 검색 엔진에서 HashSet으로 막연하게 값을 저장할리는 없다. 메모리가 무한대도 아닐테니 말이다.

 

이 참에 Trie 자료구조를 공부하기 위해 Editorial을 참고해서 TrieNode를 구현해 로직을 작성했다.

 

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++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }
    
    public TrieNode searchPrefix(String word) {
        TrieNode node = root;
        
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }

        return node;
    }

    public boolean search(String word) {
       TrieNode node = searchPrefix(word);
       return node != null && node.isEnd();
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}

class TrieNode {

    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch -'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }
}

 

결론적으로 Runtime이 개선됐다.