그러나 각 노드마다 문자, 자식 노드 객체를 저장한다는 점에서 메모리가 많이 필요하다는 단점이 존재
구현
노드 클래스와 트리 클래스 2개를 갖는다.
노드 클래스
각 노드는 child라는 자식 노드의 맵을 가짐
Map<문자, Node 객체>
단어의 끝인지를 표시 하는 boolean 타입 변수 필요
트리 클래스
트라이의 자료구조를 구현한 클래스
insert 메서드 : 단어를 트라이에 삽입
search 메서드 : 단어가 트라이에 존재하는지 확인
static class Node{
// child맵은 자식 노드 정보를 담는 다.
// 문자를 key, 자식노드 객체 Node를 value로 갖는다.
Map<Character, Node> child = new TreeMap<>();
// 문자의 끝인지 나타내는 변수
boolean isEndOfWord = false;
}
static class Trie{
Node root;
Trie() {
this.root = new Node();
}
// 삽입 함수 : 문자열 삽입하기
public void insert(String word) {
// 시작 노드는 루트 노드
Node curNode = this.root;
char c;
for (int i = 0; i < word.length(); i++) {
c = word.charAt(i);
// 문자열의 단어가 자식 노드 중에 있는가?
// 없다면, 해당 문자 노드를 생성
curNode.child.putIfAbsent(c, new Node());
// 자식 노드로 이동
curNode = curNode.child.get(c);
}
// for문을 돌고 났을 때 가리키는 curNode는 문자열의 끝문자인지? -> isEndOfWord true로
curNode.isEndOfWord = true;
}
// 탐색 함수 : 원하는 문자열이 존재하는가?
public boolean search(String word) {
// 시작 노드는 루트 노드
Node curNode = this.root;
char c;
for (int i = 0; i < word.length(); i++) {
c = word.charAt(i);
if (curNode.child.containsKey(c)) {
// c문자가 현재노드의 자식노드에 있다면 -> 이동
curNode = curNode.child.get(c);
} else {
// 없다면 -> 탐색 종료
return false;
}
}
return curNode.isEndOfWord;
}
}
