알고리즘

트라이(Trie) 자료구조

KYBee 2023. 1. 2. 16:59

트라이 자료구조

  • 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
  • 문자열을 한 자리씩 뽑아내어 트리 형태로 저장한다.
  • 각 노드의 자식들을 탐색하며 저장된 문자열을 얻는다.
  • 즉, 트리의 형태로 문자열을 저장하고 탐색할 수 있는 자료구조가 트라이이며 각 노드의 자식들에는 다음에 나올 문자에 대한 노드가 연결되어 있다.

트라이 시간복잡도

  • 트라이는 주로 많은 문자열들을 저장한 뒤에 특정 문자열이 그 안에 속하는지를 확인할 때 많이 사용된다. 예를 들어 길이가 L인 문자열 M개를 저장해두고 길이가 L인 임의의 문자열 A가 M개 안에 속해있는지 확인한다고 가정해 보자.
  • 저장 시 시간복잡도 : O(L * M) 한 개의 문자열을 저장할 때 L만큼의 시간이 걸린다. 문자열을 문자의 집합으로 분리하면 L개의 문자들이 생긴다. 그 문자들을 차례대로 트라이의 루트부터 저장하기 때문이다. 이런 문자열이 M개 있으므로 O(L * M)의 시간이 걸리게 된다.
  • 탐색 시 시간복잡도 : 임의의 문자열 A를 문자의 집합으로 분리하여 L개의 문자들을 얻는다. 트라이의 루트부터 각 문자들을 순차적으로 탐색하게 되면 O(L)의 시간 만에 그 문자열이 존재하는지 탐색할 수 있다.
  • 이처럼 트라이는 저장된 문자열을 탐색하는데 매우 효율적이다. 만약 트라이를 사용하지 않고 문자열 A가 M개의 문자열 집합에 속해있는지 탐색하려면 M번의 문자열 비교가 이루어져야 하기에 탐색에만 O(L * M)의 시간이 걸리게 된다.

트라이 장단점

  • 문자열 검색을 빠르게 할 수 있다. (위에 설명한 시간 복잡도 참고)
  • 각 노드에서 자식들에 대한 포인터들을 모두 저장하고 있기에, 저장 공간의 크기가 크다.

트라이 동작 원리

트라이에 문자열 저장하기

boy, boi, bo, abc를 저장한다고 가정하겠다.

 

 

boy를 저장

1. 저장 전 트라이 상태는 아래와 같다.

2. boy를 b, o, y로 자른다.

3. 트라이 루트를 시작으로 자식에 b에 매핑된 트라이가 있는지 확인한다.

4. 현재 b에 매핑된 자식이 없으므로 트라이를 하나 새로 만들고 b로 매핑한다.

5. 다음으로 b에 매핑된 트라이의 자식에 o에 매핑된 트라이가 있는지 확인한다.

6. 현재 o에 매핑된 자식이 없으므로 트라이를 하나 새로 만들고 o로 매핑한다.

7. 다음으로 o에 매핑된 트라이의 자식에 y에 매핑된 트라이가 있는지 확인한다.

8. 현재 y에 매핑된 자식이 없으므로 트라이를 하나 새로 만들고 y로 매핑한다.

9. y는 마지막 문자열이므로 y와 매핑된 트라이의 isEnd값은 true로 바꾼다.

10. 저장 후 트라이 상태는 아래와 같다.

 

boi를 저장

1. 저장 전 트라이 상태는 아래와 같다.

2. boy를 b, o, i로 자른다.

3. 트라이 루트를 시작으로 자식에 b에 매핑된 트라이가 있는지 확인한다.

4. 현재 b에 매핑된 자식이 있으므로 해당 노드로 간다.

5. 다음으로 b에 매핑된 트라이의 자식에 o에 매핑된 트라이가 있는지 확인한다.

6. 현재 o에 매핑된 자식이 있으므로 해당 노드로 간다.

7. 다음으로 o에 매핑된 트라이의 자식에 i에 매핑된 트라이가 있는지 확인한다.

8. 현재 i에 매핑된 자식이 없으므로 트라이를 하나 새로 만들고 i로 매핑한다.

9. i는 마지막 문자열이므로 i와 매핑된 트라이의 isEnd값은 true로 바꾼다.

10. 저장 후 트라이 상태는 아래와 같다.

 

bo를 저장

1. 저장 전 트라이 상태는 아래와 같다.

2. boy를 b, o로 자른다.

3. 트라이 루트를 시작으로 자식에 b에 매핑된 트라이가 있는지 확인한다.

4. 현재 b에 매핑된 자식이 있으므로 해당 노드로 간다.

5. 다음으로 b에 매핑된 트라이의 자식에 o에 매핑된 트라이가 있는지 확인한다.

6. 현재 o에 매핑된 자식이 있으므로 해당 노드로 간다.

7. o는 마지막 문자열이므로 o와 매핑된 트라이의 isEnd값은 true로 바꾼다.

8. 저장 후 트라이 상태는 아래와 같다.

 

abc를 저장

1. 저장 전 트라이 상태는 아래와 같다.

2. abc를 a, b, c로 자른다.

3. 트라이 루트를 시작으로 자식에 a에 매핑된 트라이가 있는지 확인한다.

4. 현재 a에 매핑된 자식이 없으므로 트라이를 하나 새로 만들고 a로 매핑한다.

5. 다음으로 a에 매핑된 트라이의 자식에 b에 매핑된 트라이가 있는지 확인한다.

6. 현재 b에 매핑된 자식이 없으므로 트라이를 하나 새로 만들고 b로 매핑한다.

7. 다음으로 b에 매핑된 트라이의 자식에 c에 매핑된 트라이가 있는지 확인한다.

8. 현재 c에 매핑된 자식이 없으므로 트라이를 하나 새로 만들고 c로 매핑한다.

9. c는 마지막 문자열이므로 c와 매핑된 트라이의 isEnd값은 true로 바꾼다.

10. 저장 후 트라이 상태는 아래와 같다.

 

 

트라이에서 문자열 탐색하기

b, ca, bo가 트라이에 저장되어 있는지 확인한다고 가정한다.

저장된 트라이의 모습은 다음과 같다.

 

b를 탐색

1. 트라이의 루트를 시작으로 자식에 b에 매핑된 트라이가 있는지 확인한다.

2. 매핑된 트라이가 있고 더 이상 탐색할 문자가 없으므로 b와 매핑된 트라이의 isEnd를 리턴한다.

3. isEnd가 false이므로 b는 해당 트라이에 존재하지 않는다고 판단한다. (실제로 b는 boi, boy, bo를 저장할 때 만들어진 노드일 뿐, 존재하는 단어가 아니기 때문에 isEnd가 false이다. 이 처리를 위해서 isEnd를 관리해야 한다.)

ca를 탐색

1. 트라이의 루트를 시작으로 자식에 c에 매핑된 트라이가 있는지 확인한다.

2. 매핑된 트라이가 없으므로 ca가 해당 트라이에 존재하지 않는다고 판단한다.

bo를 탐색

1. bo를 b, o로 자른다.

2. 트라이의 루트를 시작으로 자식에 b에 매핑된 트라이가 있는지 확인한다.

3. 매핑된 트라이가 있으므로 b에 매핑된 트라이의 자식에 o에 매핑된 트라이가 있는지 확인한다.

4. 매핑된 트라이가 있고 더 이상 탐색할 문자가 없으므로 o와 매핑된 트라이의 isEnd를 리턴한다.

5. isEnd가 true이므로 bo는 해당 트라이에 존재한다고 판단한다.

트라이 구현

트라이 클래스와 구현한 클래스를 사용하는 3가지 메서드를 소개한다.

트라이 클래스
  • 처음은 영어 문자 1개씩을 노드에 저장하기 위한 트라이이다. 따라서 총 26개의 트라이 배열을 만들어 두고 각 문자를 저장할 필요가 있을 때 새로 트라이를 생성하여 올바른 Index에 할당한다.
  • 그 아래는 Map을 활용하여 문자열과 트라이를 매핑해둔 구조이다. 기존 트라이의 응용 버전으로 생각하면 된다. 트라이 노드에 문자뿐만 아니라 문자열을 저장할 필요가 있을 때 사용하면 유용하다.
class Trie {
    //0이 a, 1이 b ..... 25가 z에 해당하는 트라이이다.
    Trie children[];
    boolean isEnd;

    Trie() {
        //초기에는 모두 null값으로 세팅된다.
        children = new Trie[26];
    }
}

class Trie {
    //문자열은 문자와 다르게 순서가 없다. 따라서 Map을 사용하여 문자열과 트라이를 매핑한다.
    Map<String, Trie> children;
    boolean isEnd;

    Trie() {
        //Map의 구현체로는 TreeMap이나 HashMap 어떤 것을 사용해도 좋다.
        this.children = new HashMap<>();
    }
}

 

3가지 메서드 (모든 메서드를 Map을 사용한 트라이를 기준으로 설명하겠다.)
  • insert
    • 문자열을 순차적으로 순회하면서 루트 노드부터 해당 문자가 children에 포함되어 있는지를 체크하고 만약 해당 노드의 children에 target과 매핑된 트라이가 없다면 새로운 트라이를 만들고 target과 매핑한다.
    • 마지막 문자까지 저장을 완료했다면 해당 노드의 isEnd 값을 true로 바꾸어 저장을 마친다.
  • search
    • 문자열을 순차적으로 순회하면서 루트 노드부터 해당 문자가 children에 포함되어 있는지 체크한다. 만약 해당 노드의 children에 target과 매핑된 트라이가 없다면 그 문자열은 존재하지 않는 것으로 판단한다.
    • 만약 마지막 문자까지 탐색이 완료되었다며 그 노드의 isEnd값을 리턴한다. 해당 노드의 isEnd 값이 true라면 실제 존재하는 문자열이며, false라면 존재하지 않는 문자열이다.
  • traverse
    • 루트 노드부터 존재하는 모든 노드들을 순회하는 코드이다. dfs 방식으로 구현되었다.
public static void insert(String[] word) {
    Trie current = root;

    for (int i = 0, size = word.length; i < size; i++) {
        String target = word[i];

        if (!current.children.containsKey(target)) {
            current.children.put(target, new Trie());
        }

        current = current.children.get(target);
    }
    current.isEnd = true;
}
public static boolean search(String word) {
    Trie currentTrie = root;

    for (int i = 0, size = word.length; i < size; i++) {
        String target = word[i];

        if(!current.children.containsKey(target)) return false;

        current = current.children.get(target);
    }

    return current.isEnd;
}
public static void traverse(Trie current) {
    for (String key: current.children.keySet()) {
        //이 곳에 필요한 코드를 작성하면 된다.

        traverse(current.children.get(key));
    }
}

백준 트라이 예제

 

문제 - 1 페이지

 

www.acmicpc.net

 

저작자표시 (새창열림)