트라이(Trie)란?

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.

• 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다.

• 래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree)라고도 한다. 트라이는 retrieval tree에서 나온 단어이다.

• 예를 들어 'Datastructure'라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고, 다음에 'a', 't', ... 의 순서로 찾으면 된다. 이러한 개념을 적용한 것이 트라이(Trie)이다.

트라이(Trie) 장단점

• 트라이(Trie)는 문자열 검색을 빠르게 한다.

• 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다.

• 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다. (메모리 측면에서 비효율적일 수 있음!)

예제를 통한 트라이(Trie)의 이해

'abc', 'ab', 'car' 단어들을 'abc'부터 트라이에 저장한다고 가정해보자.

1. 'abc' 트라이(Trie)에 삽입

   • 첫 번째 문자는 'a'이다. 초기에 트라이 자료구조 내에는 아무것도 없으므로 Head의 자식노드에 'a'를 추가해준다.
   • 'a'노드에도 현재 자식이 하나도 없으므로, 'a'의 자식노드에 'b'를 추가해준다.
   • 'c'도 마찬가지로 'b'의 자식노드로 추가해준다.
   • 'abc' 단어가 여기서 끝남을 알리기 위해 현재 노드에 abc라고 표시한다. (Data)

2. 'ab' 트라이(Trie)에 삽입

   • 현재 Head의 자식노드로 'a'가 이미 존재한다. 따라서 'a'노드를 추가하지 않고, 기존에 있는 'a'노드로 이동한다.
   • 'b'도 'a'의 자식노드로 이미 존재하므로 'b'노드로 이동한다.
   • 'ab' 단어가 여기서 끝이므로 현재 노드에 ab를 표시한다.

3. 'car' 트라이(Trie)에 삽입

   • Head의 자식노드로 'a'만 존재하고, 'c'는 존재하지 않는다. 따라서 'c'를 자식노드로 추가한다.
   • 'c'의 자식노드가 없으므로 마찬가지로 'a'를 추가한다.
   • 'a'의 자식노드가 없으므로 마찬가지로 'r'을 추가한다.
   • 'car' 단어가 여기서 끝이므로 현재 노드에 car를 표시한다.

모든 그림의 출처 : 링크

트라이(Trie) 구현 (Python)

Python의 Dictionary자료형을 이용하여 트라이(Trie)를 구현해보자.

먼저 Node를 아래와 같이 생성한다.

Node

• key에는 해당 노드의 문자가 들어가고, child에는 자식노드가 포함되게 된다.
• data는 문자열이 끝나는 위치를 알려주는 역할을 한다.
  (Ex) 'car'가 'r'에서 끝날 때, 'r'을 key로 가지는 노드의 data에 'car'를 입력한다.
• 해당 노드에서 끝나는 문자열이 없을 경우에는 그대로 None으로 내비둔다.

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}

두 번째, Dictionary자료형을 이용하여 트라이(Trie)를 구현해보자.

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(None)

    # 문자열 삽입
    def insert(self, string):
        curr_node = self.head

        # 삽입할 String 각각의 문자에 대해 자식Node를 만들며 내려간다.
        for char in string:
            # 자식Node들 중 같은 문자가 없으면 Node 새로 생성
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)

            # 같음 문자가 있으면 노드를 따로 생성하지 않고, 해당 노드로 이동
            curr_node = curr_node.children[char]

        # 문자열이 끝난 지점의 노드의 data값에 해당 문자열을 표시
        curr_node.data = string


    # 문자열이 존재하는지 탐색!
    def search(self, string):
        # 가장 아래에 있는 노드에서부터 탐색 시작한다.
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        # 탐색이 끝난 후에 해당 노드의 data값이 존재한다면
        # 문자가 포함되어있다는 뜻이다!
        if curr_node.data is not None:
            return True

• 트라이의 생성 시간 복잡도는 O(MxL), 탐색 시간 복잡도는 O(L)이다.
  제일 긴 문자열의 길이를 L이라 하고, 총 문자열들의 수를 M이라 할 때 시간 복잡도는 위와 같다.
  생성 시간 복잡도는 모든 문자열 M개를 넣어야하고, M개에 대해서 트라이에 넣는건 가장 긴 문자열 길이인 L만큼 걸리므로 O(MxL)의 시간 복잡도를 가진다. (삽입은 O(L)이다.)
  탐색 시간 복잡도는 트리를 제일 깊게 탐색하는 경우는 가장 긴 문자열 길이인 L까지 깊게 들어가는 것이므로 O(L)의 시간 복잡도를 가진다.

트라이(Trie)에서 문자열 탐색

위에서 트라이 자료구조에 데이터를 삽입해보았는데, 이를 바탕으로 트라이에서 문자열 탐색을 진행해보려 한다.

1. 위의 트라이에 'abc' 문자열이 있는지 탐색해보자.

   • Head의 child에 'a'가 존재 --> 'a'노드(key='a')로 이동
   • 'a'노드의 child에 'b'가 존재 --> 'b'노드(key='b')로 이동
   • 'b'노드의 child에 'c'가 존재 --> 'c'노드(key='c')로 이동
   • 문자열 탐색이 완료됨 --> 현재 노드('c'노드)에 Data값이 존재! --> 따라서 'abc'라는 문자열이 존재함을 알 수 있음

2. 'ca'라는 문자열이 있는지 탐색해보자.

   • Head의 child에 'c'가 존재 --> 'c'노드(key='c')로 이동
   • 'c'노드의 child에 'a'가 존재 --> 'a'노드(key='a')로 이동
   • 문자열 탐색이 완료됨 --> 현재 노드('a'노드)에 Data값이 없음! --> 따라서 'ca'라는 문자열은 존재 X