문자열을 효율적으로 저장하고 검색하는 데 사용되는 트리 기반의 자료구조
사전과 같은 단어 검색, 자동 완성, 접두사 매칭 등에 유용하다.
Pros
- 불완전한 해시 함수를 사용하는 해시테이블과 비교할 때, 자료에 접근할 때 최악의 경우 더 유리한 시간복잡도를 갖는다. m이 탐색할 문자열의 길이일 때 시간복잡도는 O(m)이다. 보통 해시테이블은 탐색 시간이 O(1)이고 해시 함수 평가 시간이 O(m)이지만, 불완전한 해시 테이블은 키 충돌이 일어날 수 있으므로, O(N)이 될 수 있다.
- 트라이에서는 키 충돌이 일어나지 않는다.
- 여러 값이 하나의 키와 연관되어 있지 않는 한 버킷이 필요 없다.
- 해시 함수가 없어도 된다. 키가 늘어날 때 해시 함수를 변경할 필요도 없다.
- 모든 항목이 키에 따라 사전순으로 정렬되어 있다.
Cons
- 조회는 해시 테이블보다 느릴 수 있다. 특히 주 메모리에 비해 임의 접근 비용이 큰 하드 디스크 드라이브와 같은 보조 기억장치에서 직접 읽는다면 더욱 그렇다
- 부동소수점과 같이 문자열로 장황하게 표시되는 자료의 경우 무의미하게 길게 늘어진 접두사와 노드를 가질 수 있다.
- 표준 IEEE 부동소수점 수는 비트 트라이로 처리할 수는 있다.
- 트라이가 메모리를 더 소비할 수 있다. 대부분의 해시 테이블에서는 전체 항목을 하나의 메모리 청크에 올리곤 하지만, 트라이에서는 검색 문자열의 각 문자마다 메모리가 할당될 수 있다.
Insert

- 루트 노드에서 시작해 문자열의 각 문자를 트리의 깊이를 따라가며 노드를 추가한다.
- 문자열의 각 문자에 대해 자식 노드가 없으면 새로운 노드를 추가하고, 있으면 기존 노드를 따라간다.
- 문자열의 끝에 도달하면 해당 노드에 endOfWord를 true로 표시한다
Search

- 루트 노드에서 시작해 문자를 따라가다 모든 문자가 트리에서 일치하면 마지막 노드가 endOfWord 를 가지고 있는지 확인한다.
- endOfWord를 가지고 있지 않다면 존재하지 않는 문자열이다
Delete

- 먼저 문자열이 존재하는지 확인한다.
- 존재한다면 마지막 노드인 endOfWord를 false로 변경한다. 마지막 노드의 자식이 있다면 나머지 노드들을 삭제하지 않고 없다면 다른 자식 노드가 없을 때까지 상위 노드로 이동하며 노드를 삭제한다.
Code
public class Trie {
private class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isEndOfWord;
public TrieNode() {
this.isEndOfWord = false;
}
}
private final TrieNode root;
public Trie() {
root = new TrieNode();
}
// insert
public void insert(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
current = current.children.computeIfAbsent(ch, c -> new TrieNode());
}
current.isEndOfWord = true;
}
// search
public boolean search(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
current = current.children.get(ch);
if (current == null) {
return false;
}
}
return current.isEndOfWord;
}
// delete
public void delete(String word) {
delete(root, word, 0);
}
private boolean delete(TrieNode current, String word, int index) {
if (index == word.length()) {
if (!current.isEndOfWord) {
return false;
}
current.isEndOfWord = false;
return current.children.isEmpty();
}
char ch = word.charAt(index);
TrieNode node = current.children.get(ch);
if (node == null) {
return false;
}
boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
if (shouldDeleteCurrentNode) {
current.children.remove(ch);
return current.children.isEmpty() && !current.isEndOfWord;
}
return false;
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("hello");
trie.insert("helium");
System.out.println(trie.search("hello")); // true
System.out.println(trie.search("helix")); // false
trie.delete("hello");
System.out.println(trie.search("hello")); // false
System.out.println(trie.search("helium")); // true
}
}