[자료구조] Trie(트라이)에 대한 개념과 활용법

 

 

자료구조 Trie란?

 일반적으로 트리의 개념 중 하나로, Radix Tree, Prefix Tree라고도 불립니다. 문자열의 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조입니다.

 

 

자료구조 트리의 종류

 

✅Trie의 형태

 각 Trie의 노드는 <Key, Value> 형태의 Map을 가지고 있습니다. 여기서 Key는 하나의 알파벳이 되고, Value는 Key에 해당하는 자식 노드가 됩니다.

 

• K-진 트리 구조를 통해 문자열을 저장하는 방식.
• 영어 사전의 방식을 그대로 차용함. 만약, game이라는 단어를 찾는다면 사전에서 g부터 a, m, e를 순서대로 찾는 방식을 트리 형태로 구현한 것.
• 즉, 맨 앞의 접두어(prefix)부터 시작하여 단어 전체를 찾아가는 과정.
• Trie는 문자열 저장을 위한 공간을 많이 쓰지만, 탐색에는 매우 효율적이라는 특성이 있습니다.
• 최대 문자열 길이 N일 때, 문자의 개수와 무관하게 시간복잡도는 O(N)이 됩니다. 각 문자 하나를 배열의 위치로 지정하기 때문에 문자열 하나를 찾을 때, O(1)이므로 문자열 길이만큼의 시간이 소요됩니다.
• 만약, 문자열 길이가 너무 커서 Map 등을 이용해 동적할당을 해야 하는 경우, O(MlogN)만큼의 시간복잡도가 발생합니다.

 예를 들어, DOG, CAR, CAT, COW라는 단어로 이루어진 Trie를 도식화하면 아래 그림과 같습니다. 만약, 'CAT'이라는 문자열을 찾으려면, 루트 노드에서부터 차례대로 root -> [C] -> [A] -> [T] 를 탐색합니다.

 

(출처: https://mishuni.tistory.com/46)

 

 그림에서 확인할 수 있듯이 Root 노드는 특정 문자를 의미하지 않고, 자식 노드만 존재합니다. 유의할 점은 노드들이 각각 어떤 알파벳(Key)에 해당하는 노드(Value)인지를 가지고 있는게 아니라는 점입니다.

 

 즉, 루트 노드는 [D], [C]라고 하는 알파벳을 Key로 하는 자식 노드들을 가지고 있고, [D]는 [O]를 Key로 하는 자식 노드, [C]는 [A]와 [O]를 Key로 하는 자식 노드들을 가지고 있는 것입니다.

 

 또한, 루트 노드를 제외한 노드의 자손들은 해당 노드의 공통 접두어를 가진다는 특징이 있습니다. 즉, 'CA' 노드이 자손인 'CAR'과 'CAT'는 'CA-'라는 공통 접두어를 가집니다.

 

 

✅ Trie를 Java로 구현하기

 Trie 자료구조의 노드 역할을 하는 TrieNode 클래스를 먼저 생성합니다.

TrieNode는 자식 노드(Map)와 현재 노드가 마지막 글자인지 여부(Boolean)에 대한 정보로 이루어져 있습니다. 마지막 글자란 'DOG'라는 문자열에서의 마지막 글자인 'G'에서는 isLastChar가 True라는 의미입니다.

 변수와 Getter/Setter를 생성한 코드는 아래와 같습니다.

 

class TrieNode {

    private Map<Character, TrieNode> childNodes = new HashMap<>();
    private boolean isLastChar;

    Map<Character, TrieNode> getChildNodes() {
        return this.childNodes;
    }

    boolean isLastChar() {
        return this.isLastChar;
    }

    void setIsLastChar(boolean isLastChar) {
        this.isLastChar = isLastChar;
    }
}

 

 이어서 TrieNode로 구성된 Trie 클래스를 생성합니다.

 

class Trie {
    private TrieNode rootNode;
    
    Trie() {
        rootNode = new TrieNode();
    }
}

 

 

✅ 메서드 구현

 이제 Trie 자료구조에 단어 정보를 저장(insert)하고, 해당 단어가 존재하는지 확인(contains)하고, 특정 단어를 삭제(delete)하는 3가지 메서드를 구현하겠습니다.

 

1. insert

 입력받은 단어의 각 알파벳을 계층 구조의 자식노드로 만들어서 삽입합니다.

이때, 이미 같은 알파벳이 존재하면 공통 접두어 부분까지는 추가로 생성하지 않습니다. 즉, 해당 계층 문자의 자식 노드가 존재하지 않을 때만 자식 노드를 생성합니다. (람다식으로 구현)

 

 insert하는 과정에서 문자열의 마지막 글자에서는 isLastChar에 true를 대입합니다.

 

public void insert(String word) {
    TrieNode thisNode = this.rootNode;
    
    for(int i=0; i<word.length(); i++) {
        thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), chr -> new TrieNode());
    }
    
    thisNode.setIsLastChar(true);
}

 

 

