트라이(Trie)
문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료 구조
정렬된 트리 구조로, 문장 저장을 위한 메모리가 필요하지만 탐색이 빠르다
-> 길이가 N인 문자열 탐색의 시간 복잡도 : O(N)
예를들어 문자열 구성 : apple, april, ace, bear, best로 되어있다 가정
단어의 끝이라는 것을 나타내기 위한 하나의 flag가 필요!
삭제
기존의 apple,app, april이 존재 한다고 가정
apple 삭제할려고 할때, e까지 간다음에 flag를 해제하고, 아래에 다른 자식 노드가 없으면 지우는 식으로 e -> l 제거
구현
Key,Value로 이루어진 노드 구성
-> 여기서 Key는 알파벳, Value는 자식 노드
자식 노드 ex) 처음 a 다음에 오는 자식 -> p와 c
class Node{
HashMap<Character, Node> child;
boolean isTerminal;
}class Node{
HashMap<Character, Node> child;
boolean isTerminal;
public Node(){
this.child = new HashMap<>();
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){
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);
if(cur.child.containsKey(c)){
cur = cur.child.get(c);
}else{
return false;
}
if(i == str.length() - 1){
if(!cur.isTerminal){
return false;
}
}
}
return true;
}
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);
if(!node.child.containsKey(c)){
return false;
}
Node cur = node.child.get(c);
idx++;
if(idx == str.length()){
if(!cur.isTerminal){
return false;
}
cur.isTerminal = false;
if(cur.child.isEmpty()){
node.child.remove(c);
}
}else{
// 지워야 하는 문자 찾기 전
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) {
Trie trie = new Trie();
trie.insert("apple");
trie.insert("april");
trie.insert("app"); // 이부분 주석처리하면 밑에서 false;
trie.insert("ace");
trie.insert("bear");
trie.insert("best");
System.out.println(trie.search("apple"));
System.out.println(trie.search("april"));
System.out.println(trie.search("app"));
System.out.println(trie.search("ace"));
System.out.println(trie.search("bear"));
System.out.println(trie.search("best"));
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"));
System.out.println(trie.search("appl")); // false
trie.delete("apple");
}
}연습문제
문제1
// Practice1
// 문자열 배열 strs 와 문자열 prefix 가 주어졌을 때
// 문자열 배열 내에 prefix 로 시작하는 단어가 있는지를 확인하는 프로그램을 작성하세요.
// prefix 로 시작하는 단어가 있으면 true, 없으면 false 를 반환하세요.
// 입출력 예시
// 입력 strs: "apple", "april", "app", "ace", "bear", "best"
// 입력 prefix: "app"
// 출력: true
// 입력 strs: "apple", "april", "app", "ace", "bear", "best"
// 입력 prefix: "pre"
// 출력: false
public class Practice1 {
public static boolean solution(String[] strs, String prefix) {
Trie trie = new Trie();
for(String s : strs){
trie.insert(s);
}
Node cur = trie.root;
for(int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if(cur.child.get(c) == null){
return false;
}
cur = cur.child.get(c);
}
return true;
}
public static void main(String[] args) {
// Test code
String[] strs = {"apple", "april", "app", "ace", "bear", "best"};
String prefix = "app";
System.out.println(solution(strs, prefix)); // true
prefix = "be";
System.out.println(solution(strs, prefix)); // true
prefix = "pre";
System.out.println(solution(strs, prefix)); // false
}
}문제 2
// Practice2
// 문자열 배열 dictionary 와 문자열 sentence 가 주어졌을 때
// sentence 내의 단어 중 dictionary 의 단어로 시작하는 경우
// 해당 단어로 변경하여 출력하는 프로그램을 작성하세요.
// 입출력 예시
// 입력 dictionary: "cat", "bat", "rat"
// 입력 sentence = "the cattle was rattled by the battery"
// 출력: "the cat was rat by the bat"
// 입력 dictionary: "a", "b", "c"
// 입력 sentence = "apple banana carrot water"
// 출력: "a b c water"
public class Practice2 {
public static void solution(String[] dictionary, String sentence) {
Trie trie = new Trie();
for(String str : dictionary){
trie.insert(str);
}
StringBuffer sbResult = new StringBuffer();
for(String word : sentence.split(" ")) {
Node cur = trie.root;
StringBuffer sbCur = new StringBuffer();
for (char c : word.toCharArray()) {
sbCur.append(c);
if (cur.child.get(c) != null) {
if (cur.child.get(c).isTerminal) {
break;
}
cur = cur.child.get(c);
} else {
sbCur = new StringBuffer(word);
break;
}
}
sbResult.append(sbCur);
sbResult.append(" ");
}
System.out.println(sbResult);
}
public static void main(String[] args) {
// Test code
String[] dictionary = {"cat", "bat", "rat"};
String sentence = "the cattle was rattled by the battery";
solution(dictionary, sentence);
dictionary = new String[]{"a", "b", "c"};
sentence = "apple banana carrot water";
solution(dictionary, sentence);
}
}문제 3
// Practice3
// 문자열 배열 strs 와 targets 가 주어졌을 때
// targets 내의 단어 중 한 문자만 바꾸면 strs 중의 단어가 되는지 판별하는 프로그램을 작성하세요.
// 입출력 예시
// 입력 strs: "apple", "banana", "kiwi"
// 입력 target: "applk", "bpple", "apple"
// 출력: true, true, false
public class Practice3 {
public static void solution(String[] strs, String[] targets) {
// 트라이 구성
Trie trie = new Trie();
for (String str : strs) {
trie.insert(str);
}
// target 별 검사
for (String target : targets) {
boolean result = examineWord(trie.root, target, 0, false);
System.out.print(result + " ");
}
System.out.println();
}
public static boolean examineWord(Node node, String target, int i, boolean flag){
if (i < target.length()) {
// 해당 문자로 시작하는 데이터가 trie 내에 있으면 그 다음 재귀 호출
if (node.child.containsKey(target.charAt(i))) {
if (examineWord(node.child.get(target.charAt(i)), target, i + 1, flag)) {
return true;
}
}
if (!flag) {
// 현재 depth 의 문자들 순회하며 비교
for (char c : node.child.keySet()) {
// 문자 하나만 다르고 나머지는 true 일 때 true 반환
if (c != target.charAt(i) && examineWord(node.child.get(c), target, i + 1, true)) {
return true;
}
}
}
return false;
}
// flag 가 true 인 상황에서 단어 끝일 때 true 반환
return flag && node.isTerminal;
}
public static void main(String[] args) {
// Test code
String[] strs = {"apple", "banana", "kiwi"};
String[] targets = {"applk", "bpple", "apple", "banan", "kiww"};
solution(strs, targets); // true, true, false, false, true
}
}추가 개념
트라이는 일반적으로 단어들을 사전의 형태로 생성한 후, 트리의 부모 자식 노드 관계를 이용해 검색을 수행
- N진 트리 : 문자 종류의 개수에 따라 N이 결정됨. 예를들어 알파벳은 26개 문자로 이뤄져 있으므로 26진 트리가 구성됨
- 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지
Journey for Backend Developer