[Data Structure] 트라이 트리(Trie Tree)

트라이 트리(Trie Tree)?

트라이 트리는 문자열 검색을 빠르게 해주는 트리 형태의 자료구조이다.

radix tree, prefix tree, retireval tree 라고도 한다. 여기서 트라이(Trie)는 retireval에서 따온 단어이다.

 

 

구현

위 그래프 처럼 car, cb, do, dog라는 단어를 저장한다고 가정한다.

 

먼저 노드를 하나 만들어 주어야 한다.

import java.util.HashMap;
import java.util.Map;

public class Node {
    private final Map<Character, Node> children;
    private boolean endOfWord;

    public Node() {
        children = new HashMap<>();
    }

    public Map<Character, Node> getChildren() {
        return children;
    }

    public boolean isEndOfWord() {
        return endOfWord;
    }

    public void endOfWordToTrue() {
        this.endOfWord = true;
    }
}

노드에는 그 다음 문자를 가진 노드를 저장하는 Map타입인 children과, 단어의 끝인지 확인하는 endOfWord의 인스턴스 변수를 가지고 있다.

 

그 다음은 Node를 사용하여 insert와 search 메서드를 가지고 있는 Trie Class를 구현해보자.

public class Trie {
    private final Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String str) {
        Node curNode = this.root;

        char[] chars = str.toCharArray();
        for (char c : chars) {
            curNode = curNode.getChildren().computeIfAbsent(c, key -> new Node());
        }
        curNode.endOfWordToTrue();
    }

    public boolean search(String str) {
        Node curNode = this.root;

        char[] chars = str.toCharArray();
        for (char c : chars) {
            curNode = curNode.getChildren().get(c);
            if (curNode == null) {
                return false;
            }
        }
        return curNode.isEndOfWord();
    }
}

먼저 insert 메서드부터 살펴보자.

insert 메서드는 항상 root 노드부터 시작하여 자식 노드들을 탐색한다.

예를 들어, car이라는 글자를 넣는다고 가정하면 ['c', 'a', 'r'] 배열을 순차적으로 돌면서 'c' 부터 자식노드에 해당 문자를 가진 노드가 있는지 찾는 것이다.

만약 'c'를 가진 자식 노드가 있다면 해당 노드로 들어가고, 없다면 새 노드를 만들고 거기로 들어간다.

자식 노드로 들어가면 그 다음 문자인 'a'에서 다시 위 과정을 반복한다.

 

처음 들었던 예시를 기준으로 삽입을 진행한다고 하면, 최종적으로 다음과 같은 형태가 될 것이다.

 

그 다음 search 메서드를 살펴보자.

형태는 insert 메서드와 매우 유사하다.

문자열을 순차적으로 탐색하며 자식 노드를 계속 탐색해나가는 형태이다. 자식이 만약 없거나 단어의 마지막임에도 endOfWord가 false 라면 false가 반환된다.

 

그럼 위 코드를 한 번 실행시켜보자

public class App {

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

        trie.insert("car");
        trie.insert("cb");
        trie.insert("do");
        trie.insert("dog");

        System.out.println(trie.search("car"));
        System.out.println(trie.search("ca"));
        System.out.println(trie.search("cb"));
        System.out.println(trie.search("do"));
        System.out.println(trie.search("dog"));
    }
}

true
false
true
true
true

ca라는 단어는 저장하지 않았으므로 자식 노드가 있어도 endOfWord가 false기 때문에 false가 출력된다.

 

 

시간 복잡도

문자열 최대 길이가 M이라고 하면, 문자열 검색 시 시간복잡도는 O(M log n)이다.