[Algorithm] Trie(트라이)

트라이(Trie)란?

✔️ Trie : 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

✔️ 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다.

✔️ 문자열 탐색시 하나씩 비교하면서 탐색하는 것보다 효율적

✔️ 빠르게 탐색이 가능하지만 각 노드에서 자식들에 대한 포인터드을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점 존재

✔️ 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 활용

구조

루트 노드

• 루트노드는 항상 비어있다.
• 루트노드의 자식노드는 각 단어들의 첫 글자이다.

endOfWord 표시

• 파란색으로 칠해져 있는 노드는 각 문자열의 마지막 글자이다.

각 노드 구성

• 각 노드의 자식 노드들을 Map에 저장한다.
• 해당 노드가 단어의 마지막을 뜻하는 endOfWord를 저장할 boolean형 필드를 갖는다.

과정

• 삽입(insert) 방법 루트노드부터 자식노드를 담은 Map에서 삽입할 문자열의 한 문자씩 찾아본 뒤, 없으면 추가하고 있으면 타고 들어간다. 문자열의 마지막 문자가 되면 노드에 마지막 노드라는 표시를 한다. 그림에서는 파란색 색칠을, 코드로는 endOfWord = true로 바꿔준다.
• 탐색(search) 방법 Trie에 “best”가 존재하는지 탐색해보자 중간에 한번이라도 원하는 값이 존재하지 않으면 트라이에는 “best”가 들어있지 않는 것이다.
  1. root node의 자식노드들 중 'b' 가 있는지 찾아본다. - 이제 b로 이동해서 찾는다.
  2. 'b' 노드의 자식노드들 중에서 'e' 가 있는지 찾아본다. - 이제 e로 이동해서 찾는다.
  3. 'e' 노드의 자식노드들 중에서 's' 가 있는지 찾아본다. - 이제 s로 이동해서 찾는다.
  4. 's' 노드의 자식노드들 중에서 't' 가 있는지 찾아본다. - t로 이동한다.
  5. 't'는 "best"의 마지막 글자이다. 't'의 endOfWord를 확인해보고 endOfWord=true면 탐색 성공이다.
  6. 't'의 endOfWord를 확인했는데 endOfWord=false면 탐색 실패이다. (트라이에 "best"가 없다.)
• 삭제(delete) 방법 “apple”을 삭제해보자
  1. 위의 탐색 방법으로 "apple"을 탐색하여 "apple"의마지막 노드로 이동한다.
  2. 'e'의 endOfWord를 확인하여 true면 삭제 성공이다. 'e'의 endOfWord를 false로 바꿔준다. (삭제한다는 것은 더이상 이 트라이에서 해당 문자열을 찾을 수 없다는 것이다.)
  3. 'e'의 자식노드가 있는지 확인한다. 없으면 이제 거꾸로 타고올라가면서 노드를 삭제해준다.
  4. 'l'에 'e'를 제외한 다른 자식노드가 있는지 확인한 후 없으면 'l' 노드를 삭제한다.
  5. apple 까지 도착했다. 찾아보니 p를 제외한 다른 자식노드('r') 이 존재한다. p는 삭제하지 않는다.

구현

• TrieNode

  public class TrieNode {
  
  		// 노드의 자식 노드들을 저장
      private Map<Character, TrieNode> childNodes = new HashMap<>();
  
  		// 이 노드가 단어의 끝인지 저장
      private boolean endOfWord;
  
      public Map<Character, TrieNode> getChildNodes() {
          return childNodes;
      }
  
      public boolean isEndOfWord() {
          return endOfWord;
      }
  
      public void setEndOfWord(boolean endOfWord) {
          this.endOfWord = endOfWord;
      }
  }

• Trie

  public class Trie {
  
      private TrieNode rootNode;
  
      public Trie() {
          rootNode = new TrieNode();
      }
  
      void insert(String word) {
          TrieNode node = this.rootNode;
  
          for (int i = 0; i < word.length(); i++) {
              node = node.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
          }
          node.setEndOfWord(true);
      }
  
      boolean contains(String word) {
          TrieNode node = this.rootNode;
  
          for (int i = 0; i < word.length(); i++) {
              char charAtIdx = word.charAt(i);
              node = node.getChildNodes().get(charAtIdx);
  
              if (node == null) {
                  return false;
              }
          }
  
          return node.isEndOfWord();
      }
  
      void delete(String word) {
          delete(this.rootNode, word, 0);
      }
  
      private void delete(TrieNode node, String word, int index) {
          char charAtIdx = word.charAt(index);
          TrieNode childNode = node.getChildNodes().get(charAtIdx);
          if(childNode == null) {
              System.out.println("There is no \"" + word + "\" in this Trie.");
              return;
          }
  
          index++;
          if (index == word.length()) {
              if (!childNode.isEndOfWord()) {
                  System.out.println("There is no \"" + word + "\" in this Trie.");
                  return;
              }
  
              if (!childNode.getChildNodes().isEmpty()) {
                  childNode.setEndOfWord(false);
              } else {
                  node.getChildNodes().remove(charAtIdx);
              }
          } else {
              delete(childNode, word, index);
  
              if (!childNode.isEndOfWord() && childNode.getChildNodes().isEmpty()) {
                  node.getChildNodes().remove(charAtIdx);
              }
          }
      }
  
      void print() {
          Queue<Map<Character, TrieNode>> queue = new LinkedList<>();
          queue.add(rootNode.getChildNodes());
  
          while (!queue.isEmpty()) {
              for (Map.Entry<Character, TrieNode> entry : queue.poll().entrySet()) {
                  System.out.println(entry.getKey());
                  queue.add(entry.getValue().getChildNodes());
              }
          }
      }
  }

시간 복잡도

최대 문자열 길이가 m일 때 문자의 갯수와 무관하게 시간 복잡도는 $O(m)$이다.

각 문자 하나를 배열의 위치로 지정하여 문자열 하나를 찾을 때 $O(1)$이므로 딱 길이만큼의 시간만 소요한다.

만약, 문자열 길이가 너무 커서 Map 구조를 사용하여 동적 할당을 해야 하는 경우에는 $O(mlogn)$을 요구할 수도 있다.