[java] 트라이 알고리즘

04 Dec 2023

java

트라이 알고리즘은 문자열 집합을 효율적으로 저장하고 검색하는 데 사용되는 자료구조입니다. 트라이는 트리의 형태를 가지고 있으며, 각 노드는 문자를 가리키는 포인터들을 가지고 있습니다.

트라이의 동작 원리

트라이의 루트 노드는 아무런 문자를 가리키지 않습니다.
문자열의 문자들을 하나씩 트라이에 삽입합니다.
각 문자마다 해당 문자를 가리키는 자식 노드가 있는지 확인합니다.
- 자식 노드가 있다면, 해당 자식 노드로 이동합니다.
- 자식 노드가 없다면, 새로운 노드를 생성하여 현재 노드의 자식으로 연결합니다.
문자열의 마지막 문자까지 위 과정을 반복한 후, 마지막 노드에는 해당 문자열의 종료 여부를 표시합니다.

트라이의 장점과 활용

트라이 알고리즘은 다음과 같은 장점을 가지고 있습니다.

문자열 검색을 빠르게 수행할 수 있습니다. 루트에서부터 시작하여 문자열의 모든 문자를 검색하는 과정에 걸리는 시간은 문자열의 길이와 상관없이 일정합니다.
중복된 문자열을 저장하지 않아도 됩니다. 각 노드는 문자를 가리키는 포인터들을 가지고 있으므로, 중복된 문자열이 존재하는 경우 공간을 절약할 수 있습니다.
문자열의 접두사를 효율적으로 찾을 수 있습니다. 트라이는 접두사를 표현하는데 효과적이며, 이를 활용하여 자동 완성 기능 등을 구현할 수 있습니다.

트라이 알고리즘은 문자열 검색이 많이 필요한 애플리케이션에서 활용될 수 있습니다. 예를 들어, 오타 교정, 검색 엔진, 문자열 매칭 등의 분야에서 효과적으로 사용될 수 있습니다.

예시 코드

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // 알파벳 개수에 맞게 배열 크기 설정
        isEndOfWord = false;
    }

    public void insert(String word) {
        TrieNode current = this;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // 알파벳의 인덱스 계산
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true; // 문자열의 끝을 표시
    }

    public boolean search(String word) {
        TrieNode current = this;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false; // 문자열이 트라이에 존재하지 않음
            }
            current = current.children[index];
        }
        return current.isEndOfWord; // 문자열의 끝인지 확인
    }
}

public class Trie {
    public static void main(String[] args) {
        TrieNode trie = new TrieNode();

        trie.insert("apple");
        trie.insert("banana");
        trie.insert("grape");

        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("orange")); // false
    }
}

트라이의 동작 원리

트라이의 장점과 활용

예시 코드

참고 자료