[알고리즘 공부] 트라이(Trie)

0. 개요

요즘 백준을 돌아다니다 보다가 처음 보는 자료 구조 형태가 있어서 찾아보았다.

이름부터 처음 들어본만큼 천천히 찾아보았다.

 

1. 알고리즘 개념

트라이(Trie)는 문자열을 저장하고 탐색하는 것에 최적화된 트리 기반 자료구조이다.

문자열 검색, 자동완성, 접두사 검사, 전화번호 목록 문제 등에서 사용된다.

 

기수 트리(radix tree), 접두사 트리(prefix tree), 탐색 트리(retrieval tree)라고도한다.

 

위 사진 처럼 특정 단어들의 접두사(혹은 앞글자)를 기준으로 관리하기 때문에

문자열이 많고 길 때 더 효율적으로 사용될 수 있다.

2. 알고리즘 구조

트리이기 때문에 노드의 구성을 먼저 살펴보자

struct TrieNode
{
	TrieNode* child[25]; // 알파벳은 26개임
    	bool isEnd;
}

특정 알파벳을 기준으로 내려가는 형식이기 때문에 특정 요소 하나 당 노드가 하나씩 만들어진다.

위 노드의 예시는 알파벳을 기준으로 하기에 최대 26개의 자식 노드를 가질 수 있다.

 

isEnd는 하나의 단어가 끝났는지를 알려주기 위한 플래그 값으로 사용된다.

 

1) 생성

트라이에 특정 단어를 삽입할 때는 다음의 순서를 따른다.

1. root 노드에서부터 출발하여 특정 요소의 노드가 있는지 확인한다.

2. 노드가 없다면 생성한다.

3. 단어의 끝에 다다르면, 해당 노드의 isEnd 플레그를 true로 바꾼다.

 

이 경우 문자열의 길이만큼(L) 각 문자열의 항목별로 요소 수(C)만큼 순회하기 때문에

O(L*C) 만큼의 시간 복잡도를 갖는다.

 

2) 탐색

트라이에 특정 단어를 탐색할 때는 다음의 순서를 따른다.

1. root 노드에서부터 출발하여 특정 요소의 노드가 있는지 확인한다.

2-1. 노드가 없다면 탐색 실패

2-2. 문자열의 끝 요소에 해당하는 노드의 isEnd가 true면 탐색 성공

 

이 경우 문자열의 길이만큼 탐색하기 때문에

O(L) 만큼의 시간 복잡도를 갖는다.

3. 알고리즘 구현

간단하게 영어 문자열을 예시로 들어보았다. (대소문자 구분 X)

struct TrieNode 
{
	const int elementCount = 26;
	TrieNode* child[elementCount];
    bool isEnd;
    
    TrieNode() 
    {
    	isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    // 삽입
    void insert(const string& s)
    {
    	TrieNode* node = this;
        for(int i = 0, size = s.length(); i < size; ++i)
        {
        	int index = s[i] - 'a';
            if(node->child[index] == nullptr)
            	node->child[index] = new TrieNode();
            node = node->child[index];
        }
        node->isEnd = true;
    }
    
    // 탐색
    bool search(const string& s)
    {
        TrieNode* node = this;
        for(int i = 0, size = s.length(); i < size; ++i)
        {
        	int index = s[i] - 'a';
            if(node->child[index] == nullptr)
            	return false;
            node = node->child[index];
        }
        return node->isEnd; // 끝이 아닌 경우 해당 단어는 추가되지 않았다는 의미
    }
}

4. 참고 사이트

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie