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

트라이 자료구조

문자열의 집합을 표현하는 트리 자료구조 이다.

문자열에서의 검색을 빠르게 해주는 자료구조로 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 쓰이고 있으며 검색을 뜻하는 Retrieval의 중간 음절에서 따와 Trie라고 불린다고 한다.

원하는 원소를 찾기 위해 사용되는 이진 검색 트리 등에서는 원소를 찾는데 O(logN)의 시간이 걸리게 된다.

하지만 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다.

이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)이다.

작동 원리

다음 그림은 문자열 집합 {"rebro", "replay", "hi" , "high", "algo"} 를 트라이로 구현한 것이다.

트라이는 한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 빨간색으로 나타낸 리프 노드는 문자열의 끝을 의미한다.

트라이는 문자열을 탐색하기 위한 자료구조이므로 문자열 탐색을 위해서는 다음 글자에 해당하는 노드를 타고 따라가면 된다.

또 트라이의 중요한 속성 중 하나는 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면, 찾고자 하는 문자열의 접두사를 얻을 수 있다.

예를 들어서 "rebro"를 찾는다고 해보자.
r -> re -> reb -> rebr -> rebro의 순서로 탐색되므로 "rebro"의 모든 접두사들이 다 구해지게 된다.

장단점

• 장점
  문자열을 빠르게 찾을 수 있다.
  문자열을 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 문자열의 추가와 탐색이 모두 O(M)만에 가능하다.

• 단점
  필요한 메모리의 크기가 너무 크다.
  문자열이 모두 알파벳 소문자로만 이루어진 경우라고 해도, 1 depth에 a~z까지 26개의 공간이 필요하게 된다.
  
  이 단점을 해결하기 위해 보통 map이나 vector를 이용하여 필요한 노드만 메모리를 할당하는 방식들을 이용하는데, 문제에 따라서 메모리 제한이 적은 경우에는 최적화가 까다롭다.
  

구현 (Java)

[백준] 5052번 : 전화번호 목록
이 문제를 통하여 코드를 구현했고 일반적인 트리와 비슷하게 구현했다.
주어지는 전화번호 목록 내의 한 전화번호가 다른 전화번호의 접두사가 되면 일관성 있는 전화번호 목록이라고 할 때 이를 판별하는 문제이다.

1. 생성자/클래스 정의

class TrieNode {
    TrieNode[] child = new TrieNode[10]; // 0~9 까지 저장
    boolean isLeaf = true; // 리프노드 여부
    char val; // 현재 노드의 값;

    public TrieNode(char val) {
        this.val = val;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode(' ');
    }
}

2. 문자열 추가

class TrieNode {
    TrieNode[] child = new TrieNode[10]; // 0~9 까지 저장
    boolean isLeaf = true; // 리프노드 여부
    char val; // 현재 노드의 값;

    public TrieNode(char val) {
        this.val = val;
    }

    void insert(String str, int idx) {
        // 문자열을 끝까지 확인했다면 종료
        if (str.length() == idx) {
            return;
        }
        char curChar = str.charAt(idx);
        int curCharIdx = str.charAt(idx) - '0';
        // 이번에 저장할 문자 인덱스에 해당하는 노드가 null이라면 새로 생성
        if (this.child[curCharIdx] == null || this.isLeaf) {
            this.child[curCharIdx] = new TrieNode(curChar);
            this.isLeaf = false;
        }
        // 다음 문자 저장
        this.child[curCharIdx].insert(str, idx + 1);
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode(' ');
    }

    void insert(String str) {
        root.insert(str, 0);
    }
}

전체 코드

package main.java.백준.전화번호목록;

import java.util.*;

class TrieNode {
    TrieNode[] child = new TrieNode[10]; // 0~9 까지 저장
    boolean isLeaf = true; // 리프노드 여부
    char val; // 현재 노드의 값;

    public TrieNode(char val) {
        this.val = val;
    }

    void insert(String str, int idx) {
        // 문자열을 끝까지 확인했다면 종료
        if (str.length() == idx) {
            return;
        }
        char curChar = str.charAt(idx);
        int curCharIdx = str.charAt(idx) - '0';
        // 이번에 저장할 문자 인덱스에 해당하는 노드가 null이라면 새로 생성
        if (this.child[curCharIdx] == null || this.isLeaf) {
            this.child[curCharIdx] = new TrieNode(curChar);
            this.isLeaf = false;
        }
        // 다음 문자 저장
        this.child[curCharIdx].insert(str, idx + 1);
    }

    boolean isConsistency(String str, int idx) {
        // 문자열을 끝까지 확인했다면 결과 리턴
        if (str.length() == idx) {
            // 끝까지 봤는데 그게 리프노드면 일관성 있는거고 아니면 없는거
            return isLeaf;
        }
        // 다음 문자 확인
        int curCharIdx = str.charAt(idx) - '0';
        if (!this.isLeaf) {
            if (this.child[curCharIdx] != null)
                return this.child[curCharIdx].isConsistency(str, idx + 1);
        }
        return false;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode(' ');
    }

    void insert(String str) {
        root.insert(str, 0);
    }

    boolean isConsistency(String str) {
        return root.isConsistency(str, 0);
    }
}

public class Solution {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- != 0) {
            int n = sc.nextInt();
            sc.nextLine();

            Trie trie = new Trie();
            List<String> numList=  new ArrayList<>();
            for(int i=0;i<n;i++) {
                String str = sc.nextLine();
                numList.add(str);
                trie.insert(str);
            }
            boolean res = true;
            for(int i=0;i<n;i++) {
                if(!trie.isConsistency(numList.get(i))) {
                    res = false;
                    break;
                }
            }
            System.out.println(res?"YES":"NO");
        }
    }
}