[java] 자바의 트라이(Trie) 자료구조 이해하기
트라이(Trie)는 트리 자료구조의 변형인데 문자열을 저장하고 검색하는 데 사용됩니다. 이 포스트에서는 자바에서의 트라이 자료구조를 소개하고, 실제로 어떻게 사용하는지에 대해 알아보겠습니다.
트라이(Trie)란 무엇인가요?
트라이(Trie) 는 검색을 위한 정렬된 트리의 일종으로, 문자열 키들을 저장하고 검색하는 데 사용됩니다. 각 노드는 키의 한 글자를 나타내며, 루트(root) 노드부터 시작해서 자식 노드로 내려감으로써 특정 문자열을 찾을 수 있게 됩니다.
자바에서의 트라이 자료구조
자바에서 트라이 자료구조를 구현하는 방법에는 여러 가지가 있습니다. 주로 맵(Map) 자료구조를 사용해서 노드를 구현하는 방법과 배열을 사용해서 구현하는 방법이 있습니다.
예시 코드
아래는 자바에서의 간단한 트라이 자료구조 예시 코드입니다.
class TrieNode {
Map<Character, TrieNode> children;
boolean isEndOfWord;
public TrieNode() {
children = new HashMap<>();
isEndOfWord = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
node = new TrieNode();
current.children.put(ch, node);
}
current = node;
}
current.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
return false;
}
current = node;
}
return current.isEndOfWord;
}
}
마치며
트라이(Trie)는 문자열을 저장하고 검색하는 데 유용한 자료구조입니다. 이를 이해하고 자바에서 구현하는 방법을 배웠습니다. 트라이는 자연어 처리, 검색 엔진, 오토컴플릿 등의 기능을 구현할 때 유용하게 활용될 수 있습니다.