트라이(trie)
컴퓨터 과학에서 탐색 트리의 일종.
동적 집합이나 연관 배열을 저장하는데 사용되는 트리 자료 구조.
주로 문자열이 키인 경우가 많다.
이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다.
대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다.
즉, 키의 값은 자료 구조 전체에 분산된다.
노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다.
루트는 빈 문자열에 연관된다.
일부 내부 노드가 키에 대응할 수도 있지만, 일반적으로 키는 단말에 연관되는 경향이 있다.
따라서 모든 노드가 꼭 키와 연결되지는 않는다.
메모리에 최적화 된 경우는 기수 트리가 된다.
예시에서 키는 노드에, 값은 그 아래에 있다.
완전한 단어 키마다 연관된 임의의 정수가 있는 식이다.
트라이는 트리 모양인 결정적 유한 오토마타로 볼 수도 있다.
트라이 오토마타로 생성한 각 유한 언어는 결정적 비순환 유한 상태 오토마타로 압축할 수 있다.
트라이는 문자열이 키인 경우가 흔하지만, 꼭 그래야 하는 것은 아니다.
어떻게 구성된 정렬된 리스트라도 비슷한 기능을 제공할 수 있는 동등한 알고리즘을 적용할 수만 있다면 상관 없다.
이를테면 숫자나 도형의 리스트로 구성한 순열 같은 것이 가능하다.
정수나 메모리 주소 같은 고정 길이 이진 자료를 표현하는 각각의 비트로 구성된 트라이를 특별히 비트 트라이라고 부른다.
장점
해시테이블을 대체하여 사용 가능하며 이진 검색 트리에 비해 몇 가지 장점이 있다.
- 불완전한 해시 함수를 사용하는 해시테이블과 비교할 때, 자료에 접근할 때 최악의 경우 더 유리한 시간복잡도를 갖는다. m이 탐색할 문자열의 길이일 때 시간복잡도는 O(m)이다. 보통 해시테이블은 탐색 시간이 O(1)이고 해시 함수 평가 시간이 O(m)이지만, 불환전한 해시 테이블은 키 충돌이 일어날 수 있으므로, O(N)이 될 수 있다.
- 트라이에서는 키 충돌이 일어나지 않는다.
- 여러 값이 하나의 키와 연관되어 있지 않는 한 버킷이 필요 없다.
- 해시 함수가 없어도 된다. 키가 늘어날 때 해시 함수를 변경할 필요도 없다.
- 모든 항목이 키에 따라 사전순으로 정렬되어 있다.
단점
- 조회는 해시테이블보다 느릴 수 있다. 특히 주 메모리에 비해 임의 접근 비용이 큰 하드 디스크 드라이브와 같은 보조 기억장치에서 직접 읽는다면 더욱 그렇다.
- 부동소수점과 같이 문자열로 장황하게 표시되는 자료의 경우 무의미하게 길게 늘어진 접두사와 노드를 가질 수 있다.(한편 표준 IEEE 부동소수점 수는 비트 트라이로 처리할 수는 있다.)
- 트라이가 메모리를 더 소비할 수 있다. 대부분의 해시테이블에서는 전체 항목을 하나의 메모리 청크에 올리곤 하지만, 트라이에서는 검색 문자열의 각 문자마다 메모리가 할당될 수 있다.
응용
- 휴대 전화에서 예측 문자나 자동 완성에 필요한 사전을 저장하는 것
-> 트라이에서 빠르게 조회, 삽입, 삭제할 수 있는 기능을 활용 - 맞춤법 검사
=> 문자열을 저장하고 탐색하는데 유용한 자료구조.
알고리즘
트라이는 탐색과 삽입을 지원하는 노드로 구성된 트리.
탐색 - 키 문자열과 연관된 값을 반환
삽입 - 문자열(키)과 그 값을 삽입
키의 길이가 m일 때 탐색과 삽입 모두 O(m) 시간에 수행된다.
코드
package algorithm;
import java.util.HashMap;
import java.util.Map;
public class SelfTrie {
class NodeTrie {
Map<Character, NodeTrie> childNodes = new HashMap<>();
boolean isLastChar;
Map<Character, NodeTrie> getChildNodes() {
return this.childNodes;
}
boolean isLastChar() {
return this.isLastChar;
}
void setIsLastChar(boolean isLastChar) {
this.isLastChar = isLastChar;
}
}
NodeTrie rootNode;
SelfTrie() {
rootNode = new NodeTrie();
}
void insert(String word) {
NodeTrie curNode = this.rootNode;
for (int i = 0; i < word.length(); i++) {
curNode = curNode.getChildNodes().computeIfAbsent(word.charAt(i),
c -> new NodeTrie());
}
curNode.setIsLastChar(true);
}
boolean contains(String word) {
NodeTrie curNode = this.rootNode;
for (int i = 0; i < word.length(); i++) {
char character = word.charAt(i);
NodeTrie node = curNode.getChildNodes().get(character);
if (node == null)
return false;
curNode = node;
}
return curNode.isLastChar();
}
void delete(String word) {
delete(this.rootNode, word, 0);
}
void delete(NodeTrie curNode, String word, int index) {
char character = word.charAt(index);
if (!curNode.getChildNodes().containsKey(character))
throw new Error("There is no [" + word + "] in this Trie.");
NodeTrie childNode = curNode.getChildNodes().get(character);
index++;
if (index == word.length()) {
if (!childNode.isLastChar())
throw new Error("There is no [" + word + "] in this Trie.");
childNode.setIsLastChar(false);
if (childNode.getChildNodes().isEmpty())
curNode.getChildNodes().remove(character);
} else {
delete(childNode, word, index);
if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
curNode.getChildNodes().remove(character);
}
}
boolean isRootEmpty() {
return this.rootNode.getChildNodes().isEmpty();
}
public static void main(String[] args) {
SelfTrie trie = new SelfTrie();
System.out.println("isRootEmpty: " + trie.isRootEmpty());
trie.insert("PI");
trie.insert("PIE");
trie.insert("POW");
trie.insert("POP");
System.out.println("isRootEmpty: " + trie.isRootEmpty());
System.out.println("does contain POW: " + trie.contains("POW"));
System.out.println("does contain PIES: " + trie.contains("PIES"));
trie.delete("POP");
System.out.println("does contain POP: " + trie.contains("POP"));
System.out.println("does contain POW: " + trie.contains("POW"));
}
}
출처
