트라이(Trie)

[devLupin]

• 문자열을 효율적으로 처리하기 위한 트리 자료구조
• 단어 S를 삽입/탐색/삭제할 때 $O(|S|)$
  • 이진트리로 탐색하는 경우 $O(|S| * lgN)$
  • 해시로 탐색하는 경우 $O(|S|)$
    • 이론상으로 이렇고, 실제로는 충돌 때문에 더 좋지 않을 수 있음.
• 트라이는 메모리를 아주 많이 차지한다는 단점이 있음.
  • 4x글자의 종류 배 만큼 더 사용
  • 트라이는 문자열을 삭제할 때 문자열이 있다는 표시만 제거한다.
    • 트리 구조를 유지해야되기 때문에
    • 삭제가 자주 일어나는 환경에서는 트라이가 적합하지 않다.

[devLupin]

• 사용되는 변수들

const int ROOT = 1;    // 루트
int unused = 2;  // 사용된 정점의 번호
const int MX = 10000 * 500 + 5;  // 문자의 등장횟수(+5는 배열 여유를 둔 것)
bool chk[MX]  // 문자열의 끝이다 라는 표시
int nxt[MX][26];  // 자식 정점 번호, 알파벳이라는 가정(26개)
                      // O(1)에 탐색이 가능하지만 메모리 측면에서 조금 비효율적임.

for(int i=0; i<MX; i++)
    fill(nxt[i], nxt[i]+26, -1);    // 돌다가 -1을 만나면 해당 자식 정점이 없다는 뜻

[devLupin]

• example

nxt[5][4] = 6;  // 5번 위치의 자식은 4번째 알파벳이고(E가 4번째 알파벳) 6번 노드에 저장되어 있다.
nxt[5][24]=7;  // 5번 위치의 다른 자식은 24번째 알파벳이고(Y = 24번째) 7번 노드에 저장되어 있다.
nxt[5][나머지] = -1

// chk배열
  // 초록색으로 표시된 게 단어의 끝이라는 의미이고
  // 해당 부분만 true, 그 외에는 false이다.

[devLupin]

• insert

void insert(string &s) {
  int cur = ROOT;    // init
  for(auto c : s) {
    if(nxt[cur][c2i(c)] == -1)    // 자식 정점이 없으니
      nxt[cur][c2i(c)] = unused++;    // 새로운 정점 번호 부여
    cur = nxt[cur][c2i(c)];  // 이후, 현재 보고 있는 정점 이동
  }
  chk[cur] = true;

[devLupin]

• find

bool find(string& s) {
  int cur = ROOT;
  for(auto c : s) {
    if(nxt[cur][c2i(c)] == -1)
      return false;
    cur = nxt[cur][c2i(c)];
  }
  return chk[cur];
}

[devLupin]

• erase

void erase(string& s) {
  int cur = ROOT;
  for(auto c : s) {
    if(nxt[cur][c2i(c)] == -1)  // 트라이에 없음.
      return;
    cur = nxt[cur][c2i(c)];
  }
  chk[cur] = false;
}