[알고리즘 정리] 트라이

February 8, 2021 6 분 소요

트라이(Trie)란?

트라이는 트리의 하나로써, 문자열을 검색하는 데에 유용한 자료구조입니다.

정수형 타입의 이진 검색 트리(Binary Search Tree, BST) 를 사용하면, 탐색에는 O(logN) 만큼의 시간이 소요됩니다. 이에 문자열을 적용시키면, 다음과 같은 탐색 시간이 소요될 것입니다.

아래 그림과 같이 모든 노드에 문자열이 들어있기 때문에, 문자열의 최대 길이(M)에 대해 O(MlogN) 의 시간 복잡도를 갖게 됩니다.

위의 일반적인 BST와는 다르게, 트라이는 각 노드에 오로지 하나의 문자만을 저장하여, 트리 탐색을 마치면 찾고자 하는 단어가 완성되는 구조를 사용합니다. 따라서 알파벳만을 사용한다면, 26개의 자식 노드를 가질 수 있으며, 26진 트리로 구현됩니다. 다른 특수문자들을 사용한다면, 자식 노드의 수는 더 많아질 것입니다.

아래와 같이, 하나의 문자로 이뤄진 노드들을 사용해, 아래로 탐색을 하며 문자열을 탐색할 수 있습니다.

예를 들어, cop 는 깊이 3까지, copy 는 깊이 4까지 탐색해 찾을 수 있게 됩니다.

트리 탐색을 진행하며, 접두사에 문자가 하나씩 붙어(예 c → co → cop → copy) 단어가 완성되기 때문에 접두사 트리(Prefix Tree) 라고도 합니다.

전체 코드

트라이 자료구조의 구현은 아래 코드와 같습니다.

package 카카오2018;

public class Trie {
    TrieNode root; // 아래 생성자에서 루트 노드 객체를 생성 및 초기화 할 것임.
    static final int SIZE = 26; // 사이즈는 k-진수에 맞게 가변적임.

    public Trie() {
        this.root = new TrieNode();
        this.root.value = ' '; // value만 의미없는 값으로 초기화 함.
    }

    private static class TrieNode {
        TrieNode[] children = new TrieNode[SIZE]; // 각 노드들은 자식 노드들을 관리하는 배열을 갖음.
        boolean isTerminal = false; // 각 노드가 단말인지를 나타내는 변수.
        int childCount = 0; // 각 노드의 자식 노드들의 수를 저장하는 변수.
        char value; // 각 노드에 문자를 저장하는 변수.
    }

    // char -> int
    public int ctoi(char c) {
        return c - 'a';
    }

    // int -> char
    public char itoc(int i) {
        return (char) (i + 'a');
    }

    // 트라이에 문자열을 삽입하는 함수
    public void insert(String str) {
        int len = str.length();
        TrieNode current = this.root;

        for (int i = 0; i < len; i++) {
            char ch = str.charAt(i);        // 삽입할 문자열을 구성하는 문자 하나.
            int idx = ctoi(ch);             // 문자를 인덱스로 변환해 child 배열을 접근하기 위함.

            if (current.children[idx] == null) {        // 없으면? 첨으로 추가됨.
                current.children[idx] = new TrieNode();
                current.children[idx].value = ch;
                current.childCount++;
            }

            current = current.children[idx]; // 그 다음 번 자식 노드로 넘어간다.
        }

        current.isTerminal = true; // 삽입할 문자열을 구성하는 마지막 문자에 해당하는 노드는 단말 표시를 한다.
    }

    // 트라이에서 문자열을 검색하는 함수
    public boolean find(String str) {
        int len = str.length();
        TrieNode current = this.root; // 루트부터 자식 노드들을 탐색한다.

        for (int i = 0; i < len; i++) {
            char ch = str.charAt(i);
            int idx = ctoi(ch);

            if (current.children[idx] == null) { // 해당 문자에 대한 노드가 생성되지 않았다면, 삽입된 이력이 없으므로 false를 반환한다.
                return false;
            }

            current = current.children[idx];
        }

        return current != null && current.isTerminal; // 찾고자 하는 문자열의 마지막 문자를 포함하는 노드가 단말이라면 true를 반환한다.
    }