2. contains

 특정 단어가 Trie에 존재하는지 확인하려면 2가지 조건을 만족해야 합니다.

 1. 루트 노드부터 순서대로 알파벳이 일치하는 자식 노들들이 존재.

 2. 해당 단어의 마지막 글자에 해당하는 노드의 isLastChar가 true일 것.

    (해당 글자를 마지막으로 하는 단어가 있다는 의미)

 

public boolean contains(String word) {
    TrieNode thisNode = this.rootNode;

    for(int i=0; i<word.length(); i++) {
        char chr = word.charAt(i);
        TrieNode node = thisNode.getChildNodes().get(chr);

        if(node == null) {
            return false;
        }

        thisNode = node;
    }

    return this.isLastChar();
}

 

3. delete

 마지막으로 Trie에 넣었던 단어를 삭제하는 과정입니다. contains 메서드처럼 주어진 단어를 찾아 하위 노드로 단어의 길이만큼 내려갑니다.

 

 주의할 점은 노드들이 부모 노드의 정보를 가지고 있지 않기 때문에, 하위 노드로 내려가며 삭제 대상 단어를 탐색하고, 다시 올라오며 삭제하는 과정이 콜백(Callback)형식으로 구현되어야 한다는 점입니다.

 즉, 탐색 방향은 부모 노드 -> 자식 노드지만, 반대로 삭제 방향은 자식 노드 -> 부모 노드로 이루어집니다.

 

 

 삭제 진행은 마지막 글자에서 부모 노드 방향으로 되돌아 오는 과정으로 진행된다는 점에 유의하며 아래와 같은 삭제 조건들을 따라갑니다.

 

 1. 자식 노드를 가지고 있지 않아야 합니다. 위 그림에서 'CA' 노드를 지워버리면 'CAR', 'CAT'까지 삭제되기 때문입니다.

 2. 삭제를 시작하는 첫 노드는 isLastChar == true여야 합니다. 즉, 문자열의 마지막 단어라는 의미입니다. 만약 isLastChar가 false인 경우, Trie에 없는 단어라는 의미가 됩니다.

 3. 삭제를 진행하는 중, isLastChar == false여야 합니다. 삭제 진행방향은 자식 노드 -> 부모 노드이기 때문입니다. 삭제 과정 중에서 isLastChar가 true라는 것은 또 다른 단어가 있다는 의미이므로 삭제 대상이 아닙니다.

 

public void delete(String word) {
    delete(this.rootNode, word, 0);
}


private voide delete(TrieNode thisNode, String word, int index) {
    char chr = word.charAt(index);
    
    if(!thisNode.getChildNodes().containsKey(character))
        throw new Error("there is no [" + word + "] in this Trie"); 
        
    
   TrieNode childNode = thisNode.getChildNodes().get(chr);
   index += 1;
   
   if(index == word.length()) {
       if(!childNode.isLastChar())
           throw new Error("there is no [" + word + "] in this Trie"); 
           
       childNode.setIsLastChar(false);
       
       if(childNode.getChildNodes().isEmpty())
           thisNode.getChildNodes().remove(chr);
   
   } else {
       delete(childNode, word, index);
       
       if(!childNode.isLashChar() && childNode.getChildNodes().isEmpty())
           thisNode.getChilNodes().remove(chr);
   }
}

 

 

 

✅ 추가 사항

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

 백준의 [전화번호 목록]이라는 문제를 Trie를 통해 해결할 수 있습니다. 다만, 문제에서 요구하는 조건인 '같은 접두어의 경우, 일관성이 없는 목록으로 간주'를 만족하려면 위에 작성한 contains 메서드를 아래와 같이 변경해야 합니다.

 

boolean contains(String word) {
    TrieNode thisNode = this.rootNode;

    for(int i=0; i<word.length(); i++) {
        char chr = word.charAt(i);
        TrieNode node = thisNode.getChildNodes().get(chr);

        if(node != null && node.isLastChar) {
            return true;
        } else if(node == null) {
            break;
        }

        thisNode = node;
    }

    return false;
}

 

 

 

✅ Reference

https://www.baeldung.com/trie-java

https://the-dev.tistory.com/2?category=1059400 

[자료구조] Trie(트라이)-1 : 기초 개념

https://hongjw1938.tistory.com/24

자료구조 - 트라이(Trie)