이번 아티클에서는 자료구조 중 하나인 트라이(Trie)에 대해 알아본다.
트라이의 핵심
우선 용어에 대해 이해하는 것이 도움이 될 것 같다. Trie는 Retrieval Tree에서 추출한 단어라고 한다. 즉, 트라이는 트리이면서 검색(Retrieval)을 위해 사용될 수 있다. 그렇다면 트라이가 어떻게 검색에 활용될 수 있다는 것일까?
보통은 문자열 검색에서 트라이를 많이 활용하게 된다. 필자를 포함하여 대부분의 사람들은 검색창 자동완성 기능을 사용해 본 경험이 있을 것이다. 'coffee'를 검색하려고 할 때, 'cof' 까지만 치더라도 coffee라는 단어가 자동완성이 된다.
그렇다면 수많은 단어들 사이에서 cof가 coffee와 연관되어 있다는 사실은 어떻게 알아낼까? 사전에 기록된 모든 단어에 대해 브루트 포스로 순회하면서 비교할 순 없을 것이다.
이러한 시점에 사용해볼 수 있는게 트라이라는 자료구조이다. 트라이는 트리 구조를 가지고 있는데, 노드가 하나의 Prefix를 가지고 있고, 해당 Prefix들을 접목시켜나가면서 단어를 완성하는 방식이다.
루트 노드는 빈 문자열에 대응되며, 'ten'이라는 문자를 찾고 싶다고 가정하자. 그렇다면 t -> e -> n으로 해당 문자를 찾아낼 수 있다. 트라이의 핵심 특징 중 하나는 Prefix를 공유한다는 것인데, t -> e -> n과 t -> e -> a는 t -> e 라는 경로를 공유한다. 이에 따라 메모리 최적화가 가능하다. 필요한 모든 단어를 개별적으로 메모리에 저장할 필요가 없다.
또한 트리 내에서 단어가 완성되었다는 것을 표기하기 위해 별도의 비트 플래그나 Data 필드를 추가해 해당 노드까지의 데이터를 저장하기도 한다.
트라이는 Prefix Tree로 불리기도 하는데, 각 노드에서 문자열 등의 Prefix를 저장하는 과정을 거치기 때문이다. 이외에도 트라이의 변형된 종류로는 Radix Tree가 있고, 이는 한 노드에서 하나의 Prefix만 관리하는게 아니라, 메모리를 최적화하기 위해 여러 Prefix를 압축해 갖고 있는 자료구조를 의미한다.
참고로, 트라이는 문자열 검색 뿐만 아니라 비트열 검색이나 패턴 매칭에도 활용될 수 있다고 한다.
시간복잡도
트라이는 메모리를 많이 사용하는 대신, 시간적 효율성이 상당히 높다. 찾고자 하는 단어를 그대로 한글자씩 Prefix에 대입하여 트리를 탐색하면 되기 때문에, 조회의 경우 O(L)이라는 복잡도를 가진다. 여기서 L은 문자의 길이이다.
삽입의 경우에는, 모든 문자가 Prefix로 등록되어있지 않은 상태가 최악의 시나리오인데, 이 경우도 탐색과 동일하게 O(L) 의 복잡도를 가진다. 새로운 문자가 삽입되었다고 해서 트리를 재정렬할 필요가 없기 때문이다.
장단점
장점
- 공통 접두사(Prefix)를 단일 노드로 사용하기 때문에, 메모리 크기를 최적화할 수 있다.
- 검색, 추가가 쉽다. 두 경우 모두 O(L)의 시간 복잡도를 가진다.
단점
- 각 노드가 다른 노드를 가리키기 위한 포인터를 추가로 가지기 때문에, 메모리 부담이 있다. (한국어의 경우를 생각해보자)
- 정확히 일치하는 문자열을 찾는 과정은 트라이보다 이진 검색 트리(BST)나 해시가 효율적이다.
번외 - 한국어의 경우
한국어의 경우는 어떻게 될까? 알파벳의 경우 ASCII로 표현이 가능하지만, 한국어의 경우 2바이트 이상의 메모리를 사용하여야 한다. 또한, 자음과 모음의 조합이 많기 때문에, 노드 수가 급격하게 증가할 수 있다.
이러한 경우 글 초기에 언급하였던 Radix Tree를 사용하여 노드를 압축하거나, 하위 노드들을 관리하기 위한 전략으로 고정 크기 배열이 아닌 연결 리스트를 사용할 수 있고, 사용 빈도에 따라 가중치를 부여하여 캐싱과 비슷한 기능을 부여함으로서 해결할 수 있다.
참고 자료
https://www.geeksforgeeks.org/trie-meaning-in-dsa/
