[자바] 트라이(Trie) 개념과 삽입/검색/삭제 구현까지
트라이(Trie)
트라이 역시 트리형태의 자료구조라 보면 된다.
정렬된 트리 구조를 지니고 있으며, 시간복잡도는 O(N)이다.
대신, 사전에 문자열들을 트라이 형태로 구축을 해야한다.
트라이의 구조
문자열이 apple, april, ace, bear, best가 있으면 트라이는 위 사진처럼 구현된다.
문자열의 맨 앞자리부터 공통된 부분을 하나의 노드로 잡고 서로 다른 문자열을 자식노드만 나눠서 쭉 연결하는 구조이다.
그렇기 때문에 문자열의 갯수 M에 따른 시간복잡도 O(MN)을 가졌다고 볼 수 있다.
트라이 - 삽입
문자열의 맨 앞자리부터 비교하며 공통된 문자를 하나의 노드로 묶기때문에, 맨 앞 문자부터 삽입하면 된다.
단, 지금처럼 apple, april이 존재하는 상황에서 app 문자열이 삽입되면 apple과 겹친다.
이럴 경우에 p자리에 플래그를 세워준다.
트라이 - 삭제: CASE1
삭제는 삽입과 반대로 문자열의 끝부분부터 지우면 된다.
왜냐하면, 삽입은 공통된 문자를 하나의 노드로 묶기 위해서 맨 앞부터 삽입했지만,
삭제는 그림처럼 하나의 문자열을 삭제하다가 다른 문자열과 겹칠 수 있기 때문이다.
예를들어, apple에서 e와 l을 차례로 지우고 p를 지우려고 보니까 app이라는 또다른 문자열이 있을 수 있기 때문이다.
트라이 - 삭제: CASE 2
그렇다면 삭제 CASE 1과 반대로 apple문자열 중에서 app 문자열만 삭제하려면 어떡해야할까?
처음 app을 삽입할때 마지막 p자리에 플래그를 세워야 한다고 말했었다.
그렇다면 이 경우에는 간단하다.
p자리에 파란색 음영으로 표시해두었던 플래그만 없애주면 되는것이다.
트라이 - 구현방식
트라이는 Key와 Value 값으로 구성되어있다.
Key자리에는 문자열의 맨 앞 문자가 들어가고, Value에는 문자열의 두번째 자리 문자부터 들어간다.
Key와 Value. 생각나는게 있을것이다.
그렇다 HashMap을 이용해 구현할 수 있다.
그리고 매개변수로 Character를 Key값으로, Node를 Value값으로 잡아주면 된다. ( HashMap<Character, Node> )
처음에는 문자열의 맨 앞자리가 Character로 Key 자리에 들어갈것이다.
그런다음 두번째문자는? 두번째 문자는 세번째문자와 Character, Node쌍을 이루어 삽입될것이다.
세번째 문자부터도 동일하게 그 다음문자와 Character, Node쌍을 이루어 들어가면 된다.
이렇게 Character와 Node가 연쇄적으로 들어가는 것이다.
그러면서 각 문자열의 끝 문자마다 끝이라는 표시를 해주면 된다.
트라이 - 구현
1. 준비
class Node {
HashMap<Character, Node> child;
boolean isTerminal;
public Node(){
this.child = new HashMap<>();
this.isTerminal = false;
}
}
class Trie {
Node root; // 최상단 노드
public Trie() {
this.root = new Node();
}먼저 구현을 위한 준비단계이다.
Node 클래스를 만들어서 문자의 끝부분을 표시할 isTerminal 변수를 생성해준다.
그리고 자식노드끼리 꼬리에 꼬리를 물며 연결해줄 것이기에 HashMap도 만들어준다.
맨 처음 시작할 루트노드를 만들어주는 것도 잊지 않는다.
2. 삽입
public void insert(String str) { // 삽입
Node cur = this.root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i); // 삽입되는 문자열의 문자 하나하나씩 가져온다.
cur.child.putIfAbsent(c, new Node()); // 노드로 구성된 문자열이 꼬리에 꼬리를 무는 부분!
cur = cur.child.get(c);
if (i == str.length() - 1) { // 반복문 끝에 도달하면 true로 바꿔준다.
cur.isTerminal = true;
return;
}
}
}문자를 삽입하며 Trie를 구성하는 부분이다.
우선, cur.child.putIfAbsent(c, new Node()); 부분을 보자.
문자열 c가 Map에 key값으로 들어있으면 해당 value값을 반환하고,
들어있지 않다면 key값과 value값을 추가하고 Null을 반환해주는 부분이다.
하지만 여기서는 반환하는 값을 사용하지 않는다.
그렇다면 저 코드가 하는 역할은?
단순하다. Map에 key값이 없으면 역할대로 key값과 value값을 넣어주고,
이미 들어있다면 단순히 다음 코드로 넘어가도록 하는 역할이다.
그리고 key값과 value값이 들어간 이후에는 cur에 해당 value, 그러니깐 해당 자식노드인 new Node를 넣는다.
이 과정을 반복하면서 문자들이 꼬리에 꼬리를 물도록 연결하면 되는것이다.
apple과 april을 예로 들어보자.
처음에 a가 들어가고 a의 노드에 (p, new Node)가 들어갈것이다.
그리고 두번째 p가 들어가는 Node에도 현재 아무런 key와 value값이 없기 때문에 p와 Node가 쌍을이루어 들어간다.
여기까지 어떻게든 표현을 해보자면, (a, (p, (p, new Node))) 인 상태일 것이다.
이렇게 apple이 전부 들어갔다면 this,root.child의 모습은 (a, (p, (p, (l, (e, new Node)))) 처럼 생겼을 것이다.
그리고 마지막 반복문이 끝에 도달했을때, 해당 끝 노드의 isTerminal을 true로 만들어줌으로써 문자열의 끝이라는 것을 표시한다.
이후에 april이 들어오는 것도 상상해보자.
apple과 겹치는 a, p부분에서는 cur.child.putIfAbsent(c, new Node()); 코드에 걸려서 새로운 key와 value값을 추가하지 않고 넘어갈것이다.
그리고 'r' 문자가 들어올 때는 p의 자식노드로 들어올것이다.
이 때는 apple에서 만들었던 세번째 문자 (p, new Node)와 별개로 두번째 문자 p에서 (r, new Node)를 이루는 key, value쌍을 만들것이다. 그리고 해당 new Node가 cur에 할당되면서 'i'와 'l'이 해당 new Node에 꼬리를 물며 들어올것이다.
이것을 그림으로 보여주면 이렇게 생겼을 것이다.
사진에서는 문자열의 맨 끝 문자가 마킹되어있지만 cur = cur.child.get(c); 과 같이 cur를 정의했기 때문에
실제로는 끝 문자의 보이지않는 자식노드(new Node)에 표시가 되어있다고 봐도 된다.
하지만 구현 후 실행 결과에는 차이가 없기 때문에 사진처럼 이해하는게 편할것이다.
그럼 위 사진에서 문자열 app을 추가한다면?
apple, april이 들어왔던 과정과 동일하다.
apple 문자 안에 app의 모든 문자가 들어있기 때문에 별도의 값은 추가하지 않을것이다.
대신 아래 구현한 코드에 의해 해당 노드에서 isTerminal을 true로 세팅하여 문자의 끝부분이라는 게 표시될 것이다.
if (i == str.length() - 1) { // 반복문 끝에 도달하면 true로 바꿔준다.
cur.isTerminal = true;
return;
}
3. 검색
public boolean search(String str) { // 특정 str 문자열이 트라이에 있는지 체크하는 메서드
Node cur = this.root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (cur.child.containsKey(c)) {
cur = cur.child.get(c); // 현재 cur의 key가 해당 문자를 갖고있으면 자식노드로 이동한다.
} else {
return false;
}
if (i == str.length() - 1) {
if (!cur.isTerminal) {
return false;
}
}
}
return true;이번에는 트라이에 특정 문자열이 포함되어있는지 확인하는 부분이다.
삽입과정을 충분히 이해했다면 이부분은 크게 어렵지 않다.
삽입과 동일하게 문자를 하나씩 뽑아오면 된다.
이후 cur의 key값 중 해당 문자가 있는지 확인하고, 있으면 key의 자식노드로, 없다면 false 리턴이다.
단, 문자열의 끝까지 체크하고 containsKey가 true로 확인되었다해서 true로 최종 리턴하면 안된다.
반드시 문자열의 끝에 도달했을때 위에서 표시했던 isTerminal이 false인지 true인지 체크해야 된다.
만약 apple을 넣은후 app 문자의 유무를 체크했는데 false가 나온다면 app은 없다는 뜻이기 때문이다.
4. 삭제
마지막 삭제 부분이다.
public void delete(String str) {
boolean check = this.delete(this.root, str, 0);
if (check) {
System.out.println(str + " 삭제 완료");
} else {
System.out.println(str + " 단어가 없습니다.");
}
}
public boolean delete(Node node, String str, int idx) {
char c = str.charAt(idx); // 재귀를 호출하면서 문자의 자릿수가 되는 idx를 늘려간다.
if (!node.child.containsKey(c)) {
return false; // 노드를 따라가다 노드의 순서가 문자의 순서와 맞지 않으면 바로 false 리턴
}
Node cur = node.child.get(c); // 삽입떄와 마찬가지로 꼬리에 꼬리를 물며 내려간다.
idx++;
if (idx == str.length()) { // idx를 증가시키고 비교하기 때문에 length - 1이 아니라 length와 비교한다.
if (!cur.isTerminal) { // 끝까지 다다랐을때 문자에 마킹이 안되어있다면 false 리턴
return false;
}
cur.isTerminal = false; // 만약 마킹이 되어있다면 삭제할 것이기 때문에 마킹을 false로 바꿔준다.
if (cur.child.isEmpty()) { // 마킹을 없앤 노드로 부터 파생되는 자식노드가 없다면
node.child.remove(c); // 해당 노드가 끝 노드이므로 바로 지워준다.
} // --> 마킹을 없앤 노드가 끝 노드가 아닌 경우는 별도의 노드 삭제 없이 true를 반환한다.
} else { //
if (!this.delete(cur, str, idx)) { // 해당 문자열의 끝에 도달할 때 까지 계속 재귀호출한다.
return false;
}
if (!cur.isTerminal && cur.child.isEmpty()) {
node.child.remove(c); // 재귀호출을 끝낸 노드가 마킹이 안돼있고 자식노드가 비어있다면
} // 현재 끝 노드인 해당노드를 삭제하고 다시 리턴해 한칸씩 앞으로 가면서 이 부분을 반복한다.
}
return true;
}재귀호출을 반복하면서 조건문에 맞게 true 혹은 false를 반환하면 된다.
이해가 잘 될지는 모르겠지만 최대한 이해하기 쉽도록 노력하며 작성해보았다.
그래도 글로 다시한번 간단히 설명해보자면...
삭제할 문제가 apple이라고 했을 경우,
1. 재귀호출로 apple 문자열 끝까지 체크하며 a-p-p-l-e 순서로 이루어진 노드가 없다면 바로 false를 반환한다. -> false
2. apple 문자열의 끝까지 도달했을 때 isTerminal로 마킹한 부분이 false라면 바로 false를 반환한다. -> false
3. apple 문자열 끝까지 도달했고, isTerminal도 true라면 해당 노드의 isTerminal을 false로 바꿔준다.
- 재귀호출도 끝까지 돌았고 그 안에서 1번과 2번을 무사히 넘겼다면 마지막 과정만 남았다.
4. 재귀호출을 끝낸 뒤 return하면 한칸 앞 노드로 이동해있을것이다.
5. 해당 노드의 isTerminal이 false이고, 자식노드가 비어있다면 해당 노드가 마지막 노드일 것이다. 이 경우, 해당 노드를 삭제한다.
6. 만약 5번에 해당하지 않는다면 apple 안에 들어있는 app처럼 다른 문자열에 포함된 문자일 것이다. 우리는 3번에서 isTerminal을 이미 true에서 false로 바꿨기 때문에, 별도로 삭제할 필요 없이 모든 재귀호출을 true로 리턴하면 된다.
여기까지 Trie의 개념과 삽입, 검색, 삭제를 구현해보았다.
최대한 쉽게 설명하려 노력했지만, 그럼에도 코드가 길고 재귀함수가 들어가는 등 복잡해서 이해하기 어렵다면,
천천히 그려보며 깊게 생각해보는 것이 중요할 것 같다.
마지막으로, 전체 코드와 함께 출력결과를 보여주겠다.
import java.util.HashMap;
class Node {
HashMap<Character, Node> child;
boolean isTerminal;
public Node(){
this.child = new HashMap<>();
this.isTerminal = false;
}
}
class Trie {
Node root; // 최상단 노드
public Trie() {
this.root = new Node();
}
public void insert(String str) { // 삽입
Node cur = this.root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i); // 삽입되는 문자열의 문자 하나하나씩 가져온다.
cur.child.putIfAbsent(c, new Node()); // 노드로 구성된 문자열이 꼬리에 꼬리를 무는 부분!
cur = cur.child.get(c);
if (i == str.length() - 1) { // 반복문 끝에 도달하면 true로 바꿔준다.
cur.isTerminal = true;
return;
}
}
}
public boolean search(String str) { // 특정 str 문자열이 트라이에 있는지 체크하는 메서드
Node cur = this.root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (cur.child.containsKey(c)) {
cur = cur.child.get(c); // 현재 cur의 key가 해당 문자를 갖고있으면 자식노드로 이동한다.
} else {
return false;
}
if (i == str.length() - 1) {
if (!cur.isTerminal) {
return false;
}
}
}
return true;
}
public void delete(String str) {
boolean check = this.delete(this.root, str, 0);
if (check) {
System.out.println(str + " 삭제 완료");
} else {
System.out.println(str + " 단어가 없습니다.");
}
}
public boolean delete(Node node, String str, int idx) {
char c = str.charAt(idx); // 재귀를 호출하면서 문자의 자릿수가 되는 idx를 늘려간다.
if (!node.child.containsKey(c)) {
return false; // 노드를 따라가다 노드의 순서가 문자의 순서와 맞지 않으면 바로 false 리턴
}
Node cur = node.child.get(c); // 삽입떄와 마찬가지로 꼬리에 꼬리를 물며 내려간다.
idx++;
if (idx == str.length()) { // idx를 증가시키고 비교하기 때문에 length - 1이 아니라 length와 비교한다.
if (!cur.isTerminal) { // 끝까지 다다랐을때 문자에 마킹이 안되어있다면 false 리턴
return false;
}
cur.isTerminal = false; // 만약 마킹이 되어있다면 삭제할 것이기 때문에 마킹을 false로 바꿔준다.
if (cur.child.isEmpty()) { // 마킹을 없앤 노드로 부터 파생되는 자식노드가 없다면
node.child.remove(c); // 해당 노드가 끝 노드이므로 바로 지워준다.
} // --> 마킹을 없앤 노드가 끝 노드가 아닌 경우는 별도의 노드 삭제 없이 true를 반환한다.
} else { //
if (!this.delete(cur, str, idx)) { // 해당 문자열의 끝에 도달할 때 까지 계속 재귀호출한다.
return false;
}
if (!cur.isTerminal && cur.child.isEmpty()) {
node.child.remove(c); // 재귀호출을 끝낸 노드가 마킹이 안돼있고 자식노드가 비어있다면
} // 현재 끝 노드인 해당노드를 삭제하고 다시 리턴해 한칸씩 앞으로 가면서 이 부분을 반복한다.
}
return true;
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
Trie trie = new Trie();
trie.insert("apple");
trie.insert("april");
trie.insert("app");
trie.insert("ace");
trie.insert("bear");
trie.insert("best");
System.out.println(trie.search("apple")); // true
System.out.println(trie.search("april")); // true
System.out.println(trie.search("app")); // true
System.out.println(trie.search("ace")); // true
System.out.println(trie.search("bear")); // true
System.out.println(trie.search("best")); // true
System.out.println(trie.search("abc")); // false
System.out.println();
trie.delete("apple");
System.out.println(trie.search("apple")); // false
System.out.println(trie.search("april")); // true
System.out.println(trie.search("appl")); // false
trie.delete("apple");
}
}출력
true
true
true
true
true
true
false
apple 삭제 완료
false
true
false
apple 단어가 없습니다.