[Java] 트라이(Trie) 알고리즘

트라이(Trie) 알고리즘

개요

정렬된 배열에서 특정 정수 값을 찾기 위한 시간 복잡도는 $O(\log N)$
(N은 배열의 크기)이다.
예를 들어서 1~64 까지 임의의 수를 찾기 위한 최대 시도 횟수는 6번이다.

그러면 문자열을 찾기 위한 시간 복잡도는 어떻게 될까?
문자열을 찾기 위해서 각 문자마다 어디에 위치하는지 찾아야 한다. 이는 $O(\log N)$의 연산을 하고, 문자열의 길이가 M이라고 했을 때, 총 시간 복잡도는 $O(M\log N)$이 된다.

하지만 트라이 알고리즘을 사용한다면, 내가 원하는 원소를 $O(M)$만에 할 수 있다. (공간과 시간의 Trade Off를 이용..)

트라이 알고리즘은 트리를 이용하여 구현한다.
각 원소마다 HashMap이 존재하여 다음 문자의 위치로 이동하는 방식이다.
루트로부터 트리로 내려갈 수록 접두사가 붙어진다고 이해하면 된다.

알고리즘에 사용할 Trie

예를 들어서 BEAR를 찾는다면

루트 노드(-)에서

B로 내려간 뒤

E로 내려가고,

A로 내려가고,

R로 내려간다.

BEAR 4글자 짜리 탐색하는데 내려간 횟수는 4이다.

이렇게 O(M)의 빠른 속도로 탐색을 할 수 있다는 장점이 있다.

하지만 그 만큼의 트리가 만들어지므로, 공간을 많이 잡아먹을 수 있다는 단점이 있다.

코드

삭제 없이 트라이 알고리즘만 구현한 코드는 다음과 같다.

public class Trie {
    Boolean is_terminal;
    HashMap<Character, Trie> childNodes = new HashMap<>();

    public Trie() {
        is_terminal = false;
    }

    Boolean isLastNode() {
        return is_terminal;
    }

    void setLastNode(Boolean isLastChar) {
        is_terminal = isLastChar;
    }

    void insert(String word) {
        Trie trie = this;

        for (int i = 0; i < word.length(); i++) {
            trie = trie.childNodes.computeIfAbsent(word.charAt(i), c -> new Trie());
        }

        trie.setLastNode(true);
    }

    boolean contains(String word) {
        Trie thisNode = this;

        for (int i = 0; i < word.length(); i++) {
            if (thisNode.isLastNode())
                return false;
            thisNode = thisNode.childNodes.get(word.charAt(i));

            if (thisNode == null)
                return false;
        }

        return true;
    }
}

https://the-dev.tistory.com/3 에서 코드를 참조했다.

Trie에 들어가는 childNodes의 구조가 약간 특이하다는 것을 잘 보자

HashMap<Character, Trie> 형태로써 노드가 물리고 물리는 구조임을 이해하자

다음 삽입하는 메소드를 보자

    void insert(String word) {
        Trie trie = this;

        for (int i = 0; i < word.length(); i++) {
            trie = trie.childNodes.computeIfAbsent(word.charAt(i), c -> new Trie());
        }

        trie.setLastNode(true);
    }

computeIfAbsent라는 메소드는 HashMap에서 만약

trie.childNodes.get(word.charAt(i)) 의 값이 존재하지 않으면, new Trie()를 통해서 생성해주고,

값이 존재한다면 그 값을 반환하는 메소드이다.

computeIfAbsent를 사용하지 않으면 다음과 같이 구성된다.

    void insert2(String word) {
        Trie trie = this;

        for (int i = 0; i < word.length(); i++) {

            if (trie.childNodes.get(word.charAt(i)) == null) {
                trie.childNodes.put(word.charAt(i), new Trie());
            }
            trie = trie.childNodes.get(word.charAt(i));
        }
        trie.setLastNode(true);
    }

isLastNode라는 변수는 리프노드인지 판단하는 변수이다.

이제 해당 단어를 포함하고 있는지 확인하는 메소드를 보자

    boolean contains(String word) {
        Trie thisNode = this;

        for (int i = 0; i < word.length(); i++) {
            if (thisNode.isLastNode())
                return false;
            thisNode = thisNode.childNodes.get(word.charAt(i));

            if (thisNode == null)
                return false;
        }

        return true;
    }

입력받은 단어(word)의 길이 만큼 반복하면서, 노드를 타고 내려간다.

만약 단어의 길이가 마지막이 아닌데 리프노드를 만났거나(Apples를 탐색한 경우)

thisNode값이 존재하지 않는경우 (Banana를 탐색한 경우)에는 false를 반환하고

마지막 단어 문자까지 존재한다면 그 단어가 존재하는 것이므로 true를 반환한다.