자료구조 - 트라이(Trie)

트라이의 개념

트라이(Trie)란 문자열 검색을 빠르고 효율적으로 수행하기 위해 설계된 트리 기반 자료구조다. 트라이라는 이름은 검색을 의미하는 "retrieval"에서 유래했다. 트라이는 주로 문자열 키를 저장하고 검색하는 데 사용되며, 키가 공통 접두사를 공유하는 경우 메모리와 시간 측면에서 이점을 제공한다. 따라서 접두사 트리(Prefix Tree)라고도 불린다.

트라이의 구조

트라이는 문자열 키를 노드의 계층 구조로 저장한다. 각 노드는 개별 문자를 나타내며, 루트 노드에서부터 시작해서 문자열의 각 문자에 따라 하위 노드로 이동하면서 키를 구성한다.

• 루트 노드는 공백 문자 또는 빈 상태로 시작
• 자식 노드는 알파벳, 숫자, 특수 문자 등 허용된 문자 중 하나를 나타냄
• 문자열의 끝은 종단 노드(End of Word Node)로 표시

위 그림을 트라이에 저장되는 구조로 다시 표현해보면 아래와 같다. (참고로 아래의 경우, 종단 노드 대신 isEnd 프로퍼티를 사용해서 문자열의 끝을 표시했다.)

 

트라이의 시간복잡도

문자열이 N개 있고, 문자열의 평균 길이가 L일 때의 시간 복잡도를 살펴보자.

트라이 생성 시간복잡도

문자열 N개를 트라이에 삽입할 때의 시간복잡도는 O(N*L)이다. 각 문자열의 문자를 하나씩 처리하며 트라이에 삽입하므로, 문자열 길이에 비례한 시간이 소요된다.

문자열 검색 시간복잡도

트라이에서 특정한 문자열을 검색하는 시간복잡도는 O(L)이다. 루트 노드에서 시작해 문자열의 각 문자를 따라가며 탐색하기 때문이다. 탐색 과정에서 각 노드의 자식 노드로 이동하는 작업이 O(1) 시간에 이루어지므로, 전체 탐색 시간은 문자열의 길이에만 의존한다.

공통 접두사 검색

공통 접두사를 탐색하는 작업 또한 O(L) 시간에 수행된다. 접두사의 길이에 비례하여 탐색 경로를 따라가며 확인하기 때문이다.

 

 

트라이의 장점과 단점

장점

• 문자열 검색이 O(L) 시간에 수행되어 빠른 검색이 가능하다.
• 접두사 기반 문자열 검색에 최적화 되어 있다.

단점

• 문자 집합의 크기에 따라 각 노드가 많은 자식 노드를 가지므로 메모리 사용량이 증가할 수 있다.
• 단순 배열이나 해시맵보다 구조가 복잡해 구현 난이도가 높다.

 

트라이의 사용 사례

• 문자열 검색 및 자동완성
  • 사전 구현: 문자열을 빠르게 검색하고, prefix 기반 검색을 효율적으로 처리할 때
  • 자동완성 시스템: 사용자가 입력하는 도중에 가능한 단어들을 빠르게 찾아주는 기능에 사용
• 문자열 패턴 매칭, 문자열 필터링
  • 문자열 패턴 매칭: 여러 개의 문자열 패턴을 효율적으로 처리해야 할 때(ex. DNA 염기 서열 패턴 매칭)
  • 문자열 필터링: 특정 문자열을 포함한 데이터를 찾거나 제외하는 경우
• 접두어 기반 검색
  • 단어의 접두어를 기반으로 빠르게 일치하는 문자열을 찾을 때
  • IP 주소 라우팅: 네트워크 라우팅 테이블에서 IP 주소의 접두사를 빠르게 탐색(ex. CIDR(Classless Inter-Domain Routing) 기반 라우팅)
• 데이터 압축
  • Lempel-Ziv-Welch(LZW) 알고리즘과 같이 중복된 문자열을 효과적으로 저장하여 데이터 압축에 사용

 

트라이 구현 (Python)

class TrieNode:
  def __init__(self):
    self.children = {}
    self.isEnd = False
    
class Trie:
  def __init__(self):
    self.root = TrieNode()
  
  def insert(self, word): # 트라이에 단어를 삽입하는 메소드
    node = self.root
    
    for char in word:
      if char not in node.chlidren:
        node.children[char] = TrieNode()
      node = node.children[char]
    node.isEnd = True # 단어의 끝을 표시
  
  def search(self, word): # 트라이에서 특정한 단어를 찾는 메소드
    node = self.root
    for char in word:
      if char not in node.children:
        return False
      node = node[char]
    return node.isEnd
    
  def starts_with(self, prefix): # 트라이에서 특정 접두사로 시작하는 단어가 있는지 확인하는 메소드
    node = self.root
    for char in perfix:
      if char not in node.children:
        return False
      node = node.children[char]
    return True
    
 # 사용 예시
 trie = Trie()
 trie.insert("apple")
 trie.insert("app")
 trie.insert("banana")
 
 print(trie.search("apple")) # True
 print(trie.search("ban")) # False
 
 print(trie.starts_with("app")) # True
 print(trie.starts_with("ban")) # True