[코딩인터뷰] 트라이 자료 구조 Trie data structure

트라이 자료 구조 Trie data structure

문자열 검색에 특화된 트리 자료 구조

트라이 자료 구조는 기본적으로 트리 형태로 구성되는데, 언어의 문자가 제한되어 있다는 특징을 활용한 자료 구조입니다. 트라이 자료 구조는 아래 그림과 같이, 단어를 문자의 형태와 순서를 기준으로 트리를 구성하는 자료구조입니다. 예를 들어, tea 라는 단어를 트라이 자료 구조에 추가하게 되면 root 노드부터 시작해서 t, e, a 순서로 트리에 추가합니다. 이렇게 여러 단어가 추가된 트라이 자료 구조에서 tea 로 시작하는 단어를 찾는다면, 모든 단어를 하나 하나 첫 문자부터 비교하며 검색할 필요없이 트라이 자료 구조의 tea 노드의 자식 노드만 탐색하면 됩니다.

트라이 자료 구조

특히 영어의 알파벳은 한글과 달리 문자가 나열되는 형태이면서 26 자로만 이루어져 있기 때문에, 트라이 자료 구조를 활용해서 문자열을 검색하면 효율적입니다. 반면 한자와 같이 한 글자 한 글자가 의미가 있는 문자의 경우 트리아 자료 구조로 문자열 검색을 하더라도, 다른 언어에 비해 효율이 떨어지게 됩니다.

트라이 자료 구조는 단어의 문자 하나가 트리의 노드가 되므로, 특정 단어를 찾을 때 단어의 문자 수 만큼 탐색을 해야 단어를 찾을 수 있습니다. 즉, 탐색에 O(단어의 문자 수) 시간이 걸립니다.

트라이 자료 구조는 트리 형태 자료 구조이므로 각 노드는 검색에 활용할 문자와 연결된 데이터 그리고 자식 노드의 포인터를 가지고 있어야 합니다. 따라서 알파벳으로 된 트라이 자료 구조의 노드를 꽉 채우면 26 개의 자식 노드 포인터를 리스트로 가지게 됩니다. 따라서 노드가 많아져서, 더 깊이 들어가게 될수록 필요한 메모리가 거의 26 배수로 증가하게 됩니다.

Python 3 구현

class TrieNode:
    """ 트라이 자료 구조에 사용될 노드"""

    def __init__(self, char):
        # 탐색에 기준이 되는 문자
        self.char = char

        # 자식 노드 포인터
        # 검색을 편하게 하기 위해 dict 을 사용한다. 
        self.children = {}

        # 자료구조에서 단어를 검색할 때, 얻고자 하는 데이터는 노드에 추가하면 된다.

    def is_leaf():
        return True if self.children else False

노드 별로 필요한 정보는 TrieNode 클래스에 추가하면 됩니다. 대부분 특정 문자의 counter 를 저장하거나, 단어에 데이터를 저장하고 검색합니다.

class Trie(object):
    """트라이 자료 구조"""

    def __init__(self):
        """ 루트 노드 """
        self.root = TrieNode("")

    # 함수에 데이터 매개변수를 추가해서 노드에 기록해도 된다.
    def add(self, word):
        """새로운 단어를 자료 구조에 추가한다."""
        node = self.root

        for char in word:
            # 모든 문자를 순회한다.
            if char in node.children:
                # 자료 구조에 이미 존재하는 문자일 경우 다음 노드로 이동한다.
                node = node.children[char]
            else:
                # 자료 구조에 없는 노드일 경우 노드를 추가한다.
                new_node = TrieNode(char)
                node.children[char] = new_node
                node = new_node

    def search(self, prefix):
        """자료 구조에서 단어 노드를 탐색한다."""
        node = self.root

        for char in prefix:
            if char in node.children:
                node = node.children[char]
            else:
                return None

       return node

위 구현을 기본으로 트리 자료 구조의 특성에 맞춰서 필요한 함수를 추가해서 사용하면 됩니다.

코딩 테스트에서...

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 4번 효율성 문제 는 트라이(Trie) 자료 구조 를 활용해야 해결할 수 있습니다.