package org.dataStructure;

// Trie는 기본적으로 빈 문자열을 가지는 루트노드만 가지고 있다.

// insert메서드를 통해 단어를 입력하면서 그에 맞게 자식 노드가 생성된다.

public class Trie {

// 루트 노드

private TrieNode rootNode;

Trie() {

rootNode = new TrieNode();

}

// 자식 노드 추가

void insert(String word) {

TrieNode thisNode = this.rootNode;

for (int i = 0; i < word.length(); ++i) {

thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());

}

// 계속해서 thisNode를 갱신하기 때문에 마지막 글자가 되므로 true.

thisNode.setIsLastChar(true);

}

// 특정 단어가 Trie에 존재하는지 확인

// 1. 루트노드 부터 순서대로 알파벡이 일치하는 자식노드들이 존재 할것

// 2. 해당 단어의 마지막 글자에 해당하는 노드의 isLastChar == true 일것

boolean contains(String word) {

TrieNode thisNode = this.rootNode;

for (int i = 0; i < word.length(); ++i) {

char character = word.charAt(i);

TrieNode node = thisNode.getChildNodes().get(character);

if (node == null)

return false;

thisNode = node;

}

return thisNode.isLastChar();

}

// 삭제

// 탐색 : 부모노드 -> 자식노드

// 삭제 : 자식노드 -> 부모노드

// 1. 자식 노드를 가지고 있지 않아야 합니다.

// 삭제시, 자식노드까지 지우면 안된다.

// 2. 삭제 시작 첫 노드는 isLastChar == true여야한다.

// false이면 존재하지 않는 단어이기 때문에 삭제 불가능.

// 3. 삭제 진행 중에는 isLastChar == false 여야한다.

// true이면 다른 단어가 존재하기 때문에 삭제하면 안된다.

void delete(String word) {

delete(this.rootNode, word, 0); // 최초로 delete 시작.

}

private void delete(TrieNode thisNode, String word, int index) {

char character = word.charAt(index);

// 단어가 아예존재 하지 않는경우 , ex) ABC , DEF

if (!thisNode.getChildNodes().containsKey(character))

throw new Error("There is no [" + word + "] in this Trie.");

// 글자가 존재하는 trieNode를 가져온다

TrieNode childNode = thisNode.getChildNodes().get(character);

index++;

// 탐색완료

if (index == word.length()) {

// 삭제 조건 2번 항목

if (!childNode.isLastChar())

throw new Error("There is no [" + word + "] in this Trie.");

childNode.setIsLastChar(false);

// 삭제 조건 1번 항목

if (childNode.getChildNodes().isEmpty())

thisNode.getChildNodes().remove(childNode);

} else {

// 콜백함수

delete(childNode, word, index);

// 콜백함수로 인해서 단어 탐색이 완료된 후에 이부분이 불린다.

// 삭제 조건 1, 3번 항목

// 자식노드가 없고, 현재 노드로 끝나는 단어가 없는 경우 이 노드 삭제

if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty())

thisNode.getChildNodes().remove(character);

}

}

boolean isRootEmpty() {

return this.rootNode.getChildNodes().isEmpty();

}

}