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

1. 트라이(Trie)란?

원하는 요소를 찾기위해 자주 사용되는 이진 검색 트리 등에서는 타겟 요소를 찾는데에 O(logN)의 시간이 걸립니다.
하지만 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에,
원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸립니다.
따라서 이 작업을 여러번 수행한다면 시간이 오래 걸리게 됩니다. 
이러한 문자열 검색시의 단점을 해결하기 위해 나온 자료구조가 트라이(Trie)입니다.

 

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 구글이나 네이버 등에 검색어를 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 합니다.
• 래딕스 트리(Radix Tree)나 접두사 트리(Prefix Tree), 탐색 트리(Retrieval Tree)라고도 합니다
  • 트라이(Trie)는 Retrieval Tree에서 나온 단어

예를 들어 'Tistory'라는 단어를 검색하기 위해 제일 먼저 'T'를 찾고, 다음에 'i', 's', 't', ... 의 순대로 찾으면 됩니다.

이런 개념을 적용한 자료구조가 트라이(Trie)입니다.

 

2. 트라이(Trie)의 작동 원리

다음 그림은 문자열 집합 {"apple", "app", "dad", "dream", "age"}를 트라이로 구현한 것입니다.

*트라이(Trie)는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리입니다.

 

[공통 접두어]

"apple"과 "app"은 "app"라는 공통 접두어가 있으므로 같은 서브 트리에 표시됩니다.

즉, "a"라는 공통 접두어를 가진 "apple", "app", "age"는 Head의 자식 노드 'a'에,

"d"라는 공통 접두어를 가진 "dad", "dream"은 Head의 자식 노드 'd'에 표시됩니다.

 

[Leaf Node]

리프 노드는 각 단어의 마지막 문자를 의미하므로, 단어의 끝 문자라는 표시(endOfWord)를 해야합니다.

또한 리프 노드의 개수는 단어의 개수를 의미합니다.

 

[트라이(Trie) 생성 과정]

1. "apple"를 트라이에 삽입

• 'a': 첫번째 문자인 'a'는 초기에 트라이 자료구조 내에 아무것도 없으므로 Head의 자식노드에 'a'를 추가
• 'p': 'a' 노드에도 현재 자식이 하나도 없으므로 'a'의 자식노드에 'p'를 추가
• 'p', 'l', 'e'에 대해서도 자식노드로 추가
• 'l': "apple" 단어가 끝남을 알기 위해 'l' 노드에 마지막 노드(endOfWord)임을 표시

2. "app"를 트라이에 삽입

• 'a': 현재 Head의 자식 노드로 'a'가 이미 존재하기 때문에 'a' 노드를 추가하지 않고 기존에 있는 'a'노드로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동하면서, 'p'노드에 마지막 노드임을 표시

3. "dad", "dream",  "age"를 트라이에 삽입

• "dad"와 "dream"의 첫 문자인 'd'는 Head의 자식 노드로 없기 때문에 추가해서, 각 단어별로 문자를 순차적으로 추가
• "age"는 Head의 자식 노드로 'a'가 있기 때문에,
  • 'a'로 이동 => 'a'의 자식 노드에 'g'가 없으므로 'g'를 추가 => 'e'도 'g'의 자식 노드로 추가한 후 마지막 노드 표시

 

3. 트라이(Trie) 구현(Java)

그럼 트라이를 Java로 구현하려면 어떻게 해야할까?

기본적으로는 Map Interface를 사용해서 구현합니다.

Map의 Key값에는 단어를 이루는 각각의 문자들이 들어가고, Value에는 자식 노드 클래스를 저장합니다.

 

이제 순차적으로 자바로 구현을 해보겠습니다.

Node 클래스 생성

Node 클래스는 해당 노드의 자식 노드정보와 단어의 끝인지를 판단하는 변수로 구성합니다.

private class Node {
    HashMap<Character, Node> childNode = new HashMap<>(); // 자식 노드
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
}

 

트라이(Trie) 자료구조 클래스 생성

기본적으로 루트 노드를 초기화해 줍니다.

*루트 노드는 1) 항상 비어있고 2) 루트노드의 자식 노드는 각 단어의 첫 글자입니다.

public class Trie {
    private Node rootNode;
    Trie() {
        // Trie 생성시 루트 노드는 기본으로 생성
        rootNode = new Node(); // 루트 노드는 빈 노드
    }
}

 

기본 메서드

1) 노드 추가(insert)

입력 받은 단어를 문자 순대로 트리 계층 구조의 자식 노드로 생성해서 넣습니다.

• 문자가 자식 노드에 존재하면 새로 생성하지 않고 자식 노드로 이동
• 단어의 마지막 문자인 노드라면 endOfWord = true로 설정

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드를 확인
    //  1) 자식 노드에 있는 문자라면 자식 노드를 가져옴
    //  2) 자식 노드에 없는 문자라면 새롭게 생성
    for (int i=0; i<word.length(); i++) node = node.childNode.computeIfAbsent(word.charAt(i), key -> new Node());
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

 

2) 포함 여부 확인(contains)

