Go, Vantage point

가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.

Github | https://github.com/overnew/

Blog | https://everenew.tistory.com/

티스토리 뷰

알고리즘 공부/알고리즘 기법

Trie (Prefix Tree) 구현 문제와 함께 이해하기 (C++)

EVEerNew 2023. 7. 10. 18:46

릿코드의 문제 중에서 Trie(트라이) 또는 Prefix Tree를 구현하는 문제가 나온다.

문제

https://leetcode.com/problems/implement-trie-prefix-tree/description/

Implement Trie (Prefix Tree) - LeetCode

Can you solve this real interview question? Implement Trie (Prefix Tree) - A trie [https://en.wikipedia.org/wiki/Trie] (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There

leetcode.com

trie (prefix) 트리는 검색할 수 있는 단어의 사전 목록을 저장하는데 유용하다.

https://en.wikipedia.org/wiki/Trie

Trie - Wikipedia

From Wikipedia, the free encyclopedia K-ary search tree data structure This article is about a tree data structure. For the French commune, see Trie-sur-Baïse. TrieTypetreeInvented1960Invented byEdward Fredkin, Axel Thue, and René de la BriandaisAlgorith

en.wikipedia.org

root로부터 시작하여, 단어를 insert하면 알파벳이 연결된 순서를 따라가면서 노드를 연결한다.

예를들어 "tea"를 삽입하면 root -> t -> e -> a 순서대로 노드가 연결된다.

예시의 trie는 알파벳만을 저장하므로 소문자 알파벳으로 한정할 경우, trie의 node들은 최대 26개(알파벳 개수)의 자식 node를 가질 수 있도록 만들면 된다.

이를 이용하면 저장된 단어를 prefix로 만으로도 존재 여부를 빠르게 찾을 수 있다.

"te"로 시작하는 단어를 찾고 싶다면 root->t->e 로의 경로가 tire에 존재하는지 찾아보면 알 수 있다.

prefix가 아니라 "tea"라는 단어가 찾고 싶다면, trie의 node는 연결되는 알파벳의 자식 노드 이외에 자신에게서 word가 끝나는지 여부를 boolean으로 저장하면된다.

"tea"를 insert할때 word가 끝나는 3번 노드는 자신에서 끝나는 여부를 true로 저장하면 된다.

trie의 조회, 삽입 복잡도와 공간 복잡도은 단어(key)의 크기에 비례한다.

즉 O(N)이다.

prefix 존재 여부를 확인하는 기능을 활용하면 텍스트 자동완성과 같은 알고리즘을 구현할 수 있다.

하지만, 각 노드가 26개의 자식 노드를 가리켜야하므로 짧은 단어를 몇개만 저장한다면 오히려 엄청난 량의 공간 낭비가 발생한다.

따라서 릿코드의 문제에서도 실제로 trie를 포인터로 구현하면 속도와 공간 소모가 다른 유저에 비해 굉장히 낮다.

다른 유저들은 Map 자료구조를 활용해서 단어들을 때려 박아 구현했기 때문이다.

물론 알고리즘 문제를 푸는데 제한되지 않았다면 수단을 가릴 필요는 없으니, 훌륭한 전략이라고 생각한다.

실제로 공간 문제로 인해 단순한 구현보다는 다른 방식의 전략을 선택한다고 한다.

구현 코드

참고