트라이(Trie)

🕹️ 트라이(Trie) 란?

트라이는 “문자열을 빠르게 탐색하게 해주는 자료구조” 이다.

작동원리

트라이는 주어진 문자열을 이루고 있는 문자를 앞에서부터 하나씩 노드를 생성해가면서 만들어진다.

재귀 호출을 사용한다.

1. 주어진 문자열에서 현재 문자를 가져온다
2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하고, 노드가 없다면 그 노드를 새로 할당받은 후, 해당 노드를 통해 다음 문자열을 탐색한다
3. 문자열의 마지막이 될 때까지 위의 과정을 반복한다.

트라이의 장점

• 문자열 탐색에 유리하다
• 트라이에 삽입만 하게 된다면 자동으로 정렬된 효과를 얻을 수 있다.

Code - C++

트라이를 생성하기 위해 만든 구조체

struct TRIE
{
    bool Finish;     // 위에 사진에서 네모와 같이 문자열이 끝난지점을 체크해준다. 
    TRIE *Node[26];  // 노드 , 알파벳은 총 26개
    TRIE()           // 생성자를 통해 노드 생성 
    { 
        Finish = false;  
        for (int i = 0; i < 26; i++) Node[i] = NULL;
    }
}

트라이에 문자열 삽입 함수

“Str”이라는 문자열을 삽입한다.

void Insert(char *Str)
{
    if (*Str == NULL)
    {
        Finish = true;
        return;
    }
 
    int Cur = *Str - 'A';            // 현재 문자열 가져오기 
    if (Node[Cur] == NULL) Node[Cur] = new TRIE();    // 현재 연결된 노드가 없는 경우 노드 생성 
    Node[Cur]->Insert(Str + 1);     // 다음 문자열로 넘어가기 
}

🔗 참조한 사이트

https://yabmoons.tistory.com/379

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Data Structure/Trie.md