[자료구조 면접 준비] 트라이 (Trie)

트라이(Trie)

문자열에서 검색을 빠르게 도와주는 자료구조이다. 정수형에서 이진탐색트리를 이용하면 시간 복잡도는 O(logN)이 나오게 된다. 문자열에서 적용했을 때, 문자열의 길이만큼 탐색을 진행해야 하기 때문에 길이를 M이라 하면 O(M*logN)이 걸리게 된다. 하지만 트라이 자료구조를 사용하게 된다면 시간복잡도를 O(M)에 끊을 수 있다.

 

다음 문자열 집합 {"rebro", "replay", "hi" , "high", "algo"} 를 트라이로 구현한 것이다. 그림에서 보면 알수 있듯이 문자열의 접두사에 대응되는 노드는 서로 연결된 트리이고 빨간 노드는 문자열의 끝을 의미한다. 트라이의 중요한 속성 중 하나는 root에서 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수도 있다. 

 

트라이의 장단점을 말해주세요.

 

장점으론, 문자열을 빠르게 찾을 수 있습니다. 문자열의 추가, 탐색 모두 O(M)만에 가능하다. 중복 문자열의 경우 한 번만 저장되기 때문에 메모리를 절약할 수도 있습니다.

 

단점으론, 필요한 메모리의 크기가 큽니다. 그래도 포인터 부분을 필요한 부분만 할당하는 방식으로 map이나 vector를 이용할 수도 있습니다.

---

[참고 자료]

[자료구조] 트라이(Trie) 자료구조