[자료구조 | Java] Trie(트라이)

이번 시간에는 자료구조 트라이에 대해 알아보도록 하겠습니다.

 

1. 트라이(Trie)란?

효율적인 문자열 저장 및 탐색이 가능하도록 만든 자료구조 형태 중 하나입니다.

 

코딩을 하다 보면 수많은 문자열을 저장한 후에 어떤 문자열을 입력 받았을 때, 해당 문자열이 내가 저장한 구조에 포함된 문자열인지의 여부를 알아야 할 때가 있을 것입니다.

 

이때 사용하는 방식은 다음과 같은 것들이 있습니다.

 

① 단순 비교

• 전체 문자열을 맨 앞부터 끝까지 각 문자를 비교 하는 방식

②이진 탐색(Binary Search)

• 전체 문자열을 사전 순으로 배열 저장 후, 중간 값과 비교하여 정렬을 진행하는 방식

 

③ 트라이(Trie)

• 이번 시간에 배울 내용
• K-진 트리 구조를 통해 문자열을 저장하는 방식
• English Dictionary(영사전)의 방식을 차용함
  • absent라는 단어를 찾는다고 하면 보통 a를 찾고 순서대로 b,s,e,n,t를 찾는데 이것을 트리 형식으로 구현한 것이다.
• 맨 앞의 접두어부터 시작하여 단어 전체를 찾아가는 과정으로 접두사 트리(Prefix-Tree)라고도 한다.
• 문자열 저장을 위한 공간은 많이 소모 되지만 탐색에는 효율적인 구조이다.
• 최대 문자열 길이가 m일 때 문자의 갯수와 무관하게 시간 복잡도는 O(m)이다.
  • 각 문자 하나를 배열의 위치로 지정하여 문자열 하나를 찾을 때 O(1)이므로 딱 길이만큼의 시간만 소요한다.
  • 만약, 문자열 길이가 너무 커서 Map 구조를 사용하여 동적 할당을 해야 하는 경우에는 O(mlog₂n)을 요구할 수도 있다.

 

다음 그림을 통해 이해해 보도록 합시다.

['bar', 'bag', 'bark', 'dog', 'do', 'door']

위와 같이 문자열 6개가 담긴 배열을 K-진 트리 형태 구조로 표현한다고 생각해 보겠습니다.

 

 

2. 트라이 구현

생성자

public class Trie {

    Node root;
    static final int ALPHABET_SIZE = 26; // a-z는 26개
    public Trie(){
        this.root = new Node();
        this.root.val = ' ';
    }

    private static class Node{
        Node[] child = new Node[ALPHABET_SIZE];// 뒤로 연결되는 문자열 a-z 소문자를 index화하여 저장하는 배열(26개)
        boolean isTerminal = false; // 현재 노드가 문자 완성이 되는 노드인지 여부
        int childNum = 0;            // 현재 노드에 연결된 문자열의 개수
        char val;                    // 현재 노드의 값
    }
}

루트 노드에는 어떠한 문자열도 포함하지 않고 모든 문자열의 접두사를 자식 배열로 갖고 있습니다.

또한 노드 클래스에는 문자열이 완성되는가의 여부를 묻는 변수도 저장합니다.

 

삽입 - Insert

    private int charToInt(char c){
        return c - 'a'; // 여기서는 소문자만 있으므로 'a'를 빼면 된다.
    }

    public void insert(String str){
        int length = str.length();
        Node current = this.root;       // 루트 부터 시작해서 내려감
        for(int i=0; i < length; i++){
            char c = str.charAt(i);      // 전체 문자열의 일부 단어 추출
            int num = this.charToInt(c); // 추출한 단어를 숫자로 변환

            if(current.child[num] == null){     // 기존에 null이면 연결 문자열로 처음 추가되는 것
                current.child[num] = new Node();
                current.child[num].val = c;
                current.childNum++;
            }

            current = current.child[num];       // 자식 노드로 넘어감
        }
        current.isTerminal = true;
    }

 

find

    // 반복문으로 노드를 순환하여 문자열 존재 여부 판단
    public boolean find(tring str){
        int length = str.length();
        Node current = this.root; # 현재 노드 설정

        for(int i=0; i < length; i++){
            char c = str.charAt(i);
            int num = this.charToInt(c);
            if(current.child[num] == null){ // 문자열의 일부를 추출했는데 null 이라면 false 반환
                return false;
            }
            current = current.child[num];
        }
        return current != null && current.isTerminal; // 문자열의 마지막이라면 true
    }

 

delete

삭제는 재귀적으로 Bottom-up 방식을 사용합니다.

 

과정은 다음과 같이 진행됩니다.

1. 삭제할 문자가 다른 문자의 접두사인 경우: isTerminal을 false로 변경한다.
   • Do는 Door의 접두사가 된다. 따라서, Do를 삭제하면 D, o에서 o에 isTerminal만 false로 변경한다.
   • 단순히 삭제하면 Door 또한 사라지게 된다.
2. 삭제할 문자가 Unique하여 다른 문자와 연관이 없는 경우 - 관련 모든 노드를 삭제한다.
3. 삭제할 문자의 일부가 전체 삭제 문자의 접두사인 경우에는 다른 문자에 영향가지 않는 곳까지만 삭제한다.
   • 예를 들어, Door를 삭제하려고 하면 Do가 있으므로 전체 삭제를 할 수 없고 Door에서 뒤의 o, r 만 삭제할 수 있다.

 

    // 사용자가 호출 시 사용하는 메소드
    public void delete(String str){
        delete(this.root, str, 0);
    }

    // 내부적으로 재귀를 통해 삭제를 진행하는 메소드
    private void delete(Node current, String str, int idx){
        int leng = str.length();

        // 자식이 없는데 string의 length의 끝까지 오지 않았다면 예외 발생
        // 끝까지 갔는데 해당 노드가 terminal가 아니었다면 해당 단어를 저장하지 않은 것이므로 예외 발생
        if((current.childNum == 0 && idx != leng) || (idx == leng && !current.isTerminal)) {
            throw new NoSuchElementException("Value " + str + " does not exist in Trie!");
        }

        // 문자열의 마지막에 다다른 경우
        if(idx == leng){
            current.isTerminal = false;

            // 자식이 없는데 문자의 마지막이었다면 해당 문자만 저장된 것이므로 null 처리
            if(current.childNum == 0){
                current = null;
            }
        } else {
            char c = str.charAt(idx);
            int num = charToInt(c);

            // 삭제 후 돌아오는 부분
            delete(current.child[num], str,idx+1);

            // child가 null처리 되었다면 자식 노드의 수가 하나 줄어든 것이므로 -- 처리
            if(current.child[num] == null) current.childNum--;

            // 현재 노드의 자식이 없고, 단어의 마지막도 아니라면 삭제해야 한다.
            if(current.childNum == 0 && !current.isTerminal){
                current = null;
            }
        }
    }

 

3. 관련된 문제

• 백준 5670번 휴대폰 자판