Trie(트라이)

개요

여러 개의 문자열 중 특정 문자열을 찾을 때 효과적인 트라이(Trie) 자료구조에 대해 알아보자

 

먼저, 이름은 retrieval(검색) tree에서 따왔다 정도의 유래가 있는듯하다.

 

위에서 말한바와 같이 여러 개의 문자열 중 특정 문자열을 찾을 때 

하나하나 확인한다면 O(n) (n은 list의 길이)의 시간복잡도를 가지거나

정렬 후 이진 탐색을 사용한다면 O(nlog n)의 시간복잡도를 가지는 반면, 

트라이의 경우 최선일 경우 O(1), 최악일 경우에도 O(m) (m은 문자열의 길이) 안에 할 수 있다고 한다.

 

따라서, 문자열이 아주 길거나 자동 완성 및 검색어 추천 기능 등에서 Trie 자료구조를 통해 효과를 볼 수 있다.

 

형태

출처: https://rebro.kr/86

문자열 집합 {'rebro', 'replay', 'hi', 'high', 'algo'}를 트라이로 구현한 모습

집합에 포함된 문자열의 접두사에 대응되는 노드들이 서로 연결된 트리다.

빨간 노드는 문자열의 끝(flag)을 나타내는데, 변수를 따로 추가해 저장된 단어의 끝을 구분한다.

 

장단점

• 트라이의 장점은 문자열을 찾는 속도가 매우 빠르다는 점
• 단점은 자식 노드를 가리키는 포인터를 다 저장해야 되는데다,
  최악의 경우 집합에 포함되는 문자열 길이의 총합만큼 노드가 필요하기 때문에
  필요한 메모리의 크기가 매우 크다는 점이 있다.

* 이러한 단점을 보완한 redix tree(or trie)라는게 있다.

 

예시 문제

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

 

코드

import sys
input = sys.stdin.readline
from collections import defaultdict


class TrieNode:
  def __init__(self):
    self.end = False
    self.cnt = 0
    self.children = defaultdict(TrieNode)


class Trie:
  def __init__(self):
    self.root = TrieNode()
    self.consistency = True

  def insert(self, tel: str) -> None:
    if not self.consistency:
      return
    node = self.root
    for char in tel:
      if not char.isdigit():
        continue
      node = node.children[char]
      node.cnt += 1
      if node.end:
        self.consistency = False
        return
    node.end = True
    if node.cnt > 1:
      self.consistency = False

  def check_consistency(self) -> bool:
    return self.consistency


for _ in range(int(input())):
  N = int(input())
  trie = Trie()
  for _ in range(N):
    trie.insert(input().strip())
  print('YES') if trie.check_consistency() else print('NO')

당장은 안와닿기도 하고 해당 문제에 대해선 오히려 정렬을 통해 푸는게 더 메모리, 시간에 대해 효율적이기 때문에

일단 Trie 자료구조를 사용해 푸는 방법이 있다 정도만 메모해놓고 

나중에 다시 볼 예정