Trie(트라이)란?
- 트리형 자료구조이다.
- 문자열 검색을 효율적으로 저장하고 탐색하기 위해 사용된다.
- 중복해서 단어를 저장할 필요가 없다.
Trie의 구조
루트 노드
- 트리의 최상위 노드이며, 보통 빈 값을 가진다.
노드
- 문자 : 노트가 나타내는 문자
- 자식 노드 : 해당 문자의 다음 문자를 나타내는 자식 노트의 리스트
- 종료 플래그 : 해당 노드가 문자열의 끝인지 여부를 나타내는 플래그
Trie의 주요 연산
삽입 (Insert)
- 삽입하고자 하는 문자열의 한 글자씩 가져온다.
- 트리의 루트부터 적합한 노드 위치를 찾아가면서 저장한다. 이 때, 없으면 새 노드를 생성한다.
- 마지막 글자까지 삽입이 되면 isEnd 플래그로 단어의 끝을 표시한다.
검색 (Search)
- 입력받은 문자열을 한글자씩 파싱(Parsing)한다.
- Trie의 루트 노트 파싱된 문자를 앞에서부터 비교하며 노드가 존재하는 지 확인한다.
- 해당 문자 노드가 존재하지 않거나, 리프 노드(자식의 개수가 0인 노드)에 도달할 때까지 탐색한다.
삭제 (Delete)
- 문자열을 검색한 후, 마지막 문자에서부터 역으로 노드를 제거한다.
- 노드가 다른 문자열의 일부로 사용되지 않는 경우에만 삭제한다.
Trie의 장점
- 효율적인 검색이 가능하다. ( O(l) 시간 복잡도, 여기 l은 검색할 문자열의 길이를 의미 )
- 특정 접두사로 시작하는 모든 문자열을 쉽게 찾을 수 있다.
- 자동완성 즉, 검색어 제안 기능 구현에 적합하다.
Trie의 단점
- 각 노드가 자식 노드의 포인터를 가지므로 메모리 사용이 비효율적일 수 있다.
- 구현의 복잡성이 높다. 특히 삭제 기능을 구현할 때는 주의가 필요하다.
Trie 예제
TrieNode 클래스
class TrieNode {
TrieNode[] children; // 자식 노드
boolean isEndOfWord; // 단어의 끝 여부
public TrieNode() {
children = new TrieNode[26]; // 알파벳 소문자 26개
isEndOfWord = false; // 초기화
}
}Trie 클래스
class Trie {
private TrieNode root; // 루트 노드
public Trie() {
root = new TrieNode(); // 루트 노드 생성
}
// 문자열 삽입
public void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a'; // 문자 인덱스 계산
if (node.children[index] == null) {
node.children[index] = new TrieNode(); // 자식 노드 생성
}
node = node.children[index];
}
node.isEndOfWord = true; // 단어의 끝 표시
}
// 문자열 검색
public boolean search(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (node.children[index] == null) {
return false; // 문자가 없으면 false
}
node = node.children[index];
}
return node.isEndOfWord; // 단어의 끝 여부 반환
}
}사용 예시
public class Main {
public static void main(String[] args) {
Trie trie = new Trie();
// 문자열 삽입
trie.insert("apple");
trie.insert("app");
// 문자열 검색
System.out.println(trie.search("apple")); // true
System.out.println(trie.search("app")); // true
System.out.println(trie.search("appl")); // false
System.out.println(trie.search("banana")); // false
}
}설명
- TrieNode 클래스
각 노드는 26개의 자식 노드 배열과 단어의 끝을 나타내는 플래그를 포함한다.
- Trie 클래스
insert : 주어진 문자열을 Trie에 삽입한다.
search : 주어진 문자열이 Trie에 존재하는 지 확인한다.
⊙ 참고 문헌
- 김하은, 「백엔드 취업 파트타임 스쿨 5기:Part 09. 실전 배당금 프로젝트-Chapter 04. 서비스 구현-09_자동완성 01」, 제로베이스, 2024, https://zero-base.co.kr/
- interview Cake, Trie Data Structure, 2024년 10월 05일, https://www.interviewcake.com/concept/java/trie
- ChatGPT, "Trie(트라이) 자료구조"에 대한 답변, 2024년 10월 05일, https://chatgpt.com/
- ChatGPT, "Trie 자료구조 간단한 예제"에 대한 답변, 2024년 10월 05일, https://chatgpt.com/