Trie
트라이(Trie)란?
트라이는 효율적인 문자열 저장 및 탐색이 가능한 자료구조의 형태이다.
내가 저장한 구조에 포함된 문자열인지 알 수 있는 방법은 다음과 같다.
단순비교
- 전체 문자열의 맨 처음부터 끝까지 문자 하나하나를 비교하는 방식
- 최대 문자열 길이 m, 전체 문자 개수 n개 시간 복잡도: 최악의 경우 O(nm)
이진 탐색 기법
- 전체 문자열을 사전순으로 배열 저장 후, 중간 값과 비교해 사전적으로 이전이면 좌측의 반을 비교하는 방식
- 최대 문자열 길이 m, 전체 문자 개수 n개 시간 복잡도: 정렬 O(n mlogn) / 탐색 O(mlogn) → O(nmlogn)
트라이(Trie)
- k-진 트리 구조를 통해 문자열 저장하는 방식
- 영어 사전 방식, - game 이면 사전에 g를 찾고, 순서대로 a, m, e를 찾는 방식을 트리 형식으로 구현한 것
- 맨 앞의 접두어부터 시작하여 단어 전체를 찾아가는 과정으로 접두사 트리라고도 한다.
- 트라이는 문자열 저장을 위해 공간을 많이 쓰지만 탐색에 매우 효율적이라는 특성을 갖고 있다.
- 최대 문자열 길이 m일 때 문자의 개수와 무관하게 시간 복잡도 O(m)
- 각 문자 하나를 배열의 위치로 지정하여 문자열 하나 찾을 때 O(1) 이므로 길이 만큼의 시간만 소요
- 만약 문자열 길이가 너무 길어 Map을 이용해 동적 할당을 해야 하는 경우 O(m logn) 만큼 소요될 수 있다.
Trie 구현
트라이 구조의 각 노드에는 각 문자열의 일부를 포함하며 자신과 연결되는 문자열의 일부를 가지고 있어야 한다.
(1) 생성자, 클래스 정의
public class Trie {
Node root;
static final int ALPHABET_SIZE = 26; // a-z는 26개
public Trie(){
this.root = new Node();
this.root.val = ' ';
}
private static class Node{
Node[] child = new Node[ALPHABET_SIZE]; // 뒤로 연결되는 문자열 a-z 소문자를 index화하여 저장하는 배열(26개)
boolean isTerminal = false; // 현재 노드가 문자 완성이 되는 노드인지 여부
int childNum = 0; // 현재 노드에 연결된 문자열의 개수
char val; // 현재 노드의 값
}
}
(2) 문자열 삽입하기
private int charToInt(char c){
return c - 'a'; // 여기서는 소문자만 있으므로 'a'를 빼면 된다.
}
public void insert(String str){
int length = str.length();
Node current = this.root; // 루트 부터 시작해서 내려감
for(int i=0; i < length; ++i) {
char c = str.charAt(i); // 전체 문자열의 일부 단어 추출
int num = this.charToInt(c); // 추출한 단어를 숫자로 변환
if(current.child[num] == null){ // 기존에 null이면 연결 문자열로 처음 추가되는 것
current.child[num] = new Node();
current.child[num].val = c;
current.childNum++;
}
current = current.child[num]; // 자식 노드로 넘어감
}
current.isTerminal = true;
}
(3) find
// 반복문으로 노드를 순환하여 문자열 존재 여부 판단
public boolean find(String str){
int length = str.length();
Node current = this.root; // 현재 노드 설정
for(int i = 0; i < length; ++i){
char c = str.charAt(i);
int num = this.charToInt(c);
if(current.child[num] == null){ // 문자열의 일부를 추출했는데 null 이라면 false 반환
return false;
}
current = current.child[num];
}
return current != null && current.isTerminal; // 문자열의 마지막이라면 true
}
(4) print
private char intToChar(int i){
return (char)(i + (int)'a');
}
public void printTrie(){ // 사용자가 간편히 호출만 하면 되는 메소드
this.printTrie(this.root, 0, new StringBuilder());
}
// 내부에서 재귀적으로 순환하여 노드에 저장된 값들 추출해 프린트
private void printTrie(Node node, int idx, StringBuilder sb){
Node current = node;
Node[] child = current.child;
StringBuilder builder = new StringBuilder(sb);
// 루트 노드에는 저장된 것이 없으므로 그 외의 경우에만 append
if(!current.equals(this.root)){
builder.append(intToChar(idx));
}
// 완성 노드라면 프린팅하면 된다.
if(current.isTerminal){
System.out.println(builder);
}
// 연결된 노드들을 순환하기 위해 반복문 사용
for(int i = 0; i < ALPHABET_SIZE; ++i){
// null 이라면 거기에는 저장된 것이 없다는 의미이므로 건너 뜀
if(current.child[i] == null){
continue;
}
printTrie(child[i], i, builder); // 재귀적으로 순환
}
}
(5) 삭제
삭제는 재귀 bottom-up 방식으로 진행된다.
- 삭제할 문자가 다른 문자의 접두사인 경우
-isTerminal을false로 변경 - 삭제할 문자가 유니크하여 다른 문자와 연관이 없는 경우, 관련 모든 노드 삭제
- 삭제할 문자의 일부가 전체 삭제 문자의 접두사인 경우, 다른 문자에 영향가지 않는 곳까지만 삭제
// 사용자가 호출 시 사용하는 메소드
public void delete(String str){
delete(this.root, str, 0);
}
// 내부적으로 재귀를 통해 삭제를 진행하는 메소드
private void delete(Node current, String str, int idx){
int leng = str.length();
// 자식이 없는데 string의 length의 끝까지 오지 않았다면 예외 발생
// 끝까지 갔는데 해당 노드가 terminal가 아니었다면 해당 단어를 저장하지 않은 것이므로 예외 발생
if((current.childNum == 0 && idx != leng) || (idx == leng && !current.isTerminal)) {
throw new NoSuchElementException("Value " + str + " does not exist in Trie!");
}
// 문자열의 마지막에 다다른 경우
if(idx == leng){
current.isTerminal = false;
// 자식이 없는데 문자의 마지막이었다면 해당 문자만 저장된 것이므로 null 처리
if(current.childNum == 0){
current = null;
} else {
char c = str.charAt(idx);
int num = charToInt(c);
// 삭제 후 돌아오는 부분
delete(current.child[num], str,idx+1);
// child가 null처리 되었다면 자식 노드의 수가 하나 줄어든 것이므로 -- 처리
if(current.child[num] == null) current.childNum--;
// 현재 노드의 자식이 없고, 단어의 마지막도 아니라면 삭제해야 한다.
if(current.childNum == 0 && !current.isTerminal){
current = null;
}
}
}