[Algorithm] 트라이(Trie)

트라이(Trie)

• 트라이는 문자열 검색을 빠르게 실행할 수 있는 형태를 가진 트리 형태의 자료구조로 다음과 같은 특징을 가지고 있습니다.

• N진 트리: 문자 종류의 개수에 따라 N이 결정된다. 예를 들어 알파벳은 26개의 문자로 이루어져 있으므로 26진 트리로 구성된다.
• 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다.

단어 삽입해보기

• 먼저 루트 논드는 공백을 유지한채로 apple의 각 알파벳에 해당하는 노드를 생성

• 그 다음 air를 삽입할 때는 루트 노드에서부터 검색을 시작
• a노드는 공백 상태가 아니므로 a로 이동한 후 i와 r은 공백 상태 이므로 신규 노드를 생성

• apply 삽입도 마찬가지로 l까지는 이동한 후 공백 상태인 y 신규 노드 생성

알파벳 트라이 구현

class Node
{
public:
    Node* next[26]{};
    bool isEnd = false;
    Node()
    {
        fill(next, next + 26, nullptr);
    }

    ~Node()
    {
        for(auto& child : next)
        {
            delete child;
        }
    }

    // 문자열 삽입 함수
    void insert(const char* key)
    {
        if (*key == 0)
            isEnd = true;
        else
        {
            int next_idx = *key - 'a';

            if (next[next_idx] == nullptr)
                next[next_idx] = new Node();

            next[next_idx]->insert(key + 1);
        }
    }

    // 문자열 찾기 함수
    Node* find(const char* key)
    {
        if (*key == 0)
            return this;

        int next_idx = *key - 'a';

        if (next[next_idx] == nullptr)
            return nullptr;

        return next[next_idx]->find(key + 1);
    }
};