[Algorithm] 트라이

* Python을 기준으로 합니다

---

트라이 (Trie)

- 개념

• 트라이 : 문자열 탐색을 위한 트리 형태의 자료구조
  • 어떠한 문자열 내에서 특정 단어를 검색한다고 하자
    - 직관적으로 문자별 단순 비교를 사용하는 경우 $O(n^{2})$의 time complexity를 가짐
    - 대신 트라이 구조를 적용하면 $O(n)$ 내에 탐색이 가능함
  • 이때 트라이는 일반적으로 사용되는 이진 트리 형식이 아닌 다진 트리($m$-ary Tree) 형태를 가짐
  • 장점
    - 트라이를 구성하면 완전히 일치하는 문자열이 아니라 일부를 생략하더라도 탐색이 가능함
    - 문자별로 트리가 만들어지기 때문에 자동적으로 정렬되는 효과가 있음
  • 단점
    - 문자의 수가 늘어날수록 메모리를 많이 사용함
    

트라이의 구조

- 구현

1. 노드 정의

• 트라이는 이진 트리가 아니라, 영어 alphabet 기준 26진 트리를 요구함
  • 특히 현재 문자 (key)에 대한 child 노드의 수가 정해져 있지 않으므로 이를 dictionary 형태로 표현함

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

2. 트라이 연산 정의

• `insert()` : 트라이에 문자열 삽입
• `search()` : 해당하는 단어가 트라이 내에 존재하는지 탐색
• `startswith()`: 해당하는 문자열로 시작하는 단어가 존재하는지를 판별

class Trie:
  def __init__(self):
    self.root = Node()

  def insert(self, word): #트라이 삽입
    cur = self.root
    for char in word: #주어진 문자열의 각 문자에 대해 child를 생성
      if char not in cur.children: #같은 문자가 없으면 child를 추가
        cur.children[char] = Node(char)
        
      cur = cur.children[char] #같은 문자가 있으면 해당 child로 이동
      
    cur.data = word # 문자열이 끝나는 노드의 data에 해당 문자열을 저장

  def search(self, word): #트라이 내 문자열 검색
    cur = self.root
    for char in word:
      if char not in cur.children: #주어진 문자가 child 중에 없으면
        return False
      
      cur = cur.children[char] #해당 child로 이동
    
    return cur.data

  def startswith(self, prefix): #주어진 prefix로 시작하는 문자열이 존재하는지 판별
    cur = self.root
    for char in prefix:
      if char not in cur.children:
        return False
      
      cur = cur.children[char]
      
    return True

3. 트라이 구현 결과 확인

trie = Trie()

#트라이 삽입
trie.insert('program')
trie.insert('predict')

print(trie.search('program')) #program
print(trie.search('predict')) #predict

print(trie.search('programmer')) #False
print(trie.search('prefix')) #False

print(trie.startswith('pro')) #True
print(trie.startswith('pre')) #True
print(trie.startswith('pri')) #False

#트라이 삽입
trie.insert('project')
trie.insert('produce')

print(trie.search('project')) #project
print(trie.search('produce')) #produce