[매일메일] 자료구조 트라이에 대해서 설명해주세요.

트라이 구조에 대해서 코딩 테스트를 했던 친구한테 들어본 적이 있다.

친구가 설명해 준 것으로는 욕설 관련 필터링을 구현할 때 어떻게 할 것인가? 라는 질문에 로직을 고민하던 중 찾다가 알게 되었다며 알려주었다. 간단하게 아는 부분은 트리 구조와 같이 진행되면서 문자열에 대한 서칭을 좋게 한다는 점이었다. 이제 세부 내용에 대해서 한 번 자세히 알아보자. 

 

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조라고 한다.

문자열을 비교하는 부분에서는 단순히 비교하는 것에 비하여 효율적일 수 있지만, 각 정점이 자식에 대한 링크를 모두 가지고 있기 때문에 저장 공간을 더욱 많이 사용한다는 특징이 있다.

이런 형태를 보인다고 한다.

루트 노드는 항상 비어져 있으며, 각 간선은 추가될 문자를 키로 가지고 있다.

각 정점은 이전 정점의 값과 간선의 키를 더한 결과를 값으로 가진다.

(-> 이게 음성인식 공부할 때, 발음에 따라 구분 짓던 그 트리랑 비슷하게 생겼다 (치경음이라면 오른쪽 왼쪽 이런식의 분석 파트였다.))

트라이 구현 시, 이러한 구조를 염두에 두면서 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

구현 코드를 확인한 결과 단순히, 트리 구조를 배열 형태가 아닌 노드 형태로 구현한 것과 같은 형태였다. (생각보다 굉장히 단순하고 그냥 말 그대로 층을 내려 갈수록 누적되는 것만 구현하면 되는 단순한 구현이다.)