Trie 자료구조

Trie 자료 구조

1. 개요

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

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

2. 사용되는 곳

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

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

3. 구현

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

TrieNode

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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;
  }
}

Trie

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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 가 되므로 없는 단어라 나온다.

Trie 자료구조

Trie 자료 구조

1. 개요

2. 사용되는 곳

3. 구현

4. 관련 문제

What's on this Page