목차
- 트라이의 개념 및 구조
- 트라이의 동작 방식
- 트라이의 시간 복잡도와 효율성
- 해시 테이블과 비교
1. 트라이의 개념 및 구조
트라이는 문자열을 저장하기 위해 특화된 트리 형태의 자료 구조로, 노드들이 문자 배열 형태로 구성되어 있음.
각 노드는, 다음 문자로 이어지는 자식 노드들을 배열 형태로 가짐.
(영어 알파벳 기준으로 보면 각 노드는 최대 26개의 포인터(또는 링크)를 가짐.)
1-1. "hello"를 저장할 경우
- 루트 노드에서 'h' 자식 노드로 이동
- 그 다음 'e' 자식 노드로 이동
- 'l' → 'l' → 'o' 순으로 이동하며 노드 연결
이 구조를 통해, 공통 접두사를 갖는 문자열들이 같은 경로를 공유 가능.
2. 트라이의 동작 방식
Hermione, Harry, Hagrid를 트라이에 저장
예를 들어, "Harry"를 검색하는 경우, H → a → r → r → y 순으로 탐색.
또한, 특정 접두사를 갖는 모든 단어 검색(prefix search)에 매우 효과적.
(예: "Ha"로 시작하는 모든 단어 검색 시, "Ha"까지 도달한 뒤 서브트리 전체 순회하면 됨.)
2-1. 트라이 구조
Root
└── H
├── e → r → m → i → o → n → e (Hermione)
├── a → r → r → y (Harry)
└── a → g → r → i → d (Hagrid)- 이처럼 같은 접두사(H, Ha 등)를 공유하는 노드는 한 번만 저장됨.
- 메모리 효율적으로 사용 가능.
3. 트라이의 시간 복잡도와 효율성
문자열 검색 시간은 문자열 길이 n에 비례하여 O(n).
대부분의 이름은 상수에 가까운 짧은 길이를 가지므로 실질적으로는 O(1)에 가까운 성능.
삽입, 삭제 연산 역시 동일하게 O(n).
3-1. 트라이 검색 예시
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = 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.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end- insert: 각 문자를 따라가며 없으면 새 노드를 추가
- search: 각 문자를 순서대로 따라가면서 마지막 노드가 단어의 끝인지 확인
4. 해시 테이블과 비교
4-1. 트라이의 장점
- 접두사 검색 효율적: 공통 접두사를 기반으로 저장되어, 특정 접두사로 시작하는 단어들을 빠르게 검색 가능
- 정렬된 데이터 검색 용이: 사전순 정렬된 결과를 쉽게 도출 가능 (DFS 순회로 가능)
- 충돌 없음: 해시 테이블과 달리 충돌 개념이 없기 때문에 충돌 해소 로직이 불필요함
4-2. 트라이의 단점
- 메모리 사용 많음: 각 노드가 많은 자식 포인터를 갖기 때문에, 저장할 데이터가 적을 경우 오히려 비효율적일 수 있음
- 삽입 속도 느릴 수 있음: 해시 테이블은 O(1)에 가깝게 삽입 가능하지만, 트라이는 삽입할 때 문자열 길이만큼 탐색 및 생성 필요
4-3. 해시 테이블과의 비교
- 트라이는 접두사 검색 및 정렬된 데이터 저장이 필요할 경우 유리하며, 빠른 삽입과 검색이 필요한 상황에서는 해시 테이블이 효율적.