트라이 Trie

• 문자열을 효율적으로 처리하기 위한 트리 자료구조
• 트리의 루트에서 시작해서 읽어나가면 각 단어에 대응이 된다.
• 👍 단어 S를 삽입/탐색/삭제할 때 $O(|S|)$ : 좋은 시간복잡도
• 👎 문자열을 그냥 배열에 저장하는 것보다 최대 (4 X 글자의 종류)배만큼 더 사용

이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진 검색 트리에 비해 훨씬 느리다/
메모리를 아주 많이 차지하기 때문에 메모리 사용량이 병목이 될 수 있다.
(삭제를 하더라도 이전에 삽입한 정점들은 메모리에 계속 남아있게 되어 비효율적이다.)​
그냥 문자열의 삽입/삭제/검색을 수행해야 하는 상황에서는 트라이보다 해시, 이진 검색 트리를 쓰는 것이 메모리와 시간 측면 모두에서 효율적이고 난이도도 낮다.
일반적인 상황에서는 해시나 이진 검색 트리를 사용하는게 좋으나 트라이의 성질을 사용해야 하는 문제에서는 트라이를 사용하자.
👉 (자동 완성, 접두사와 접미사와 관련된 무언가)

구현

const int ROOT = 1;
int unused = 2;
const int MX = 10000 * 500 + 5;  // 최대 등장 가능한 글자의 수
bool chk[MX];    // string의 끝인지 체크
int nxt[MX][26];
​
for(int i = 0; i < MX; i++)
    fill(nxt[i], nxt[i]+26; -1);
​
int c2i(char C) {
    return c - 'A';
}

• 루트 번호는 1로 고정
  • 정점이 추가될 때마다 unused를 이용하여 번호 부여
• MX는 최대 등장 가능한 글자 수. 문제의 제한 조건으로부터 유추하자.
  • 예를 들어 길이가 최대 500인 문자열이 10000개 들어오면 10000 * 500으로 둘 수 있다.
• chk은 초록색 테두리로 나타냈던, 해당 정점이 문자열의 끝인지 여부를 저장하는 배열이다.
• nxt는 각 정점에서 자식 정점의 번호를 의미한다.
  (예시는 문자로 알파벳이 가능하기 때문에 26으로 선언한다.)
• 배열에 문자열을 그냥 저장하면 글자당 1바이트를 사용하지만 트라이는 자식 정점의 번호를 저장하기 위해 각 글자마다 int(4바이트) 26칸이 필요하게 된다.
• c2i 함수는 글자를 배열의 인덱스로 변환하는 함수이다.

insert 함수

void insert(string& a) {
  int cur = ROOT;
  for(auto c : s) {
    if(nxt[cur][c2i(c)] == -1)
      nxt[cur][c2i(c)] = unused++;
    cur = nxt[cur][c2i(c)];
  }
  chk[cur] = true;
}

• cur : 현재 보고있는 정점, 초기값은 ROOT
  • for문을 이용해 글자에 대응되는 자식 정점으로 이동

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

• 자식 정점으로 계속 이동, 존재하지 않는 자식 정점을 만나면 false 반환
• 마지막 글자에 대응되는 정점에 도달한 후에는 바로 chk[cur] 반환

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