    // 트라이에서 문자열을 제거하는 함수.
    // 초기에 이 메소드를 호출함. 내부적으로는 오버로딩 된 파라미터를 갖는 메소드를 호출하게 됨.
    public void delete(String str) {
        this.delete(this.root, str, 0);
    }

    // 트라이에서 문자열을 제거하는 함수
    // 재귀적으로 단말 노드부터 하나씩 제거함.
    public void delete(TrieNode trieNode, String str, int idx) {
        int len = str.length();

        if (idx == len) { // 마지막 문자인 경우
            trieNode.isTerminal = false; // 단말 노드의 isTerminal을 false 로 바꾼다.

            if (trieNode.childCount == 0) // 단말 노드의 자식이 없으면, 해당 노드는 삭제까지 수행한다.
                trieNode = null;
        }

        else { // 마지막 문자가 아닌 경우
            char ch = str.charAt(idx);
            int num = ctoi(ch);

            delete(trieNode.children[num], str, idx + 1); // 다음 문자에 해당하는 노드를 재귀 함수를 호출해 제거한다.

            if (trieNode.children[num] == null) trieNode.childCount--; // 현재 노드의 자식이 제거되었으면, 자식 카운트를 감소시킨다.
            if (trieNode.childCount == 0 && trieNode.isTerminal) trieNode = null; // 자식 카운트도 0이고, 현재 노드가 단말이면, 현재 노드를 제거한다.
        }
    }

    // 트라이 구조를 콘솔에 출력하는 함수.
    // 초기에 이 메소드를 호출함. 내부적으로는 오버로딩 된 파라미터를 갖는 메소드를 호출하게 됨.
    public void print() {
        this.print(this.root, 0, new StringBuilder());
    }

    // 트라이 구조를 콘솔에 출력하는 함수.
    // 재귀적으로 탐색을 하며, 출력 문자열 뒤에 붙여 나감.
    public void print(TrieNode trieNode, int idx, StringBuilder sb) {
        TrieNode current = trieNode;
        TrieNode[] children = current.children;
        StringBuilder tmp = new StringBuilder(sb);

        if (!current.equals(this.root)) {
            tmp.append(itoc(idx));
        }

        // 단말 노드에 도착했을 때 지금까지 붙여온 문자열을 출력함.
        if (current.isTerminal) {
            System.out.println(tmp);
        }

        for (int i = 0; i < SIZE; i++) {
            if (current.children[i] == null) continue;
            print(children[i], i, tmp);
        }
    }

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

        trie.insert("cat");
        trie.insert("cap");
        trie.insert("cow");
        trie.insert("cop");
        trie.insert("copy");

        trie.print();
        System.out.println();

        trie.delete("cop");

        trie.print();
    }
}

insert 동작 과정 알아보기

public void insert(String str) {
    int len = str.length();
    TrieNode current = this.root;

    for (int i = 0; i < len; i++) {
        char ch = str.charAt(i);        // 삽입할 문자열을 구성하는 문자 하나.
        int idx = ctoi(ch);             // 문자를 인덱스로 변환해 child 배열을 접근하기 위함.

        if (current.children[idx] == null) {        // 없으면? 첨으로 추가됨.
            current.children[idx] = new TrieNode();
            current.children[idx].value = ch;
            current.childCount++;
        }

        current = current.children[idx]; // 그 다음 번 자식 노드로 넘어간다.
    }

    current.isTerminal = true; // 삽입할 문자열을 구성하는 마지막 문자에 해당하는 노드는 단말 표시를 한다.
}

비어있는 트라이에 문자열 cap 과 cat 을 순서대로 삽입했을 때, 각 TrieNode 객체가 같는 멤버 변수들의 변화는 다음과 같이 이루어집니다.

insert(“cap”);

문자열 cap을 구성하는 모든 문자들에 대해 노드가 생성되어 있지 않으므로, 노드 생성과 동시에 멤버 변수들 값에 변화를 줍니다. value 는 삽입 문자열을 순회하며, 현재 가리키는 문자 값을, childCount 는 자식 노드들의 개수를, isTerminal 은 노드가 단말 노드인지를 나타냅니다.

