트라이 (Trie)

Trie(트라이)는 문자열 검색을 위한 자료 구조 중 하나로, 문자열을 효율적으로 저장하고 빠르게 검색할 수 있다. Java에서는 Trie를 구현하기 위한 클래스를 제공하지는 않지만, 사용자가 직접 구현하여 사용할 수 있다.

Trie는 트리(Tree)의 형태를 띄며, 루트 노드부터 각 문자열의 각 글자를 표현하는 노드들이 연속적으로 이어져 있다. 따라서 문자열의 길이가 N인 경우, Trie의 높이는 최대 N이 된다.
이러한 Trie의 특성으로 인해 문자열 검색에 대한 속도가 빠르다는 장점이 있다.

Trie의 검색은 루트 노드부터 문자열의 각 글자에 해당하는 자식 노드들을 탐색하면서 문자열 전체를 탐색하는 방식으로 이루어진다. 따라서 검색 시간은 문자열의 길이에 비례하게 되고, 이러한 검색 방식으로 인해, Trie는 자동완성 기능 등에 많이 활용된다.

길이가 N인 문자열 탐색의 시간 복잡도 : O(N)

Trie의 구현 방법은 각 노드를 클래스로 정의하고, 각 노드가 자식 노드들을 가리키는 포인터를 가지도록 구현하면 된다. 검색할 문자열을 입력받으면 루트 노드부터 시작하여 문자열의 각 글자에 해당하는 자식 노드를 탐색하면서 검색을 수행한다.

Java에서 Trie를 구현하려면, 문자열을 저장할 Node 클래스와 Trie 클래스를 구현하고, 문자열의 검색, 삽입, 삭제 등의 연산을 구현하면 된다.

트리의 기본구조

기본적인 Trie 소스코드

import java.util.HashMap;

public class Trie {
    private TrieNode root;

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

    // 문자열을 Trie 구조에 삽입하는 메서드
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.computeIfAbsent(c, k -> new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
    }

    // Trie 구조 내에 주어진 문자열이 존재하는지 확인하는 메서드
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    // 주어진 prefix로 시작하는 문자열이 Trie 구조 내에 존재하는지 확인하는 메서드
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }

    // 주어진 문자열을 Trie 구조에서 삭제하는 메서드
    public boolean delete(String word) {
        TrieNode node = root;
        TrieNode lastMatch = null;
        char lastMatchChar = 0;

        // 문자열의 각 문자를 순회하며 Trie 구조에서 삭제할 문자열을 탐색
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return false; // Trie에 word가 없으면 삭제할 수 없음
            }
            if (node.children.size() > 1 || node.isEnd) {
                lastMatch = node;
                lastMatchChar = c;
            }
            node = node.children.get(c);
        }
        if (!node.isEnd) {
            return false; // Trie에 word가 없으면 삭제할 수 없음
        }

        // 삭제할 문자열의 마지막 노드를 찾은 경우, 마지막 노드의 isEnd 값을 false로 변경하고 word를 삭제하지 않음
        if (node.children.size() > 0) {
            node.isEnd = false;
            return true;
        }

        // 삭제할 문자열의 마지막 노드가 다른 문자열의 마지막 노드이면서 자식 노드가 없는 경우, word의 마지막 문자와 lastMatch 노드를 제거함
        if (lastMatch != null) {
            lastMatch.children.remove(lastMatchChar);
            return true;
        }

        // Trie에 word만 존재하고 다른 문자열과 겹치지 않는 경우, word 전체를 삭제함
        root.children.remove(word.charAt(0));
        return true;
    }

    // 주어진 문자열의 prefix를 탐색하여 마지막 노드를 반환하는 메서드
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return null;
            }
        }
        return node;
    }

    // Trie 구조의 노드를 나타내는 클래스
    private static class TrieNode {
        HashMap<Character, TrieNode> children = new HashMap<>(); // 자식노드를 저장하는 해시맵
        boolean isEnd; // 해당 노드가 문자열의 끝을 나타내는 노드인지 나타내는 변수
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("april");
        trie.insert("app");
        trie.insert("ace");
        trie.insert("bear");
        trie.insert("best");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("april"));
        System.out.println(trie.search("app"));
        System.out.println(trie.search("ace"));
        System.out.println(trie.search("bear"));
        System.out.println(trie.search("best"));
        System.out.println(trie.search("beat"));        
        System.out.println(trie.search("abc"));

        System.out.println();
        trie.delete("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("april"));
        System.out.println(trie.search("appl"));
    }
}