Trie Tree 자료구조

Java로 Trie(트라이) 자료구조 구현하기

Trie(트라이)는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다. 주로 문자열 검색, 자동 완성 기능, 사전(단어 탐색) 등에 자주 사용됩니다. 이 포스팅에서는 Trie의 특징과 기본적인 Java 구현, 활용 사례를 살펴보겠습니다.

---

1. Trie(트라이)란?

Trie(트라이) 란 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다.
문자열을 검색하거나 접두사(prefix)를 판단할 때 O(M) (M은 문자열 길이)의 시간 복잡도를 갖습니다.

자동 완성이나 사전(Dictionary) 기능 등에서 많이 활용됩니다.

---

2. Trie 기본 구조

Trie는 보통 각 노드가 다음과 같은 정보를 가집니다

1. children: 자식 노드를 가리키는 배열 혹은 Map 구조

2. isEndOfWord: 해당 노드가 단어의 끝인지 여부 영어 소문자만 다룰 때는 TrieNode[26] 형태 배열을, 범용성을 높이기 위해서는 Map<Character, TrieNode>를 사용할 수 있습니다

   3. Java로 Trie 구현하기

   3.1. TrieNode 클래스

import java.util.HashMap; 
import java.util.Map;  
class TrieNode {     
	// 자식 노드를 저장하기 위한 자료구조     
	Map<Character, TrieNode> children = new HashMap<>();     
	// 어떤 단어의 끝을 나타내는지 여부    
	boolean isEndOfWord = false;
}

3.2. Trie 클래스

Trie에 삽입, 검색, 접두사 확인 등의 기능을 구현한 클래스입니다.

class Trie {      
	private TrieNode root;      
	// 생성자에서 루트 노드를 초기화     
	public Trie() {      
		root = new TrieNode();    
	}     
	// 1) 문자열 삽입   
	public void insert(String word) {    
		TrieNode current = root;        
		for (char c : word.toCharArray()) {    
			current.children.putIfAbsent(c, new TrieNode());     
			current = current.children.get(c);       
		}       
		current.isEndOfWord = true;    
	}      
	// 2) 문자열 검색     
	public boolean search(String word) { 
		TrieNode current = root;      
		for (char c : word.toCharArray()) {     
			if (!current.children.containsKey(c)) { 
				return false;            
			}         
			current = current.children.get(c);  
		}       
		return current.isEndOfWord;  
	}     
	// 3) 특정 접두사(prefix)로 시작하는 문자열이 있는지 확인 
	public boolean startsWith(String prefix) {  
		TrieNode current = root;    
		for (char c : prefix.toCharArray()) {   
			if (!current.children.containsKey(c)) {  
				return false;           
			}           
			current = current.children.get(c);      
		}      
		return true;   
	}
}

참고: delete 메서드

단어를 삭제하려면, 우선 해당 단어의 끝 지점(isEndOfWord)을 해제하고, 더 이상 필요 없는 노드를 정리할 수 있어야 합니다. 재귀 함수를 통해 자식 노드가 없는 경우에만 삭제하는 방식으로 구현할 수 있습니다.

java public boolean delete(String word) { return deleteHelper(root, word, 0); } private boolean deleteHelper(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord) { return false; // 이미 존재하지 않는 단어 } current.isEndOfWord = false; // 자식이 없으면 상위 노드에서 삭제할 수 있도록 true 반환 return current.children.isEmpty(); } char c = word.charAt(index); TrieNode node = current.children.get(c); if (node == null) { return false; // 삭제하려는 단어가 없으면 false } boolean shouldDeleteCurrentNode = deleteHelper(node, word, index + 1); if (shouldDeleteCurrentNode) { current.children.remove(c); return current.children.isEmpty() && !current.isEndOfWord; } return false; }