[자료구조/알고리즘 기초] Ch 11. 트라이

 

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

 

트라이의 특징

1. 검색어 자동완성, 사전 찾기 등에 응용될 수 있다. 

2. 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다. 

3. L 이 문자열의 길이일 떄, 삽입은 O(L)만큼 걸린다. 

4. 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

 

트라이 구조

1. 루트는 비어있다 

2. 각 간선 (링크)은 추가될 문자 키로 가진다. 

3. 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.

4. 해시테이블과 연결리스트를 사용하여 구할 수 있다.