pathas
2022. 4. 4. 20:51
정의
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
특징
- 검색어 자동완성, 사천 찾기 등에 응용 가능
- 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 탐색 가능
- L 이 문자열의 길이일 때 탐색, 삽입 시 O(L) 만큼 시간 소요
- 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용
규칙
- 루트는 비어 있음(공백)
- 각 간선(링크)은 추가될 문자를 키로 가짐
- 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐
- 해시 테이블과 연결 리스트를 이용하여 구현 가능