CS 자료구조 Trie(트라이)

 

트라이는 주로 문자열 검색에 사용되는 특수한 형태의 자료구조다. 많은 문자열이 공통된 접두사를 가질 때 효율적인 탐색을 제공하도록 설계되어 있다. 트라이는 사전(Dictionary)처럼 동작하며, 문자열의 삽입, 검색, 삭제 등의 연산을 빠르게 수행할 수 있다.

 

ㅇ 트라이의 특징

• 노드 구조
  트라이의 각 노드는 하나의 문자(Character)를 나타내며, 자식 노드들로 연결된다.
  각 경로는 특정 문자열의 접두사를 나타낸다.
• 루트 노드
  트라이의 시작점으로, 빈 문자열을 표현하거나 의미 없는 노드로 시작한다. 모든 문자열의 경로가 이 루트에서부터 시작 된다.
• 삽입 연산
  문자열을 삽입할 때는 문자열의 각 문자를 노드로 변환하여 차례대로 삽입한다. 공통된 접두사를 가진 문자열은 동일한 경로를 공유하며, 공통 접두사 이후부터 새로운 경로가 만들어진다.
• 검색 연산
  특정 문자열이 트라이에 존재하는지 확인할 때, 루트 노드에서부터 각 문자를 순차적으로 따라가며 해당 문자열의 경로가 있는지 탐색한다.
• 효율성
  각 문자의 길이에 따라 탐색과 삽입이 이루어지므로, 시간 복잡도는 O(L)이다. 여기서 L은 검색 또는 삽입하려는 문자의 길이를 의미한다. 

 

ㅇ 트라이의 장단점

장점

• 빠른 검색
  문자열의 접두사에 따라 노드를 탐색하므로, 문자열의 길이에 비례해 빠르게 검색할 수 있다.
• 중복 데이터 최소화
  공통된 접두사를 가진 문자열이 같은 경로를 공유하므로, 메모리 사용이 최적화 된다.
• 자동완성(Auto-complete) 및 사전(Dictionary) 구현에 유리함
  트라이는 접두사를 기반으로 하는 검색에 최적화되어 있어, 입력된 문자열의 접두사를 통해 해당하는 모든 문자열을 빠르게 찾을 수 있다.

단점

• 메모리 사용량
  공통된 접두사를 활용하여 중복을 줄이긴 하지만, 전체적인 구조에서 각 문자마다 노드가 필요하므로 메모리 사용량이 클 수 있다.
• 복잡성
  노드의 수가 많아질수록 트라이의 구조가 복잡해지고, 구현하는데 있어 관리해야할 노드들이 많아질 수 있다.

 

ㅇ 트라이의 응용

• 문자열 검색 및 자동 완성
  접두사를 기반으로 빠르게 단어를 찾는 기능을 구현할 수 있어, 검색엔진이나 자동완성 기능에 많이 사용된다.
• 단어 필터링
  특정 단어를 포함하거나 금지된 단어를 빠르게 찾아내는데 사용할 수 있다.
• 사전 및 단어 정렬
  문자열을 사전 순서대로 저장하고 검색하는데 적합한 자료구조다.