특정 단어가 트라이에 존재하는지 확인합니다.

• 루트 노드부터 단어의 문자 순대로 일치하는 자식 노드가 계층을 이루고 있는지 확인
• 단어의 마지막 문자에 endOfWord가 true

두 조건을 만족하는 경우가 트라이에 존재하는 경우입니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        if (!node.childNode.containsKey(c)) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode.get(c); // 마지막 문자를 node에 저장
    }
    return node.endOfWord; // 마지막 문자 여부를 반환
}

 

3) 노드 삭제(delete)

트라이에 추가했던 단어를 삭제합니다.

• 부모 노드에 대한 정보는 없기 때문에 삭제할 단어의 마지막 문자까지 이동해서 문자를 삭제해와야 합니다. => 재귀
• 다음 문자에 존재하는 자식노드가 있고, 삭제를 시작하는 마지막 노드(리프 노드)에는 endOfWord가 true로 되어있어야 합니다. 
  • 즉, 삭제할 단어가 트라이에 포함되어있어야 합니다.
• 단어 삭제를 위해 마지막 문자 노드인 리프 노드의 endOfWord를 false로 변경합니다. 이후 순차적으로 거꾸로 올라가면서 노드를 삭제합니다. 단, 아래 두 조건이 아닌 경우에만 삭제합니다.
  • 해당 노드의 자식노드가 있는 경우
    • 자식노드가 있다는 뜻은 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.
  • endOfWord가 true인 경우
    • 단어의 끝인 문자인 경우 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
private void delete(Node node, String word, int idx) {
    // 단어의 마지막 인덱스인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    }
    char c = word.charAt(idx); // 현재 확인해야하는 문자
    if (!node.childNode.containsKey(c)) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    Node child = node.childNode.get(c); // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childNode.isEmpty() && !child.endOfWord) node.childNode.remove(c, child);
}

 

🧪 구현 테스트

public static void main(String[] args) {
        Trie trie = new Trie();
        // insert
        String[] arr = {"apple", "app", "dream", "dad", "age"};
        for (String word: arr) {
            trie.insert(word);
        }
        // delete
        trie.delete("app");
        trie.delete("dream");
        // contains
        System.out.println(trie.contains("apple")); // true
        System.out.println(trie.contains("app")); // 삭제했으므로 false
        System.out.println(trie.contains("age")); // true
        System.out.println(trie.contains("dream")); // 삭제했으므로 false
        System.out.println(trie.contains("dad")); // true
}

 

위에서 예시로 들었던 문자열 배열을 기준으로 트라이를 생성하고 삭제, 포함여부를 확인하면 아래와 같은 결과를 확인할 수 있습니다.

 

💡 전체 코드는 아래 링크에서 확인해주세요.

Algorithm/src/Trie.java at main · hywnj/Algorithm

 

4. 트라이(Trie) 시간 복잡도

총 문자의 개수를 N, 가장 긴 문자열의 길이가 L이라고 할때

• 생성 시간 복잡도: O(N*L)
  • 모든 문자열 N개를 넣어야하고, N개에 대해 트라이에 넣는 건 가장 긴 문자열 길이인 L만큼 걸린다.
  • 삽입은 O(L)만 소요
• 탐색 시간 복잡도: O(L)
  • 트리를 가장 깊게 탐색하는 경우는 가장 긴 문자열 길이인 L까지 들어가는 것이므로 O(L)

 

5. 트라이(Trie) 장단점

• 문자열에 대한 검색을 빠르게 할 수 있습니다.
  
  • 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나 추가하면 되기 때문에 문자열의 추가와 탐색 모두 O(M)만에 가능합니다.

• 필요로 하는 메모리의 크기가 너무 크다는 단점이 있습니다.
  • 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있기에 저장공간의 크기가 크다는 단점이 있습니다.
  • 문자열이 모두 영소문자로 이루어져 있어도, 자식 노드를 가리키는 26개의 포인터를 저정해야하는데
  • 최악의 경우에는 집합에 포함되는 문자열의 길이의 총 합만큼의 노드가 필요하기 때문에 총 메모리는 O(포인터 크기*포인터 배열 개수*총 노드 개수)가 됩니다.
    • 만약 1,000자리의 문자열이 1,000만개가 있다면 이때, 100만개의 노드가 필요하고 포인터의 크기가 8Byte라 하면 약 200MB의 메모리가 필요합니다.

트라이(Trie) 단점 해결을 위한 방법

'메모리의 크기가 너무 큰' 단점을 해결하기 위해, 보통 map이나 vector를 이용해서 필요한 노드만 메모리를 할당하는 방식을 사용합니다. 그러나 이는 메모리 제한이 타이트한 경우에는 최적화가 까다롭습니다.

또한 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다고 합니다.

 

6. 트라이(Trie) 코딩테스트 문제

• [백준] - 전설
• [백준] - 전화번호 목록 : 🔗풀이 포스팅

 

참고한 링크

• [자료구조] 트라이 (Trie)
• [Algorithm] Trie를 Java로 구현해보자!
• [자료구조] 트라이