Today I Learned
TIL이 어느새 356번째다. 일요일은 WIL을 쓰니 1년이 넘어 총 356회차이다. 감회가 새롭다. 앞으로도 꾸준히 달리자!
참고 사이트 : codingnojam
Trie(트라이)
트리를 기반으로 하여 각 노드에 문자를 담아 문자열 탐색에 특화된 자료구조.
특징
-
검색이라는 의미의 'Retrieval'에서 따온 검색에 특화된 트리기반의 자료구조이다.
-
문자열의 집합을 저장하며, 주어진 문자열이 집합에 포함되어 있는지 빠르게 검색할 수 있다.
-
트리의 각 노드는 기본적으로 하나의 문자를 저장한다.(확장된 형태의 trie는 여러 문자열을 한 노드에 담아 압축하기도 한다.)
-
시간복잡도: 문자열의 길이가 M일때O(M)으로 해당 문자열을 찾을 수 있다.
삽입, 삭제에도 O(M)이 소요된다. -
공통 접두어를 가진 문자열은 메모리에 한번만 저장되어 효율적인 메모리 사용이 가능하다.
-
하지만
공간복잡도가 N:키의 수, M:최대길이 일 때,O(N*M)이라 저장할 문자열이 많으면 메모리를 많이 잡아먹을 수 있다. -
사전, 자동완성, IP라우팅 등에서 활용된다.
구현 과정
- 트라이 노드 구성
-
각 노드는 알파벳의 각 글자를 나타내며 알파벳 만큼의 자식 노드를 가질 수 있다.
-
노드는 문자열의 끝을 나타내는 플래그를 포함한다. 문자열의 마지막 글자가 저장될 때 이 플래그가 활성화 된다.
- 문자열 검색
-
검색하려는 문자열의 첫 글자부터 시작해 트라이를 탐색한다.
-
한 글자라도 없다면 해당 문자열은 트라이 내에 없다.
-
문자열의 마지막 글자 노드에서 플래그가 활성화 되어있다면 해당 문자열은 저장되어 있다.
- 문자열 삽입
-
루트노드는 아무 문자도 저장하지 않고 첫번째 자식 노드부터 첫 글자를 저장한다.
-
문자열의 첫 글자부터 시작해 각 글자에 해당하는 노드를 트라이 내에서 탐색한다.
-
만약 해당 글자에 해당하는 노드가 없으면 새 노드를 생성한다.
-
문자열의 끝이라면 플래그를 활성화 한다.
- 문자열 삭제
-
삭제하려는 문자열의 첫 글자부터 시작해 트라이를 탐색한다.
-
마지막 글자의 노드에서 문자열 끝 플래그를 비활성화 한다.
-
만약 해당 노드가 다른 문자열의 일부로 사용되지 않는다면 해당 노드를 삭제하고 이 과정을 부모노드로 올라가면서 반복한다.
-
탐색은 처음부터 하되, 삭제는 재귀로 거슬러 올라가면서 한다.
Java 코드 구현
import java.util.*;
public class J_Trie {
static class Node {
// 자식노드 담을 Map
Map<Character, Node> childNode = new HashMap<>();
// 끝을 판별하는 플래그 변수
boolean isEnd;
}
public static class Trie{
// 루트노드는 아무 문자도 담지않고 생성
Node rootNode;
Trie(){
rootNode = new Node();
}
// 삽입
void insert(String str){
// 항상 루트 노드부터 시작
Node node = this.rootNode;
// trie에 해당 문자열이 없으면 새로 노드를 만들어 파고내려간다.
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
node = node.childNode.computeIfAbsent(c,key -> new Node());
}
// 마지막 노드의 플래그를 활성화
node.isEnd = true;
}
// 검색
boolean contains(String str){
// 루트노드부터 시작
Node node = this.rootNode;
// getOrDefault로 해당 문자가 없으면 null을 넣어 false를 반환.
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
node = node.childNode.getOrDefault(c, null);
if(node == null) return false;
}
// 해당 문자열이 다 있고 마지막 노드의 플래그가 true여야 끝이기 때문에 플래그를 반환
return node.isEnd;
}
void delete(String str){
delete(this.rootNode, str, 0);
}
private void delete(Node node, String str, int index){
char c = str.charAt(index);
if(!node.childNode.containsKey(c)){
throw new RuntimeException("해당 글자열이 없어 삭제할 수 없습니다.");
}
Node child = node.childNode.get(c);
index++;
if(index == str.length()){
if(!child.isEnd) throw new RuntimeException("해당 글자열이 없어 삭제할 수 없습니다.");
child.isEnd = false;
if(child.childNode.isEmpty()){
node.childNode.remove(c);
}
} else {
delete(child, str, index);
if(!child.isEnd && child.childNode.isEmpty()){
node.childNode.remove(c);
}
}
}
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("baseball");
trie.insert("basketball");
trie.insert("bus");
trie.insert("tax");
System.out.println("baseball 포함 여부 :" + trie.contains("baseball"));
System.out.println("base 포함 여부 : " + trie.contains("base"));
System.out.println("taxi 포함 여부 : " + trie.contains("taxi"));
System.out.println("bus 포함 여부 : " + trie.contains("bus"));
System.out.println("bus 삭제");
trie.delete("bus");
System.out.println("bus 포함 여부 : " + trie.contains("bus"));
System.out.println("basketball 포함 여부 : " + trie.contains("basketball"));
}
}