트라이
개요
- 문자열을 저장하고 효율적으로 탐색하는 자료구조 입니다.
- 간선에 이전 정점으로부터 새롭게 추가되는 문자정보를 가지고 있습니다.
- 트리 형태를 가지고 있습니다.
특징
- 검색어 자동완성, 사전 찾기 등에 응용될 수 있습니다.
- 문자열 탐색시, 단순한 비교 방법보다 효율적입니다.
- 단순한 비교 방법 : O(n*L)
- 트리이 : O(L)
- 대신 저장공간을 더 많이 사용합니다.
- 각 정점이 자식에 대한 링크(간선)를 전부 가지고 있기 때문입니다.
구조
- 루트는 비어있습니다.
- 각 간선(링크)은 추가될 문자를 키로 가집니다.
- 각 정점은 이전 정점의 값(이전) + 간선의 키(현재)를 값으로 가집니다.
- 해시 테이블과 연결 리스트를 이용하여 구현할 수 있습니다.
JS에서의 구현
깃허브: https://github.com/HyeonWooGa/algorhithm-code-snippet
Aim for the TOP, Developer