insert(“cat”);

문자 c, a 에 대한 노드들이 이미 생성되어 있으므로, 건너뛰고 문자 t에 대한 노드 추가만 해줍니다.

find 동작 과정 알아보기

public boolean find(String str) {
    int len = str.length();
    TrieNode current = this.root; // 루트부터 자식 노드들을 탐색한다.

    for (int i = 0; i < len; i++) {
        char ch = str.charAt(i);
        int idx = ctoi(ch);

        if (current.children[idx] == null) { // 해당 문자에 대한 노드가 생성되지 않았다면, 삽입된 이력이 없으므로 false를 반환한다.
            return false;
        }

        current = current.children[idx];
    }

    return current != null && current.isTerminal; // 찾고자 하는 문자열의 마지막 문자를 포함하는 노드가 단말이라면 true를 반환한다.
}

find(“cat”);

루트 노드를 기준으로, 검색 문자열 cat 에 대해 c → a → t 순서로 노드 탐색이 이뤄집니다. 탐색을 마쳤을 때, current 노드는 문자 t 를 value 로 갖는 노드를 가리키게 되며, 이 노드의 isTerminal 값으로 단말인지를 확인할 수 있습니다. 따라서, 마지막 문자까지 순회를 마쳤을 때, 그 노드의 isTerminal 값이 true 이면 검색이 성공적으로 완료되었음을, false 이면 그런 문자열은 삽입된 적이 없음을 나타냅니다.

delete 동작 과정 알아보기

public void delete(TrieNode trieNode, String str, int idx) {
    int len = str.length();

    if (idx == len) { // 마지막 문자인 경우
        trieNode.isTerminal = false; // 단말 노드의 isTerminal을 false 로 바꾼다.

        if (trieNode.childCount == 0) // 단말 노드의 자식이 없으면, 해당 노드는 삭제까지 수행한다.
            trieNode = null;
    }

    else { // 마지막 문자가 아닌 경우
        char ch = str.charAt(idx);
        int num = ctoi(ch);

        delete(trieNode.children[num], str, idx + 1); // 다음 문자에 해당하는 노드를 재귀 함수를 호출해 제거한다.

        if (trieNode.children[num] == null) trieNode.childCount--; // 현재 노드의 자식이 제거되었으면, 자식 카운트를 감소시킨다.
        if (trieNode.childCount == 0 && trieNode.isTerminal) trieNode = null; // 자식 카운트도 0이고, 현재 노드가 단말이면, 현재 노드를 제거한다.
    }
}

문자열 삭제를 수행할 시, 해당 문자열이 다른 문자열의 접두사와 겹치면 경우를 생각해 봐야 합니다.

위와 같은 트라이 구조에서 문자열 cop 을 삭제하려고 하면, cop 에서 확장되는 문자열 copy가 존재합니다. → 노드 p의 isTerminal 변수의 값을 false 로 설정.
문자열 copy 를 삭제하려고 하면, 문자열 cop 과 겹치는 노드들이 존재합니다. → 노드 y만 삭제.

시간 복잡도

제일 긴 문자열의 길이를 L , 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같습니다.
생성시 시간복잡도: O(ML), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(ML)만큼 걸립니다. 물론 삽입 자체만은 O(L)만큼 걸립니다.
탐색시 시간복잡도: O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸립니다.

참고 자료

Twitter Facebook LinkedIn

김무성

[알고리즘 정리] 트라이

트라이(Trie)란?

전체 코드

insert 동작 과정 알아보기

insert(“cap”);

insert(“cat”);

find 동작 과정 알아보기

find(“cat”);

delete 동작 과정 알아보기

시간 복잡도

참고 자료

공유하기

댓글남기기

참고

[프로그래머스] 67256. 키패드 누르기

[프로그래머스] 72410. 신규 아이디 추천

[프로그래머스] 81301. 숫자 문자열과 영단어

[JavaScript] 문자열을 정수로 변환하는 세 가지 방법