트라이
문자열을 저장하고 효율적으로 탐색하기 위해 사용하는 트리 형태의 자료구조입니다.
핵심 특징
루트는 항상 비어있으며, 각 간선은 추가될 문자를 키로 가집니다. 각 정점은 이전 정점의 값과 간선의 키를 더한 결과를 값으로 가지며, 이러한 구조 덕분에 문자열을 한 글자씩 비교하는 방식보다 효율적으로 탐색할 수 있습니다.
다만 각 정점이 자식에 대한 링크를 모두 가지고 있어야 하기 때문에 저장 공간을 더 많이 사용한다는 단점이 있습니다.
동작 원리
트라이는 해시 테이블과 연결 리스트 형태의 정점 연결을 함께 사용해 구현할 수 있습니다. 문자열을 삽입할 때는 루트부터 시작해 한 글자씩 자식 정점을 찾아가거나 없으면 새로 생성하고, 탐색할 때는 동일하게 한 글자씩 자식 정점을 따라가며 존재 여부를 확인합니다.
class Trie {
private final Node root = new Node("");
public void insert(String str) {
Node current = root;
for (String ch : str.split("")) {
if (!current.children.containsKey(ch)) {
current.children.put(ch, new Node(current.value + ch));
}
current = current.children.get(ch);
}
}
public boolean has(String str) {
Node current = root;
for (String ch : str.split("")) {
if (!current.children.containsKey(ch)) {
return false;
}
current = current.children.get(ch);
}
return true;
}
}
class Node {
public String value;
public Map<String, Node> children;
public Node(String value) {
this.value = value;
this.children = new HashMap<>();
}
}
사용 예
문자열의 접두사를 기준으로 빠르게 탐색해야 하는 검색어 자동완성이나 사전 찾기 기능을 구현할 때 주로 고려되는 자료구조입니다.
핵심 정리
트라이는 문자열의 각 글자를 간선으로, 접두사를 정점으로 표현해 탐색 성능을 높이는 대신 저장 공간을 더 사용하는 트레이드오프를 가진 자료구조입니다.