Trie

Trie 자료 구조

1. 개요

• 문자열을 다루는 작업은 정수나 실수 등의 다른 자료형을 다루는 것과는 다르다. 왜냐하면 정수나 실수형 변수는 그 크기가 정해져 있어 비교에 상수 시간이 걸린다고 봐도 되지만, 문자열 변수는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다.
• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조

• 위와 같은 트리 형태의 구조를 가지며, 공간을 많이 차지하는 대신, 시간 복잡도는 O(M - M은 문자열 길이) 이 되어 엄청 빠르게 검색이 가능하다.

2. 사용되는 곳

• 일단, 어디에서 사용되는지 알고 배워야 좋지 않을까?

1. 단어 검색 (자동완성으로도 사용이 가능한 것 같다.)
2. 스펠 체크
3. 아이피 라우팅 (아이피를 숫자로 바꿔서 할 줄 알았는데, 문자열 그대로 하나보다..)
4. 문장 풀이 게임

3. 구현

• java 로 구현하기에 trie 와 trieNode 가 필요.

1. TrieNode

   • childTrieNode 와 현재 노드가 마지막인지 여부에 대한 Boolean 정보를 가지고 있음.
   • 마지막인지에 대한 말은 snack 가 있으면 s,n,a,c 까지는 마지막이 아니지만, k 는 마지막 이기 때문에 true 가 됩니다.

   public class TrieNode {
     private final int ALP = 26;
   
     private TrieNode[] child;
     private boolean isEnd;
   
     public TrieNode() {
       child = new TrieNode[ALP];
     }
   
     public boolean containsKey(char ch) {
       return child[ch-'a'] != null;
     }
   
     public TrieNode get(char ch) {
       return child[ch-'a'];
     }
   
     public void put(char ch, TrieNode node) {
       child[ch-'a'] = node;
     }
   
     public void setEnd() {
       isEnd = true;
     }
   
     public boolean isEnd() {
       return isEnd;
     }
   }

2. Trie

   • 기본적으로 빈 노드를 가지고 있음
   • 삽입, 검색을 추가

   public class Trie {
     private TrieNode root;
   
     public Trie() {
       root = new TrieNode();
     }
   
     // 삽입 추가
     public void insert(String word) {
       TrieNode node = root;
       for(int i = 0; i < word.length(); i++) {
         char currentChar = word.charAt(i);
         if(!node.containsKey(currentChar)) {
           node.put(currentChar, new TrieNode());
         }
         node = node.get(currentChar);
       }
       node.setEnd();
     }
   
     // 검색 추가
     private TrieNode searchPrefix(String word) {
       TrieNode node = root;
       for(int i = 0; i < word.length(); i++) {
         char cur = word.charAt(i);
         if(node.containsKey(cur)) {
           node = node.get(cur);
         } else {
           return null;
         }
       }
       return node;
     }
   
     // 검색 추가
     public boolean search(String word) {
       TrieNode node = searchPrefix(word);
       return node != null && node.isEnd();
     }
   }

   • 삽입

     -> 파라미로 받은 word 를 반복문을 통해 존재할 경우 하위(child) 노드로 옮기고, 존재하지 않을 경우 하위 노드 생성

     -> Ex) 이미 spirng 이라고 들어가 있는 Trie 에 speak 를 넣을 경우 sp 까지만 진행하고 그 이후 eak 부분은 생성하면서 k에 isEnd 가 true 가 됨

   • 검색

     -> 삽입과 마찬가지로 반복문을 통해 word 의 마지막 단어까지 존재하는지 확인한다. 없을 경우 null 이 반환되고, 단어가 있지만, 마지막이 아닐 경우 isEnd() 가 false 가 되므로 없는 단어라 나온다.

4. 관련 문제

• 릿코드 208번 Trie 구현
• 릿코드 211번 단어 사전
• 2020카카오 블라인드 - 가사 검색