트라이 자료구조

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

트라이는 문자열을 탐색할 때 단순히 비교하는 것에 비해서 효율적으로 찾을 수 있는데, 정점이 자식에 대한 링크를 모두 가지고 있어서 저장공간을 많이 사용한다, 주로 검색어 자동완성이나 사전 찾기 기능을 구현할 때 사용한다.

트라이

트라이에서 각 노드는 하나의 문자를 나타낸다. 루트에서 특정 노드까지의 경로가 하나의 문자열이라고 생각하면 된다.

같은 접두사를 가진 문자열들은 같은 경로를 가진다. 각 노드에는 단어의 끝을 표시하는 불린 값이 있다.

 

트라이 자료구조를 사용하면 문자열 검색이 매우 빠르다. 접두사 검색에 효율적이라 자동완성을 사용하기에 좋다.

하지만 앞에서 말했던것 처럼 메모리 사용량이 많을 수 있고, 구현이 복잡하다.

 

트라이 자료구조에 루트값은 항상 비어있다. 위 예시 사진을 보면 각 간선은 추가될 문자를 키로 가지고 있는 것을 알 수 있다.

그리고 정점은 이전 정점의 값과 간선의 값을 더한 값을 가진다. 그래서 트라이를 구현할 때는 해시 테이블과 연결 리스트를 이용해서 구현한다.

 

트라이 자료구조 구현