1) 삽입 문자열: apple
2) 삽입 문자열: april
3) 삽입 문자열: app
1) 삭제 문자열: apple
class Node{
HashMap<Character, Node> child;
booleand isTerminal; //문자열 끝을 구분하는 flag
}
// 비선형 자료구조 - 트라이 (Trie)
import java.util.HashMap;
class Node {
HashMap<Character, Node> child;
boolean isTerminal; //문자열의 끝인지 체크하는 flag
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);
//현재 노드 기준 c 문자에 해당하는 노드가 없으면 추가
cur.child.putIfAbsent(c, new Node());
//이어서 추가하기 위해 다음 문자 쪽으로 이동
//get(c)를 해야 노드가 나옴
cur = cur.child.get(c);
//str 끝이면 true 체크 후 return
if(i == str.length()-1){
cur.isTerminal = true;
return;
}
}
}
//원하는 문자열이 있는지 탐색하는 메소드
public boolean search(String str){
Node cur = this.root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
//해당 글자가 있으면 다음으로 이동, 없으면 false 반환
if(cur.child.containsKey(c)){
cur = cur.child.get(c);
}else{
return false;
}
//i가 str 끝에 도달했지만, cur와 terminal이 true 아니면
//해당 단어가 들어 있는 것은 아니므로 false 반환
if(i == str.length()-1){
if(!cur.isTerminal){
return false;
}
}
}
return true;
}
//재귀로 처리하기 위해
//delete 메소드를 2개로 나눔
public void delete(String str){
boolean ret = this.delete(this.root, str, 0);
if(ret){
System.out.println(str + "삭제 완료");
}else{
System.out.println(str + "단어가 없습니다");
}
}
public boolean delete(Node node, String str, int idx){
char c = str.charAt(idx);
//없는 글자일 경우 false 반환
if(!node.child.containsKey(c)){
return false;
}
//글자가 있을 경우 다음으로 이동
Node cur = node.child.get(c);
//인덱스도 다음으로 이동
idx++;
//단어의 가장 끝에 도달 후 삭제 결정
if(idx == str.length()){
//끝에 도달했지만, 문자열의 끝을 의미하는 isTermianl이 true가 아닐 경우
//해당 문자열과 일치하는 것이 아니므로 false 반환
if(!cur.isTerminal){
return false;
}
// 해당 문자열과 일치할 경우 isTerminal false로 변경 = 해당 문자열을 삭제하는 것
cur.isTerminal = false;
// 이후의 글자 없으면 삭제
if(cur.child.isEmpty()){
node.child.remove(c);
}
}
//단어의 끝에 도달하지 않았을 때
else{
//delete를 계속 진행하면서 false가 나오면 return false하여 종료
if(!this.delete(cur,str,idx)){
return false;
}
//끝 문자 삭제 후 재귀가 다시 반환되어 가면서, 다른 문자열의 끝 글자가 아니고, 이후에 글자가 없으면 삭제
if(!cur.isTerminal && cur.child.isEmpty()){
node.child.remove(c);
}
}
return true;
}
}
public class Main {
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");
}
}