트라이 (Trie)

Topology Sort

정의

1. 문자열 집합을 표현하는 ‘트리 자료구조’

특징

장점

1. 문자열을 빠르게 찾을 수 있다.
2. 다른 문자열에 포함되는 문자열의 존재를 알 수 있다.
3. 문자열의 접두사를 모두 알 수 있다.

   단점

4. 필요한 메모리의 크기가 너무 크다. (문자를 저장할 때)
   1. 문자 a ~ z 를 모두 저장하는게 아니라면 vector 나 map 을 이용하면 좋다
   2. 저장해야하는 정보가 특정되어있다면 배열을 이용하자 (ex. 1 ~ 10, ‘A’ ~ ‘Z’)

구현

struct Trie
{
    bool end;   // 단어의 끝인지 확인
    map<char, Trie*> nextChar;      // 현재 노드에서 뻗어나가는 다음 노드

    Trie() : end(false) {}
    ~Trie()
    {
        for (pair<char, Trie*> iter : nextChar)
        {
            delete nextChar.second; // 각 부모에서 자식을 재귀적으로 삭제
        }
    }
}

Trie * head;

void Insert(string data)
{
    Trie* now = head;
    for (int i = 0; i < data.length(); ++i)
    {
        if (now->nextChar.find(data[i]) == now->nextChar.end())
        {
            now->nextChar[data[i]] = new Trie();
        }
        now = now->nextChar[data[i]];
        if (i == data.length() - 1) now->end = true;
    }
}

참조

참조1