210126 개발일지(50일차) - 트라이(Trie) 알고리즘 개념 및 파이썬에서 구현하기(feat. Class)

트라이(Trie)란?

트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 한다.
retrieval(탐색)에서 trie를 따왔다고도 한다.
이 자료구조를 활용해 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 등을 한다고 한다.

사용 목적

문자열의 탐색을 할 때, 단순하게 하나씩 비교하면서 탐색을 하는것보다 시간복잡도 측면에서 훨씬 효율적이다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다.

시간 복잡도

제일 긴 문자열의 길이를 L 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같다.

• 생성 시간 복잡도 : O(M*L), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(M*L)만큼 걸립니다. 물론 삽입 자체만은 O(L)만큼 걸린다.
• 탐색 시간 복잡도: O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸린다.

트라이 구조 예시

아래 예시는 "ab", "abc", "car" 문자들을 저장한 트라이다.

(오늘 그림의 모든 출처 : https://youseop.github.io/2020-11-09-BAEKJOON-14425_%EB%AC%B8%EC%9E%90%EC%97%B4%EC%A7%91%ED%95%A9)

“abc”→ "ac" → “car”을 순서대로 저장한다고 가정해보자.

1. 먼저, “abc”를 넣어보자.
   1-1. 첫번째 문자는 “a”이다. 초기에 trie 자료구조 내에는 아무것도 추가되어있지 않음으로 Head의 자식노드에 “a”를 추가해준다.
   1-2. “a”노드에도 현재 자식이 하나도 없음으로, “b”를 자식노드인 “a”의 자식으로 추가해준다.
   1-3. “c”도 마찬가지로 “b”의 자식노드로 추가해준다.
   1-4. “abc”라는 단어가 여기서 끝남을 알리기 위해 현재 노드에 abc라고 표시한다.
   

2. 다음으로 “ab”를 추가해보자.
   2-1. 현재 Head의 자식 노드로 “a”가 이미 존재한다. 따라서 “a”노드를 추가하지 않고, 기존에 있던 “a”노드로 이동한다.
   2-2. “b”도 “a”의 자식노드로 이미 존재한다. “b”노드로 이동하자.
   2-3. 여기서 “ab”라는 단어가 끝이 남으로, 현재 노드에 ab를 표시한다.

3. 마지막으로 “car”를 추가하자.
   3-1. Head의 자식 노드로, “a”만 존재하고 “c”는 존재하지 않는다. 따라서 “c”를 자식노드로 추가하자.
   3-2. “c”의 하위노드가 없음으로 마찬가지로 “a”를 추가한다. “r”에 대해서도 동일하다.
   “car”가 “r”노드에서 끝남으로 “car”를 표시해준다.
   

그림으로 표현

1. "abc" 추가
2. "ab" 추가
3. "car" 추가

파이썬에서 구현하기

• Node를 Class로 만들기
  - Key에는 해당 노드의 문자가 들어가고, Child에는 자식 노드가 포함되게 된다.
  - Data는 문자열이 끝나는 위치를 알려주는 역할을 한다. 예를 들어서 “car”이 “r”에서 끝날 때, “r”을 key로 가지는 노드의 data에 “car”를 입력한다.해당 노드에서 끝나는 문자열이 없을 경우에는 None으로 그대로 놔둔다.

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

  

• Trie구조 만들기 : 삽입과 검색기능 구현

  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
      # 문자열이 존재하는지 search
      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 != None:
              return True